ulvis.paste.net

Paste Search Dynamic
Recent pastes
getMedian
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int hminSize = 0;
  4. int hmaxSize = 0;
  5. double currMed = 0;
  6. int heapMin[100001];
  7. int heapMax[100001];
  8.  
  9. void heapifyMinUp()
  10. {
  11.     int i = hminSize;
  12.     int par = i/2;
  13.     int key = heapMin[hminSize];
  14.     while(par>0 && key<heapMin[par])
  15.     {
  16.         heapMin[i] = heapMin[par];
  17.         i = par;
  18.         par = i/2;
  19.     }
  20.     heapMin[i] = key;
  21. }
  22. void InsertMin(int key)
  23. {
  24.     heapMin[++hminSize] = key;
  25.     heapifyMinUp();
  26. }
  27.  
  28. void heapifyMaxUp()
  29. {
  30.     int i = hmaxSize;
  31.     int par = i/2;
  32.     int key = heapMax[hmaxSize];
  33.     while(par>0 && key>heapMax[par])
  34.     {
  35.         heapMax[i] = heapMax[par];
  36.         i = par;
  37.         par = i/2;
  38.     }
  39.     heapMax[i] = key;
  40. }
  41. void InsertMax(int key)
  42. {
  43.     heapMax[++hmaxSize] = key;
  44.     heapifyMaxUp();
  45. }
  46.  
  47. void heapifyMinDown(int i)
  48. {
  49.     int smallest = i;
  50.     int left = 2*i;
  51.     int right = left+1;
  52.     if(left < hminSize && heapMin[left]<heapMin[smallest])
  53.     {
  54.         smallest = left;
  55.     }
  56.     if(right < hminSize && heapMin[right]<heapMin[smallest])
  57.     {
  58.         smallest = right;
  59.     }
  60.     if(smallest != i)
  61.     {
  62.         swap(heapMin[smallest],heapMin[i]);
  63.         heapifyMinDown(smallest);
  64.     }
  65. }
  66. int delMinHeap()
  67. {
  68.     int top = heapMin[1];
  69.     heapMin[1] = heapMin[hminSize];
  70.     heapifyMinDown(1);
  71.     hminSize--;
  72.     return top;
  73. }
  74.  
  75. void heapifyMaxDown(int i)
  76. {
  77.     int largest = i;
  78.     int left = 2*i;
  79.     int right = left+1;
  80.     if(left < hmaxSize && heapMax[left]>heapMax[largest])
  81.     {
  82.         largest = left;
  83.     }
  84.     if(right < hmaxSize && heapMax[right]>heapMax[largest])
  85.     {
  86.         largest = right;
  87.     }
  88.     if(largest != i)
  89.     {
  90.         swap(heapMax[largest],heapMax[i]);
  91.         heapifyMaxDown(largest);
  92.     }
  93. }
  94. int delMaxHeap()
  95. {
  96.     int top = heapMax[1];
  97.     heapMax[1] = heapMax[hmaxSize];
  98.     heapifyMaxDown(1);
  99.     hmaxSize--;
  100.     return top;
  101. }
  102.  
  103. void getMedian()
  104. {
  105.     double res;
  106.     if(hminSize == hmaxSize)
  107.     {
  108.         res = heapMin[1] + heapMax[1];
  109.         res = (res*1.0)/2;
  110.     }
  111.     else if(hminSize > hmaxSize)
  112.     {
  113.         res = heapMin[1];
  114.         res = (res*1.0);
  115.     }
  116.     else
  117.     {
  118.         res = heapMax[1];
  119.         res = (res*1.0);
  120.     }
  121.     currMed = res;
  122. }
  123. void PrintMin() {
  124.         printf("\n----------------------------------------\n");
  125.         for(int i = 1; i <= hminSize; i++) {
  126.                 printf("%d ", heapMin[i]);
  127.         }
  128.         printf("\n");
  129.         //printf("\n----------------------------------------\n");
  130. }
  131. void PrintMax() {
  132.         printf("\n");
  133.         //printf("\n----------------------------------------\n");
  134.         for(int i = 1; i <= hmaxSize; i++) {
  135.                 printf("%d ", heapMax[i]);
  136.         }
  137.         printf("\n----------------------------------------\n");
  138. }
  139. int main()
  140. {
  141.     int n;
  142.     cin>>n;
  143.     int k;
  144.     int i , a, b;
  145.     cin>>a>>b;
  146.     if(a>b)
  147.     {
  148.         InsertMin(a);
  149.         InsertMax(b);
  150.     }
  151.     else
  152.     {
  153.         InsertMin(b);
  154.         InsertMax(a);
  155.     }
  156.     currMed = (a*1.0);
  157.     printf("%.1f\n",currMed);
  158.     currMed = ((a+b)*1.0)/2;
  159.     printf("%.1f\n",currMed);
  160.  
  161.     for(i=2;i<n;i++)
  162.     {
  163.         cin>>k;
  164.         if(k>=currMed)
  165.         {
  166.             InsertMin(k);
  167.             // if(k == 8)
  168.             // PrintMin();
  169.         }
  170.         else
  171.         {
  172.             InsertMax(k);
  173.         }
  174.         if(hminSize > hmaxSize+1)
  175.         {
  176.             InsertMax(delMinHeap());
  177.             // if(k == 8) {
  178.             //  printf("This is called\n");
  179.             // }
  180.         }
  181.         if(hmaxSize > hminSize+1)
  182.         {
  183.             InsertMin(delMaxHeap());
  184.         }
  185.         //PrintMin();
  186.         //PrintMax();
  187.         getMedian();
  188.         printf("%.1lf\n",currMed);
  189.     }
  190.     return 0;
  191. }
Parsed in 0.026 seconds