#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N=200005,Q=200005,S=447;
int n,q,P[N],maxp=0;
pair<pair<int,int>,int> qry[Q];
int fw[N],l=0,r=-1,lf,rg,v[Q];
int sum(int idx){
int ret=0;
for(;idx>0;idx-=idx&-idx) ret+=fw[idx];
return ret;
}
int sum(int l,int r){ return sum(r)-sum(l-1); }
void add(int idx,int v){ for(;idx<=maxp;idx+=idx&-idx) fw[idx]+=v; }
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>q;
for(int i=0;i<n;++i) cin>>P[i],maxp=max(maxp,P[i]);
for(int i=0;i<q;++i){
cin>>qry[i].first.first>>qry[i].first.second;
--qry[i].first.first,--qry[i].first.second,qry[i].second=i;
}
sort(qry,qry+q,[&](const pair<pair<int,int>,int>&a,const pair<pair<int,int>,int>&b){
return a.first.first/S==b.first.first/S?(a.first.first/S)&1?a.first.second>b.first.second:a.first.second<b.first.second:a.first.first<b.first.first;
});
for(auto&[lr,i]:qry){
auto&[nl,nr]=lr;
while(l>nl) add(P[--l],1);
while(r<nr) add(P[++r],1);
while(l<nl) add(P[l++],-1);
while(r>nr) add(P[r--],-1);
lf=1,rg=maxp;
while(lf<rg){
int mid=(lf+rg+1)>>1;
if(sum(mid,maxp)>=mid) lf=mid;
else rg=mid-1;
}
v[i]=lf;
}
for(int i=0;i<q;++i)
cout<<v[i]<<'\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |