Submission #1293187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293187		souzamarcos	Index (COCI21_index)	C++20	110 / 110	819 ms	48440 KiB

index

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

const int MAXN = 300000;
const int MAXP = 300000;       
const int MAXNODES = 7000000;

int L[MAXNODES], R[MAXNODES], val[MAXNODES];
int sz = 0;
int root[MAXN + 5];

int new_node(){
    ++sz;
    L[sz] = R[sz] = val[sz] = 0;
    return sz;
}
int update(int prev, int l, int r, int pos){
    int cur = new_node();
    L[cur] = L[prev];
    R[cur] = R[prev];
    val[cur] = val[prev] + 1;
    if(l == r) return cur;
    int mid = (l + r) >> 1;
    if(pos <= mid) L[cur] = update(L[prev], l, mid, pos);
    else R[cur] = update(R[prev], mid+1, r, pos);
    return cur;
}

int query(int u, int v, int l, int r, int ql, int qr){
    if(ql > r || qr < l) return 0;
    if(ql <= l && r <= qr) return val[u] - val[v];
    int mid = (l + r) >> 1;
    return query(L[u], L[v], l, mid, ql, qr) + query(R[u], R[v], mid+1, r, ql, qr);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    if(!(cin >> n >> q)) return 0;
    vector<int> p(n+1);
    for(int i=1;i<=n;i++) cin >> p[i];

    sz = 0;
    new_node();
    root[0] = 0;

    for(int i=1;i<=n;i++){
        root[i] = update(root[i-1], 1, MAXP, p[i]);
    }

    while(q--){
        int l, r;
        cin >> l >> r;
        int len = r - l + 1;
        int lo = 1, hi = min(len, MAXP), ans = 0;
        while(lo <= hi){
            int mid = (lo + hi) >> 1;
            int cnt = 0;
            if(mid <= MAXP) cnt = query(root[r], root[l-1], 1, MAXP, mid, MAXP);
            if(cnt >= mid){
                ans = mid;
                lo = mid + 1;
            } else hi = mid - 1;
        }
        cout << ans << '\n';
    }
    return 0;
}

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