Submission #519885

#	Time	Username	Problem	Language	Result	Execution time	Memory
519885		Vianti	Index (COCI21_index)	C++17	110 / 110	1978 ms	91596 KiB

index

#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 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50