Submission #797622

#TimeUsernameProblemLanguageResultExecution timeMemory
797622FEDIKUSAbracadabra (CEOI22_abracadabra)C++17
0 / 100
106 ms16840 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define xx first #define yy second #define ff(i,s,f) for(int i=s;i<f;i++) #define fb(i,s,f) for(int i=(s)-1;i>=f;i--) #define ffi(i,s,f) for(int i=s;i<=f;i++) #define fbi(i,s,f) for(int i=s;i>=f;i--) #define srt(a) sort(a.begin(),a.end()); #define srtg(a,int) sort(a.begin(),a.end(),greater<int>()) #define lb(a,x) lower_bound(a.begin(),a.end(),x) #define ub(a,x) upper_bound(a.begin(),a.end(),x) #define fnd(a,x) find(a.begin(),a.end(),x) #define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef string str; using ti = tuple<int,int,int>; const int maxn=2e5+10; int n,q; int a[maxn]; int inv[maxn]; int veci[maxn]; int segt[4*maxn]; ti upit[maxn]; int res[maxn]; void update(int t,int v,int ind=1,int l=1,int r=n){ if(l==r){ segt[ind]=v; return; } int mid=l+(r-l)/2; if(t<=mid) update(t,v,2*ind,l,mid); else update(t,v,2*ind+1,mid+1,r); segt[ind]=segt[2*ind]+segt[2*ind+1]; } int qry(int tl,int tr,int ind=1,int l=1,int r=n){ if(tl>tr) return 0; if(tl<=l && r<=tr) return segt[ind]; int mid=l+(r-l)/2; int ret=0; if(tl<=mid) ret+=qry(tl,tr,2*ind,l,mid); if(tr>mid) ret+=qry(tl,tr,2*ind+1,mid+1,r); return ret; } int pronadji(int x){ int l=1,r=n; int ret=-1; while(l<=r){ int mid=l+(r-l)/2; if(qry(1,mid)>=x){ ret=mid; r=mid-1; }else l=mid+1; } return ret; } bool pomeri(){ int lik=pronadji(n/2+1); int kraj=inv[lik]+qry(lik,lik)-1; int prosli=inv[lik]+n/2+1-qry(1,lik-1)-1; if(qry(a[prosli],a[prosli])!=0) return true; update(lik,n/2+1-qry(1,lik-1)-1); int tren=veci[prosli]; while(tren<=kraj){ update(a[prosli],tren-prosli); prosli=tren; tren=veci[tren]; } update(a[prosli],kraj+1-prosli); return false; } void solve(){ cin>>n>>q; for(int i=1;i<=n;i++){ cin>>a[i]; inv[a[i]]=i; } for(int i=1;i<=q;i++){ int t,ind; cin>>t>>ind; upit[i]={t,ind,i}; } sort(upit+1,upit+q+1); stack<int> stek; for(int i=n;i>0;i--){ while(!stek.empty() && a[stek.top()]<a[i]) stek.pop(); if(stek.empty()) veci[i]=n+1; else veci[i]=stek.top(); stek.push(i); } int tren=1; int prosli=-1; while(tren<=n/2){ if(prosli!=-1){ update(a[prosli],tren-prosli); } prosli=tren; tren=veci[tren]; } update(a[prosli],n/2+1-prosli); tren=n/2+1; prosli=-1; while(tren<=n){ if(prosli!=-1) update(a[prosli],tren-prosli); prosli=tren; tren=veci[tren]; } update(a[prosli],n+1-prosli); int tu=0; while(get<0>(upit[tu])==0){ res[get<2>(upit[tu])]=a[get<1>(upit[tu])]; tu++; } for(int t=1;tu<=q && t<3000;t++){ while(tu<=q && t>=get<0>(upit[tu])){ auto [t,x,ind]=upit[tu]; int gde=pronadji(x); int klk=x-qry(1,gde-1)-1; res[ind]=a[inv[gde]+klk]; tu++; } if(pomeri()) t=maxn; } for(int i=1;i<=q;i++){ cout<<res[i]<<"\n"; } } int main(){ ios; int t=1; //cin>>t; while(t--) solve(); 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...