Submission #538745

#	Time	Username	Problem	Language	Result	Execution time	Memory
538745		Jomnoi	Index (COCI21_index)	C++17	60 / 110	2577 ms	152096 KiB

index

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int N = 2e5 + 10;

int p[N];
vector <int> idx_paper[N];

class Node {
public :
    int sum;
    Node *l, *r;
    Node(int s) : sum(s), l(NULL), r(NULL) {}
    Node(Node *L, Node *R) : sum(0), l(L), r(R) {
        if(L != NULL) {
            sum += L->sum;
        }
        if(R != NULL) {
            sum += R->sum;
        }
    }
    Node(Node *copy) : sum(copy->sum), l(copy->l), r(copy->r) {}
};
Node *root[N];

Node *build(int l, int r) {
    if(l == r) {
        return new Node(0);
    }

    int mid = (l + r) / 2;
    return new Node(build(l, mid), build(mid + 1, r));
}

Node *update(Node *node, int l, int r, int q) {
    if(l == r) {
        return new Node(1);
    }

    int mid = (l + r) / 2;
    if(q <= mid) {
        return new Node(update(node->l, l, mid, q), node->r);
    }
    return new Node(node->l, update(node->r, mid + 1, r, q));
}

int query(Node *node, int l, int r, int ql, int qr) {
    if(r < ql or qr < l) {
        return 0;
    }
    if(ql <= l and r <= qr) {
        return node->sum;
    }

    int mid = (l + r) / 2;
    return query(node->l, l, mid, ql, qr) + query(node->r, mid + 1, r, ql, qr);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
        idx_paper[p[i]].push_back(i);
    }

    root[n + 1] = build(1, n);
    for(int i = n; i >= 1; i--) {
        root[i] = new Node(root[i + 1]);
        for(auto idx : idx_paper[i]) {
            root[i] = update(root[i], 1, n, idx);
        }
    }

    while(q--) {
        int a, b;
        cin >> a >> b;

        int range = b - a + 1;
        int l = 1, r = range, pos = 1;
        while(l <= r) {
            int mid = (l + r) / 2;

            if(query(root[mid], 1, n, a, b) < mid) {
                r = mid - 1;
            }
            else {
                l = mid + 1;
                pos = mid;
            }
        }
        cout << pos << '\n';
    }
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 0 / 50