Submission #1279015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279015		MvKaio	Index (COCI21_index)	C++20	110 / 110	298 ms	101960 KiB

index

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

#define int ll
#define fast_io cin.tie(0)->sync_with_stdio(0);
#define endl '\n'
typedef long long ll;

namespace perseg {
    const int MAX = 2e6 + 10;
    int n, seg[20 * MAX], l[20 * MAX], r[20 * MAX], at = 1, root;
    int node(int cp=0) {
        seg[at] = seg[cp], l[at] = l[cp], r[at] = r[cp];
        return at++;
    }
    void build(int x, int lx, int rx) {
        if (lx + 1 == rx) return;
        int mid = (lx + rx) / 2;
        build(l[x] = node(), lx, mid);
        build(r[x] = node(), mid, rx);
    }
    void build(int _n) {
        n = _n;
        build(root = node(), 0, n);
    }
    void update(int i, int v, int x, int lx, int rx) {
        if (lx + 1 == rx) {
            seg[x] += v;
            return;
        }
        int mid = (lx + rx) / 2;
        if (i < mid) update(i, v, l[x] = node(l[x]), lx, mid);
        else update(i, v, r[x] = node(r[x]), mid, rx);
        seg[x] = seg[l[x]] + seg[r[x]];
    }
    int update(int i, int v) {
        update(i, v, root = node(root), 0, n);
        return root;
    }
    int solve(int r1, int r2, int cur=0, int lx=0, int rx=n) {
        if (lx + 1 == rx) return lx;
        int mid = (lx + rx) / 2;
        int cntr = seg[r[r2]] - seg[r[r1]];
        if (cur + cntr < mid) return solve(l[r1], l[r2], cur+cntr, lx, mid);
        else return solve(r[r1], r[r2], cur, mid, rx);
    }
}

int32_t main() {
    fast_io;

    int n, q; cin >> n >> q;
    vector<int> a(n);
    for (auto &x : a) cin >> x;

    vector<int> roots(n + 1);
    const int MAX = *max_element(a.begin(), a.end());
    perseg::build(MAX + 1);
    roots[0] = perseg::root;
    for (int i = 0; i < n; i++) roots[i + 1] = perseg::update(a[i], 1);

    while (q--) {
        int l, r; cin >> l >> r;
        cout << perseg::solve(roots[l - 1], roots[r]) << endl;
    }
}

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