Guest User

Untitled

a guest
Oct 16th, 2013
1,587
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <algorithm>
  3.  
  4. static const int maxn = (1 << 17); // smallest power of 2 not less than 10^5
  5. int coords[maxn];
  6. int array[maxn];
  7.  
  8. typedef struct node {
  9.     node *l, *r;
  10.     int sum;
  11. } *Node;
  12.  
  13. node buffer[maxn * 50];
  14. Node ver[maxn];
  15.  
  16. Node allocate(int number = 1)
  17. {
  18.     static Node freep = buffer;
  19.     Node res = freep;
  20.     freep += number;
  21.     return res;
  22. }
  23.  
  24. Node update(Node v, int vl, int vr, int x)
  25. {
  26.     if (vl == x && vr == x + 1) {
  27.         Node u = allocate();
  28.         *u = *v;
  29.         u->sum = 1;
  30.         return u;
  31.     }
  32.     Node u = allocate();
  33.     *u = *v;
  34.     int m = (vl + vr) / 2;
  35.     if (x < m)
  36.         u->l = update(u->l, vl, m, x);
  37.     else
  38.  
  39.         u->r = update(u->r, m, vr, x);
  40.     ++u->sum;
  41.     return u;
  42. }
  43.  
  44.  
  45. std::pair<int, bool> find_nth(Node u, Node v, int vl, int vr, int k)
  46. {
  47.     int sum = v->sum - u->sum;
  48.     if (vr - vl == 1) {
  49.         if (k == sum)
  50.             return std::make_pair(vl, false);
  51.     }
  52.     if (sum < k)
  53.         return std::make_pair(vr, true);
  54.     if (vr - vl == 1)
  55.         return std::make_pair(vl, false);
  56.     std::pair<int, bool> p = find_nth(u->l, v->l, vl, (vl + vr) / 2, k);
  57.     if (!p.second)
  58.         return p;
  59.     return find_nth(u->r, v->r, (vl + vr) / 2, vr, k - v->l->sum + u->l->sum);
  60. }
  61.  
  62. int main()
  63. {
  64.     int n, m;
  65.     FILE *in = stdin;
  66.     FILE *out = stdout;
  67.     fscanf(in, "%d%d", &n, &m);
  68.     for (int i = 0; i < n; ++i)
  69.         fscanf(in, "%d", &array[i]);
  70.     std::copy(array, array + n, coords);
  71.     std::sort(coords, coords + n);
  72.     for (int i = 0; i < n; ++i)
  73.         array[i] = std::lower_bound(coords, coords + n, array[i]) - coords;
  74.     allocate(2 * maxn - 1);
  75.     for (int i = maxn - 2; i >= 0; --i)  {
  76.         buffer[i].l = &buffer[2 * i + 1];
  77.         buffer[i].r = &buffer[2 * i + 2];
  78.     }
  79.     ver[0] = buffer;
  80.     for (int i = 0; i < n; ++i)
  81.         ver[i + 1] = update(ver[i], 0, maxn, array[i]);
  82.        
  83.     for (int i = 0; i < m; ++i) {
  84.         int l, r, k;
  85.         fscanf(in, "%d%d%d", &l, &r, &k);
  86.         --l;
  87.         fprintf(out, "%d\n", coords[find_nth(ver[l], ver[r], 0, maxn, k).first]);
  88.     }
  89.     return 0;
  90. }
RAW Paste Data