Submission #992063

#TimeUsernameProblemLanguageResultExecution timeMemory
992063Savu_Stefan_CatalinAbracadabra (CEOI22_abracadabra)C++14
0 / 100
269 ms41504 KiB
#include <iostream> #include <stack> #include <algorithm> using namespace std; const int NMAX=2e5+5,MM=1e6+5; int ar[4*NMAX+505],n,q,val[NMAX+5],a[NMAX+5],inv[NMAX+5],ap[NMAX+5],urm[NMAX+5]; pair<pair<int,int>,int> t[MM]; int ras[MM]; pair<int,int> add(pair<int,int> a,pair<int,int> b) { return {a.first+b.first,a.second+b.second}; } void update(int st,int dr,int nod,int poz,int val) { if (st==dr) { ar[nod]=val; return ; } int mij=(st+dr)/2; if (poz<=mij) update(st,mij,nod*2,poz,val); else update(mij+1,dr,nod*2+1,poz,val); ar[nod]=ar[nod*2]+ar[nod*2+1]; } pair<int,int> query(int st,int dr,int nod,int val) { if (st==dr) { return {st,ar[nod]}; } int mij=(st+dr)/2; if (ar[nod*2]<val) return add(query(mij+1,dr,nod*2+1,val-ar[nod*2]),{0,ar[nod*2]}); else return query(st,mij,nod*2,val); } void operation() { int cen=0; { auto nod=query(1,n,1,n/2+1); int x=n/2+1-(nod.second-val[nod.first]); if (x==1) return ; val[nod.first]=x-1; update(1,n,1,nod.first,val[nod.first]); cen=a[inv[nod.first]+x-1]; } int nod=cen; while (ap[nod]==0) { ap[nod]=1; val[nod]=inv[urm[nod]]-inv[nod]; update(1,n,1,nod,inv[urm[nod]]-inv[nod]); nod=urm[nod]; } } int main() { ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0); cin>>n>>q; for (int i=1;i<=n;++i) { cin>>a[i]; inv[a[i]]=i; } inv[n+1]=n+1; stack <int> s; for (int i=1;i<=n;++i) { while (!s.empty()&&a[s.top()]<a[i]) {urm[a[s.top()]]=a[i]; s.pop();} s.push(i); } while (!s.empty()) {urm[a[s.top()]]=n+1; s.pop();} for (int i=1;i<=q;++i) { cin>>t[i].first.first>>t[i].first.second; t[i].second=i; } sort(t+1,t+q+1); { ap[n+1]=1; int nod=a[1]; while (nod!=n+1) { ap[nod]=1; val[nod]=inv[urm[nod]]-inv[nod]; update(1,n,1,nod,inv[urm[nod]]-inv[nod]); nod=urm[nod]; } } int cat=0; for (int i=1;i<=q;++i) { while (cat<t[i].first.first&&cat<=n+5) {cat++; operation();} { auto nod=query(1,n,1,t[i].first.second); int x=t[i].first.second-(nod.second-val[nod.first]); ras[t[i].second]=a[inv[nod.first]+x-1]; } } for (int i=1;i<=q;++i) cout<<ras[i]<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...