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 | } |
