Submission #1221792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221792		erering	Index (COCI21_index)	C++20	110 / 110	1290 ms	140100 KiB

index

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define endl '\n'
const int N=2e5+5,MOD=1e9+7,inf=1e18;
struct node{
    int sum=0;
    node *l,*r;
};
int a[N];
node *root[N];
void build(node* cur,int lo,int hi){
    if(lo==hi)return;
    cur->l=new node;
    cur->r=new node;
    int mid=(lo+hi)/2;
    build(cur->l,lo,mid);
    build(cur->r,mid+1,hi);
}
node *update(node *cur,int idx,int lo,int hi){
    if(lo==idx && hi==idx){
        node *x=new node;
        x->sum=cur->sum+1;
        return x;
    }
    if(lo>idx || hi<idx)return cur;
    int mid=(lo+hi)/2;
    node *x=new node;
    x->l=update(cur->l,idx,lo,mid);
    x->r=update(cur->r,idx,mid+1,hi);
    x->sum=x->l->sum+x->r->sum;
    return x;
}
int query(node* cur,int qlo,int qhi,int lo,int hi){
    if(lo>qhi || hi<qlo || cur==0)return 0;
    if(lo>=qlo && hi<=qhi)return cur->sum;
    int mid=(lo+hi)/2;
    return query(cur->l,qlo,qhi,lo,mid)+query(cur->r,qlo,qhi,mid+1,hi);
}
signed main(){
   // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,q,offset=(1<<18); cin>>n>>q;
    root[0]=new node;
    build(root[0],0,offset);
    for(int i=0;i<n;i++){
        cin>>a[i];
        root[i+1]=update(root[i],a[i],0,offset);
    }
    while(q--){
        int l,r; cin>>l>>r;
        int lo=1,hi=2e5;
        while(lo<hi){
            int mid=(lo+hi+1)/2;
            int val=query(root[r],mid,offset,0,offset)-query(root[l-1],mid,offset,0,offset);
            if(val>=mid)lo=mid;
            else hi=mid-1;
        }
        cout<<lo<<endl;
    }
}

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