Submission #751305

#TimeUsernameProblemLanguageResultExecution timeMemory
751305sofija6Index (COCI21_index)C++14
60 / 110
2542 ms100896 KiB
#include <bits/stdc++.h> #define ll long long #define MAXN 200010 #define MAXV 5000010 using namespace std; ll p[MAXN],root[MAXV],l[MAXV],r[MAXV],val[MAXV],ind=1; void Init(ll node,ll lx,ll rx) { if (lx==rx) return; l[node]=ind++; r[node]=ind++; ll mid=(lx+rx)/2; Init(l[node],lx,mid); Init(r[node],mid+1,rx); } void Update(ll node,ll pnode,ll lx,ll rx,ll pos,ll vall) { if (lx==rx) { val[node]=val[pnode]+vall; return; } ll mid=(lx+rx)/2; if (pos<=mid) { l[node]=ind++; r[node]=r[pnode]; Update(l[node],l[pnode],lx,mid,pos,vall); } else { l[node]=l[pnode]; r[node]=ind++; Update(r[node],r[pnode],mid+1,rx,pos,vall); } val[node]=val[l[node]]+val[r[node]]; } ll Calc(ll node,ll lx,ll rx,ll L,ll R) { if (lx>R || rx<L) return 0; if (lx>=L && rx<=R) return val[node]; ll mid=(lx+rx)/2; return Calc(l[node],lx,mid,L,R)+Calc(r[node],mid+1,rx,L,R); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n,q,L,R; cin >> n >> q; for (ll i=1;i<=n;i++) cin >> p[i]; root[0]=ind++; Init(root[0],1,MAXN); for (ll i=1;i<=n;i++) { root[i]=ind++; Update(root[i],root[i-1],1,MAXN,p[i],1); } while (q--) { cin >> L >> R; ll l=1,r=R-L+1,mid,ans; while (l<=r) { mid=(l+r)/2; if (Calc(root[R],1,MAXN,mid,MAXN)-Calc(root[L-1],1,MAXN,mid,MAXN)>=mid) { ans=mid; l=mid+1; } else r=mid-1; } cout << ans << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...