Submission #1291038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291038		bira	Index (COCI21_index)	C++20	110 / 110	505 ms	50560 KiB

index

#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'

typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

const int MAX = 200'000;

struct Node{
    int seg;
    int L, R;
    Node (){
        seg = 0;
        L = 0;
        R = 0;
    }
};

vector<Node> S = {Node()};
int n;

//pos[x]++ na subarvore p de range [l,r]
int update(int p, int x){
    int l = 1, r = MAX;
    int root = S.size();
    while(true){
        S.push_back(S[p]);
        p = S.size()-1;
        S[p].seg++;
        if(l == r)break;
        int m = (l+r)/2;
        if(x <= m){
            tie(p,S[p].L) = make_tuple(S[p].L,S.size());
            r = m;
        }
        else{
            tie(p,S[p].R) = make_tuple(S[p].R,S.size());
            l = m+1;
        }
    }
    return root;
}

int bs(int pl, int pr){
    int l = 1, r = MAX;
    int cur = 0;
    while(l!=r){
        int m = (l+r)/2;
        int val = S[S[pr].R].seg-S[S[pl].R].seg;
        if(val+cur < m+1){
            cur += val;
            r = m;
            pl = S[pl].L;
            pr = S[pr].L;
        }else{
            l = m+1;
            pl = S[pl].R;
            pr = S[pr].R;
        }
    }
    return r;
}

int main() { //_
    int n,q;
    cin >> n >> q;
    vector<int> rts(n+1);
    for(int i = 1; i <= n; i++){
        int p;
        cin >> p;
        rts[i] = update(rts[i-1],p);
    }
    while(q--){
        int l,r;
        cin >> l >> r;
        cout << bs(rts[l-1],rts[r]) << '\n';
    }
}

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