fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
  3. #define down(i,a,b) for (int i = (int)a; i >= (int)b; i--)
  4. using namespace std;
  5.  
  6. const int maxn = 5e6 + 10;
  7. int Heap[maxn];
  8.  
  9. void max_HeapifyDown(int Heap[], int n, int i){
  10.     int maxx_id = i;
  11.     int l = (i << 1);
  12.     int r = l+1;
  13.  
  14.     if (l > n) return;
  15.  
  16.     if (l <= n && Heap[l] > Heap[maxx_id]) maxx_id = l;
  17.     if (r <= n && Heap[r] > Heap[maxx_id]) maxx_id = r;
  18.  
  19.     if (maxx_id != i){
  20.         swap(Heap[i], Heap[maxx_id]);
  21.         max_HeapifyDown(Heap, n, maxx_id);
  22.     }
  23. }
  24.  
  25. void buildMaxHeap(int Heap[], int n){
  26.     for (int i = n/2; i >= 1; i--) max_HeapifyDown(Heap, n, i);
  27. }
  28.  
  29. int ans[maxn];
  30. void sortArray(int Heap[], int n){
  31.     down(i,n,1) {
  32.         ans[i] = Heap[1];
  33.         swap(Heap[1], Heap[i]);
  34.         max_HeapifyDown(Heap, i-1, 1);
  35.     }
  36. }
  37.  
  38. void max_HeapifyUp(int Heap[], int n, int curNode){
  39.     int par = curNode/2;
  40.     if (par >= 1){
  41.         if (Heap[curNode] > Heap[par]){
  42.             swap(Heap[curNode], Heap[par]);
  43.             max_HeapifyUp(Heap, n, par);
  44.         }
  45.     }
  46. } 
  47. /*
  48. Heap phai la mot maxHeap moi UpHeapify duoc
  49. */
  50.  
  51. void insertNode(int Heap[], int& n, int Key){
  52.     ++n;
  53.     Heap[n] = Key;
  54.     max_HeapifyUp(Heap, n, n);
  55. }
  56.  
  57. void deleteNode(int Heap[], int& n){
  58.     int last = Heap[n];
  59.     Heap[1] = last;
  60.     --n;
  61.     max_HeapifyDown(Heap, n, 1);
  62. } //xoa topNode cua Heap
  63.  
  64. void printHeap(int Heap[], int n){
  65.     up(i,1,n) cout << Heap[i] << " ";
  66.     cout << "\n";
  67. }
  68.  
  69. signed main(){
  70.     ios_base::sync_with_stdio(false);
  71.     cin.tie(0);
  72.     #define Task "A"
  73.     if (fopen(Task".inp", "r")){
  74.         freopen(Task".inp", "r", stdin);
  75.         freopen(Task".out", "w", stdout);
  76.     }
  77.  
  78.     int n, k;
  79.     cin >> n >> k;
  80.     int curSize = 0;
  81.  
  82.     int x;
  83.     up(i,1,k){
  84.         cin >> x;
  85.         insertNode(Heap, curSize, x);
  86.     }
  87.  
  88.     up(i,k+1,n){
  89.         cin >> x;
  90.         if (x > Heap[1]) continue;
  91.         Heap[1] = x;
  92.         max_HeapifyDown(Heap, curSize, 1);
  93.     }
  94.  
  95.     cout << Heap[1];
  96. }
  97. /*
  98. tim phan thu nho thu k trong mang
  99. vi du: n = 10, k = 3
  100. 4 5 6 2 3 1 9 8 7 10
  101. ans = 3
  102.  
  103. n = 3, k = 2;
  104. 3 3 3
  105. ans = 3
  106. */
  107.  
Success #stdin #stdout 0s 5612KB
comments (?)
stdin
copy 
12 7
74 12 65 32 98 65 45 78 98 10 10 45
stdout
copy 
65
https://ideone.com/wk1JBw
Simple Heapify
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!