Submission #519883

#	Time	Username	Problem	Language	Result	Execution time	Memory
519883		Vianti	Index (COCI21_index)	C++17	60 / 110	2561 ms	142888 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;

struct Node {
    Node* l, * r;
    int sum;

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

    Node() {
        l = nullptr;
        r = nullptr;
        sum = 0;
    }
};

struct SegTree {
    int sz = 0;

    Node* createTree(int l, int r) {
        if (l == r) {
            Node* res = new Node(nullptr, nullptr, 0);
            return res;
        }
        int m = (l + r) >> 1;
        Node* nd1 = createTree(l, m);
        Node* nd2 = createTree(m + 1, r);
        Node* res = new Node(nd1, nd2, 0);
        return res;
    }

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

    Node* add(Node* v, int tl, int tr, int pos, int val) {
        if (tl == tr) {
            Node* nd = new Node(nullptr, nullptr, val + v->sum);
            return nd;
        }
        int tm = (tl + tr) >> 1;
        if (pos <= tm) {
            Node* nd = add(v->l, tl, tm, pos, val);
            Node* res = new Node(nd, v->r, nd->sum + v->r->sum);
            return res;
        } else {
            Node* nd = add(v->r, tm + 1, tr, pos, val);
            Node* res = new Node(v->l, nd, v->l->sum + nd->sum);
            return res;
        }
    }

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

    int getSum(Node* 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 v->sum;
        int tm = (tl + tr) >> 1;
        return getSum(v->l, tl, tm, l, r) + getSum(v->r, tm + 1, tr, l, r);
    }

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

const int maxP = 200000;

int query(int x, int l, int r, const vector<Node*>& 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(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    SegTree tree;
    Node* root = tree.build(maxP);
    vector<Node*> 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: 0 / 50