Submission #494337

#	Time	Username	Problem	Language	Result	Execution time	Memory
494337		AlperenT	Index (COCI21_index)	C++17	60 / 110	2583 ms	47620 KiB

index

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, q, arr[N], a, b, l, r, m;

struct SegTree{
    vector<int> tree[N * 4];

    void build(int v = 1, int l = 1, int r = n){
        if(l == r) tree[v].push_back(arr[l]);
        else{
            int m = l + (r - l) / 2;

            build(v * 2, l, m); build(v * 2 + 1, m + 1, r);

            tree[v].assign(tree[v * 2].size() + tree[v * 2 + 1].size(), 0);

            merge(tree[v * 2].begin(), tree[v * 2].end(), tree[v * 2 + 1].begin(), tree[v * 2 + 1].end(), tree[v].begin());
        }
    }

    int query(int l, int r, int val, int v = 1, int tl = 1, int tr = n){
        if(l > r) return 0;
        else if(tl == l && tr == r) return tree[v].end() - lower_bound(tree[v].begin(), tree[v].end(), val);
        else{
            int tm = tl + (tr - tl) / 2;

            return query(l, min(tm, r), val, v * 2, tl, tm) + query(max(tm + 1, l), r, val, v * 2 + 1, tm + 1, tr);
        }
    }
};

SegTree sgt;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n >> q;

    for(int i = 1; i <= n; i++) cin >> arr[i];

    sgt.build();

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

        l = 1, r = (b - a + 1) + 1;

        while(r - l > 1){
            m = l + (r - l) / 2;

            if(sgt.query(a, b, m) >= m) l = m;
            else r = m;
        }

        cout << l << "\n";
    }
}

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