Advertisement
MickyOr

Untitled

Dec 1st, 2016
142
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. int T[4 * 1000000];
  8.  
  9. void init(int b, int e, int nodo)
  10. {
  11.     int mid = (b + e) / 2, L = 2 * nodo + 1, R = L + 1;
  12.     if (b == e) T[nodo] = 1;
  13.     else
  14.     {
  15.         init(b, mid, L);
  16.         init(mid + 1, e, R);
  17.         T[nodo] = T[L] + T[R];
  18.     }
  19. }
  20.  
  21. void query(int b, int e, int nodo, int k)
  22. {
  23.     int mid = (b + e) / 2, L = 2 * nodo + 1, R = L + 1;
  24.     if (b == e)
  25.     {
  26.         cout << b + 1 << endl;
  27.         T[nodo] = 0;
  28.     }
  29.     else
  30.     {
  31.         if (T[L] >= k) query(b, mid, L, k);
  32.         else query(mid + 1, e, R, k - T[L]);
  33.         T[nodo] = T[L] + T[R];
  34.     }
  35. }
  36.  
  37. int main()
  38. {
  39.     //ofstream fcin("in.txt", std::ofstream::out);
  40.     //freopen("out.txt", "w", stdout);
  41.     //srand( time (NULL));
  42.     int n;
  43.     cin >> n;
  44.     //fcin << n << " ";
  45.     init(0, n - 1, 0);
  46.     int m;
  47.     cin >> m;
  48.     //fcin << m << endl;
  49.     while (m--)
  50.     {
  51.         int k;
  52.         cin >> k;
  53.         //k = rand() % T[0] + 1;
  54.         //fcin << k << endl;
  55.         query(0, n - 1, 0, k);
  56.     }
  57.     return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement