SHOW:
|
|
- or go back to the newest paste.
1 | #include <stdio.h> | |
2 | #include <algorithm> | |
3 | ||
4 | - | static const int maxn = 8192; |
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 * 1000]; |
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 | } |