# 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