Submission #1150257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150257		nikolashami	Index (COCI21_index)	C++20	110 / 110	1175 ms	97244 KiB

index

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

const ll N=2e5,N2=5+24*N;
ll root[N2],lc[N2],rc[N2],st[N2],nd;

void bd(ll lik,ll l=1,ll r=N){
	if(l==r)return;
	lc[lik]=++nd;
	rc[lik]=++nd;
	bd(lc[lik],l,(l+r)/2);
	bd(rc[lik],(l+r)/2+1,r);
}

void upd(ll pr,ll tr,ll id,ll l=1,ll r=N){
	if(l==r){st[tr]=1+st[pr];return;}
	ll md=(l+r)/2;
	if(id<=md){
		rc[tr]=rc[pr];
		lc[tr]=++nd;
		upd(lc[pr],lc[tr],id,l,md);
	}else{
		lc[tr]=lc[pr];
		rc[tr]=++nd;
		upd(rc[pr],rc[tr],id,md+1,r);
	}
	st[tr]=st[lc[tr]]+st[rc[tr]];
}

ll walk(ll pr,ll tr,ll x,ll l=1,ll r=N){
	if(l==r)return l;
	ll md=(l+r)/2;
	ll rgt=st[rc[tr]]-st[rc[pr]];
	if(rgt>=x)return walk(rc[pr],rc[tr],x,md+1,r);
	else return walk(lc[pr],lc[tr],x-rgt,l,md);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    ll n,q;
    cin>>n>>q;

    root[0]=++nd;
    bd(root[0]);

    for(int i=1;i<=n;++i){
    	ll x;cin>>x;
    	root[i]=++nd;
    	upd(root[i-1],root[i],x);
    }

    while(q--){
    	ll l,r;cin>>l>>r;
    	ll L=1,R=N,A=L;
    	while(L<=R){
    		ll M=(L+R)/2;
    		if(walk(root[l-1],root[r],M)>=M){
    			A=M;
    			L=M+1;
    		}else
    			R=M-1;
    	}
    	cout<<A<<'\n';
    }
}

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