Submission #486462

#	Time	Username	Problem	Language	Result	Execution time	Memory
486462		davi_bart	Index (COCI21_index)	C++14	60 / 110	2591 ms	51092 KiB

index

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fi first
#define se second
#define ld long double
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct segment {
    const int dim = 1 << 18;
    struct node {
        vector<int> v;
    };
    vector<node> s = vector<node>(2 * dim);
    void upd(int pos, int l, int r, int p, int val) {
        if (p < l || r < p) return;
        s[pos].v.pb(val);
        if (l == r) return;
        int m = (l + r) / 2;
        upd(2 * pos, l, m, p, val);
        upd(2 * pos + 1, m + 1, r, p, val);
    }
    void upd(int p, int val) {
        upd(1, 0, dim - 1, p, val);
    }
    void init() {
        for (auto &k : s) {
            sort(k.v.begin(), k.v.end());
        }
    }
    vector<int> nodes;
    void query(int pos, int l, int r, int a, int b) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            nodes.pb(pos);
            return;
        }
        int m = (l + r) / 2;
        query(2 * pos, l, m, a, b);
        query(2 * pos + 1, m + 1, r, a, b);
    }
    int query(int a, int b) {
        nodes.clear();
        query(1, 0, dim - 1, a, b);
        // cout << "k: ";
        // for (int x : nodes) {
        //     for (int y : s[x].v) cout << y << " ";
        //     cout << endl;
        // }
        // cout << endl;
        int l = 1, r = b - a + 1;
        while (l < r - 1) {
            int m = (l + r) / 2;

            int tot = 0;
            for (int i : nodes) {
                tot += s[i].v.size() - (lower_bound(s[i].v.begin(), s[i].v.end(), m) - s[i].v.begin());
            }
            if (tot >= m)
                l = m;
            else
                r = m;
        }
        return l;
    }
} seg;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, Q;
    cin >> N >> Q;
    for (int i = 0; i < N; i++) {
        int u;
        cin >> u;
        seg.upd(i, u);
    }
    seg.init();
    for (int i = 0; i < Q; i++) {
        int a, b;
        cin >> a >> b;
        cout << seg.query(a - 1, b - 1) << '\n';
    }
}

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