Submission #887310

#	Time	Username	Problem	Language	Result	Execution time	Memory
887310		MinaRagy06	Index (COCI21_index)	C++17	110 / 110	787 ms	54020 KiB

index

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