Submission #1190806

#TimeUsernameProblemLanguageResultExecution timeMemory
1190806dzuizzIndex (COCI21_index)C++20
0 / 110
14 ms320 KiB
#include<bits/stdc++.h> using namespace std; #define int long long constexpr int N=200005,s=500; int fw[N],p[N]; int n,q,maxp; pair<pair<int,int>,int> qry[N]; 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; }); int l=0,r=-1; int ans[q]; for(auto&qr:qry){ auto [nl,nr]=qr.first; 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); int lf=1,rg=maxp; while(lf<rg){ int mid=(lf+rg+1)>>1; if(sum(mid,maxp)>=mid) lf=mid; else rg=mid-1; } ans[qr.second]=lf; /*cout<<">> "<<qr.second<<'\n'; for(int i=1;i<=7;++i)cout<<sum(i,i)<<" "; cout<<'\n';*/ } for(auto&x:ans)cout<<x<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...