Guest User

Untitled

a guest
Oct 16th, 2013
1,358
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.  
  6. int coords[maxn];
  7. int array[maxn];
  8. int arrayp[maxn];
  9.  
  10. typedef struct node {
  11.     node *l, *r;
  12.     int sum;
  13. } *Node;
  14.  
  15. node buffer[maxn * 20]; // XXX: Perhaps 20 is not a correct value
  16. Node ver[maxn];
  17.  
  18. Node allocate(int number = 1)
  19. {
  20.     static Node freep = buffer;
  21.     if (freep + number > buffer + maxn * 1000)
  22.         for (;;) ;
  23.     Node res = freep;
  24.     freep += number;
  25.     return res;
  26. }
  27.  
  28. Node update(Node v, int vl, int vr, int x)
  29. {
  30.     if (vl == x && vr == x + 1) {
  31.         Node u = allocate();
  32.         *u = *v;
  33.         u->sum = 1;
  34.         return u;
  35.     }
  36.     Node u = allocate();
  37.     *u = *v;
  38.     int m = (vl + vr) / 2;
  39.     if (x < m)
  40.         u->l = update(u->l, vl, m, x);
  41.     else
  42.         u->r = update(u->r, m, vr, x);
  43.     ++u->sum;
  44.     return u;
  45. }
  46.  
  47.  
  48. std::pair<int, bool> find_nth(Node u, Node v, int vl, int vr, int k)
  49. {
  50.     int sum = v->sum - u->sum;
  51.     if (vr - vl == 1) {
  52.         if (k == sum)
  53.             return std::make_pair(vl, false);
  54.     }
  55.     if (sum < k)
  56.         return std::make_pair(vr, true);
  57.     if (vr - vl == 1)
  58.         return std::make_pair(vl, false);
  59.     auto p = find_nth(u->l, v->l, vl, (vl + vr) / 2, k);
  60.     if (!p.second)
  61.         return p;
  62.     return find_nth(u->r, v->r, (vl + vr) / 2, vr, k - v->l->sum + u->l->sum);
  63. }
  64.  
  65. int main()
  66. {
  67.     int n;
  68.     FILE *in = fopen("input.txt", "r");
  69.     FILE *out = fopen("output.txt", "w");
  70.     fscanf(in, "%d", &n);
  71.     for (int i = 0; i < n; ++i)
  72.         fscanf(in, "%d", &array[i]);
  73.     std::copy(array, array + n, coords);
  74.     std::sort(coords, coords + n);
  75.     for (int i = 0; i < n; ++i)
  76.         array[i] = std::lower_bound(coords, coords + n, array[i]) - coords;
  77.     for (int  i = 0; i < n; ++i)
  78.         arrayp[array[i]] = i;
  79.     allocate(2 * maxn - 1);
  80.     for (int i = maxn - 2; i >= 0; --i)  {
  81.         buffer[i].l = &buffer[2 * i + 1];
  82.         buffer[i].r = &buffer[2 * i + 2];
  83.     }
  84.     ver[0] = buffer;
  85.     for (int i = 0; i < n; ++i)
  86.         ver[i + 1] = update(ver[i], 0, maxn, array[i]);
  87.     int m;
  88.     fscanf(in, "%d", &m);
  89.     for (int i = 0; i < m; ++i) {
  90.         int l, r, k;
  91.         fscanf(in, "%d%d%d", &l, &r, &k);
  92.         --l;
  93.         fprintf(out, "%d\n", arrayp[find_nth(ver[l], ver[r], 0, maxn, k).first] - l + 1);
  94.     }
  95.     return 0;
  96. }
RAW Paste Data