Submission #440099

#	Time	Username	Problem	Language	Result	Execution time	Memory
440099		FatihSolak	Index (COCI21_index)	C++17	60 / 110	2582 ms	133904 KiB

index

#include <bits/stdc++.h>
#define N 200005
using namespace std;
int arr[N];
int cnt[N];
struct Node{
    int sum=0;
    Node *lc=NULL,*rc=NULL;
    Node(int a){
        sum = a;
    }
    Node(Node *a, Node *b){
        if(a != NULL)sum += a->sum;
        if(b != NULL)sum += b->sum;
        lc = a;
        rc = b;
    }
};
Node* build(int l,int r){
    if(l == r){
        return new Node(cnt[l]);
    }
    int m = (l+r)/2;
    return new Node(build(l,m),build(m+1,r));
}
Node* upd(Node* v,int l,int r,int pos,int val){
    if(l == r){
        return new Node(v->sum + val);
    }
    int m = (l+r)/2;
    if(pos <=m){
        return new Node(upd(v->lc,l,m,pos,val),v->rc);
    }
    else return new Node(v->lc,upd(v->rc,m+1,r,pos,val));
}
int get(Node* v,int tl,int tr, int l,int r){
    if(tr <  l || r < tl){
        return 0;
    }
    if(l <= tl && tr <= r){
        return v->sum;
    }
    int tm  = (tl+tr)/2;
    return get(v->lc,tl,tm,l,r) + get(v->rc,tm+1,tr,l,r);
}
void solve(){
    int n,q;
    cin >> n >> q;
    for(int i=0;i<n;i++){
        cin >> arr[i];
        cnt[arr[i]]++;
    }
    vector<Node *> roots;
    roots.push_back(build(1,N-1));
    for(int i=1;i<n;i++){
        roots.push_back(upd(roots[i-1],1,N-1,arr[i-1],-1));
    }
    while(q--){
        int ql,qr;
        cin >> ql >> qr;
        ql--,qr--;
        int l = 1,r = qr-ql+1;
        while(l < r){
            int m = (l+r+1)/2;
            int val = get(roots[ql],1,N-1,m,N-1);
            if(qr +1 != n){
                val -= get(roots[qr + 1],1,N-1,m,N-1);
            }
            if(val >= m){
                l = m;
            }
            else r = m-1;
        }
        cout << l << endl;
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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