oj.uz

Submission #519885

# Submission time Handle Problem Language Result Execution time Memory
519885 2022-01-27T14:05:04 Z Vianti Index (COCI21_index) C++17
110 / 110
 1978 ms 91596 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const ll mod = 1e9 + 7;
const int maxP = 200000;
int cnt = 0;

struct Node {
    int l, r;
    int sum;

    Node(int left, int right, int v) : l(left), r(right), sum(v) {};

    Node() : l(0), r(0), sum(0) {};
};

Node nnode[36 * maxP];

struct SegTree {
    int sz = 0;

    int createTree(int l, int r) {
        if (l == r) {
            return cnt++;
        }
        int m = (l + r) >> 1;
        int nd1 = createTree(l, m);
        int nd2 = createTree(m + 1, r);
        nnode[cnt].l = nd1;
        nnode[cnt].r = nd2;
        nnode[cnt].sum = 0;
        return cnt++;
    }

    int build(int n) {
        sz = 1;
        while (sz < n)sz <<= 1;
        return createTree(0, sz - 1);
    }

    int add(int v, int tl, int tr, int pos, int val) {
        if (tl == tr) {
            nnode[cnt].sum = val + nnode[v].sum;
            return cnt++;
        }
        int tm = (tl + tr) >> 1;
        if (pos <= tm) {
            int nd = add(nnode[v].l, tl, tm, pos, val);
            nnode[cnt].l = nd;
            nnode[cnt].r = nnode[v].r;
            nnode[cnt].sum = nnode[nd].sum + nnode[nnode[v].r].sum;
            return cnt++;
        } else {
            int nd = add(nnode[v].r, tm + 1, tr, pos, val);
            nnode[cnt].l = nnode[v].l;
            nnode[cnt].r = nd;
            nnode[cnt].sum = nnode[nd].sum + nnode[nnode[v].l].sum;
            return cnt++;
        }
    }

    int add(int root, int pos, int val) {
        return add(root, 0, sz - 1, pos, val);
    }

    int getSum(int v, int tl, int tr, int l, int r) const {
        if (tl > tr)return 0;
        if (tl > r || tr < l)return 0;
        if (tl >= l && tr <= r)return nnode[v].sum;
        int tm = (tl + tr) >> 1;
        return getSum(nnode[v].l, tl, tm, l, r) + getSum(nnode[v].r, tm + 1, tr, l, r);
    }

    int getSum(int root, int l, int r) const {
        return getSum(root, 0, sz - 1, l, r);
    }
};


int query(int x, int l, int r, const vector<int>& roots, const SegTree& tree) {
    if (l == 0)return tree.getSum(roots[r], x, maxP - 1);
    else return tree.getSum(roots[r], x, maxP - 1) - tree.getSum(roots[l - 1], x, maxP - 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    SegTree tree;
    int root = tree.build(maxP);
    vector<int> roots(n);
    roots[0] = tree.add(root, a[0] - 1, 1);
    for (int i = 1; i < n; i++) {
        roots[i] = tree.add(roots[i - 1], a[i] - 1, 1);
    }
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        int left = 1;
        int right = r - l + 2;
        while (right - left > 1) {
            int x = (right + left) >> 1;
            if (query(x - 1, l, r, roots, tree) >= x) {
                left = x;
            } else {
                right = x;
            }
        }
        cout << left << '\n';
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 84812 KB Output is correct
2 Correct 45 ms 84748 KB Output is correct
3 Correct 42 ms 84844 KB Output is correct
4 Correct 42 ms 84800 KB Output is correct
5 Correct 41 ms 84848 KB Output is correct
6 Correct 42 ms 84832 KB Output is correct
7 Correct 42 ms 84744 KB Output is correct
8 Correct 41 ms 84808 KB Output is correct
9 Correct 48 ms 84760 KB Output is correct
10 Correct 47 ms 84744 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 84812 KB Output is correct
2 Correct 45 ms 84748 KB Output is correct
3 Correct 42 ms 84844 KB Output is correct
4 Correct 42 ms 84800 KB Output is correct
5 Correct 41 ms 84848 KB Output is correct
6 Correct 42 ms 84832 KB Output is correct
7 Correct 42 ms 84744 KB Output is correct
8 Correct 41 ms 84808 KB Output is correct
9 Correct 48 ms 84760 KB Output is correct
10 Correct 47 ms 84744 KB Output is correct
11 Correct 332 ms 85492 KB Output is correct
12 Correct 344 ms 85528 KB Output is correct
13 Correct 331 ms 85448 KB Output is correct
14 Correct 340 ms 85640 KB Output is correct
15 Correct 342 ms 85500 KB Output is correct
16 Correct 331 ms 85452 KB Output is correct
17 Correct 344 ms 85612 KB Output is correct
18 Correct 334 ms 85508 KB Output is correct
19 Correct 348 ms 85520 KB Output is correct
20 Correct 334 ms 85536 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 84812 KB Output is correct
2 Correct 45 ms 84748 KB Output is correct
3 Correct 42 ms 84844 KB Output is correct
4 Correct 42 ms 84800 KB Output is correct
5 Correct 41 ms 84848 KB Output is correct
6 Correct 42 ms 84832 KB Output is correct
7 Correct 42 ms 84744 KB Output is correct
8 Correct 41 ms 84808 KB Output is correct
9 Correct 48 ms 84760 KB Output is correct
10 Correct 47 ms 84744 KB Output is correct
11 Correct 332 ms 85492 KB Output is correct
12 Correct 344 ms 85528 KB Output is correct
13 Correct 331 ms 85448 KB Output is correct
14 Correct 340 ms 85640 KB Output is correct
15 Correct 342 ms 85500 KB Output is correct
16 Correct 331 ms 85452 KB Output is correct
17 Correct 344 ms 85612 KB Output is correct
18 Correct 334 ms 85508 KB Output is correct
19 Correct 348 ms 85520 KB Output is correct
20 Correct 334 ms 85536 KB Output is correct
21 Correct 1978 ms 87596 KB Output is correct
22 Correct 1894 ms 91360 KB Output is correct
23 Correct 1933 ms 91252 KB Output is correct
24 Correct 1924 ms 91240 KB Output is correct
25 Correct 1895 ms 91416 KB Output is correct
26 Correct 1949 ms 91352 KB Output is correct
27 Correct 1947 ms 91596 KB Output is correct
28 Correct 1890 ms 91236 KB Output is correct
29 Correct 1893 ms 91216 KB Output is correct
30 Correct 1893 ms 91296 KB Output is correct