oj.uz

Submission #887310

# Submission time Handle Problem Language Result Execution time Memory
887310 2023-12-14T08:58:10 Z MinaRagy06 Index (COCI21_index) C++17
110 / 110
 787 ms 54020 KB 
#include <bits/stdc++.h>
using namespace std;
#define md ((l + r) >> 1)

struct node {
    int l, r, v;
    node() {l = 0, r = 0, v = 0;}
    node(int _v) {l = 0, r = 0, v = _v;}
} seg[4'000'005];
int cur = 2;
int newpar(int l, int r) {
    int i = cur++;
    seg[i].l = l;
    seg[i].r = r;
    seg[i].v = seg[l].v + seg[r].v;
    return i;
}
int newleaf(int v) {
    int i = cur++;
    seg[i] = node(v);
    return i;
}
int upd(int i, int l, int r, int x, int v) {
    if (l == r) {
        return newleaf(seg[i].v + v);
    }
    if (x <= md) {
        return newpar(upd(seg[i].l, l, md, x, v), seg[i].r);
    } else {
        return newpar(seg[i].l, upd(seg[i].r, md + 1, r, x, v));
    }
}
int get(int rootl, int rootr, int l, int r, int k) {
    if (k <= l) {
        return seg[rootr].v - seg[rootl].v;
    }
    if (r < k) {
        return 0;
    }
    return get(seg[rootl].l, seg[rootr].l, l, md, k) + get(seg[rootl].r, seg[rootr].r, md + 1, r, k);
}
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    int a[n + 1], roots[n + 1];
    roots[0] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        roots[i] = upd(roots[i - 1], 0, 200'000, a[i], 1);
    }
    while (q--) {
        int s, e;
        cin >> s >> e;
        //0001111
        int l = 0, r = e - s + 1;
        while (l <= r) {
            int h = ((l + r) >> 1);
            if (get(roots[s - 1], roots[e], 0, 200'000, h) >= h) {
                l = md + 1;
            } else {
                r = md - 1;
            }
        }
        cout << r << '\n';
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47452 KB Output is correct
2 Correct 12 ms 47428 KB Output is correct
3 Correct 11 ms 47196 KB Output is correct
4 Correct 11 ms 47224 KB Output is correct
5 Correct 12 ms 47452 KB Output is correct
6 Correct 11 ms 47196 KB Output is correct
7 Correct 11 ms 47196 KB Output is correct
8 Correct 11 ms 47196 KB Output is correct
9 Correct 10 ms 47196 KB Output is correct
10 Correct 11 ms 47196 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47452 KB Output is correct
2 Correct 12 ms 47428 KB Output is correct
3 Correct 11 ms 47196 KB Output is correct
4 Correct 11 ms 47224 KB Output is correct
5 Correct 12 ms 47452 KB Output is correct
6 Correct 11 ms 47196 KB Output is correct
7 Correct 11 ms 47196 KB Output is correct
8 Correct 11 ms 47196 KB Output is correct
9 Correct 10 ms 47196 KB Output is correct
10 Correct 11 ms 47196 KB Output is correct
11 Correct 135 ms 49224 KB Output is correct
12 Correct 131 ms 48760 KB Output is correct
13 Correct 128 ms 48724 KB Output is correct
14 Correct 133 ms 48956 KB Output is correct
15 Correct 143 ms 48684 KB Output is correct
16 Correct 137 ms 48724 KB Output is correct
17 Correct 136 ms 48724 KB Output is correct
18 Correct 156 ms 48724 KB Output is correct
19 Correct 132 ms 48796 KB Output is correct
20 Correct 130 ms 48848 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47452 KB Output is correct
2 Correct 12 ms 47428 KB Output is correct
3 Correct 11 ms 47196 KB Output is correct
4 Correct 11 ms 47224 KB Output is correct
5 Correct 12 ms 47452 KB Output is correct
6 Correct 11 ms 47196 KB Output is correct
7 Correct 11 ms 47196 KB Output is correct
8 Correct 11 ms 47196 KB Output is correct
9 Correct 10 ms 47196 KB Output is correct
10 Correct 11 ms 47196 KB Output is correct
11 Correct 135 ms 49224 KB Output is correct
12 Correct 131 ms 48760 KB Output is correct
13 Correct 128 ms 48724 KB Output is correct
14 Correct 133 ms 48956 KB Output is correct
15 Correct 143 ms 48684 KB Output is correct
16 Correct 137 ms 48724 KB Output is correct
17 Correct 136 ms 48724 KB Output is correct
18 Correct 156 ms 48724 KB Output is correct
19 Correct 132 ms 48796 KB Output is correct
20 Correct 130 ms 48848 KB Output is correct
21 Correct 732 ms 53964 KB Output is correct
22 Correct 753 ms 53864 KB Output is correct
23 Correct 728 ms 53672 KB Output is correct
24 Correct 688 ms 53704 KB Output is correct
25 Correct 719 ms 54020 KB Output is correct
26 Correct 656 ms 53840 KB Output is correct
27 Correct 737 ms 53812 KB Output is correct
28 Correct 700 ms 53644 KB Output is correct
29 Correct 753 ms 53700 KB Output is correct
30 Correct 787 ms 53784 KB Output is correct