Submission #918794

#TimeUsernameProblemLanguageResultExecution timeMemory
918794JakobZorzAbracadabra (CEOI22_abracadabra)C++17
100 / 100
507 ms49488 KiB
#include<iostream> #include<vector> #include<queue> #include<stack> #include<algorithm> #include<limits.h> #include<math.h> #include<map> #include<set> #include<unordered_map> #include<unordered_set> #include<iomanip> #include<cstring> typedef long long ll; typedef unsigned long long ull; typedef long double ld; using namespace std; const int TREE_SIZE=1<<18; int n; int l[200001]; int r[200001]; int tree[2*TREE_SIZE]; vector<int>init; void update(int i,int val){ i+=TREE_SIZE; tree[i]=val; i/=2; while(i){ tree[i]=tree[2*i]+tree[2*i+1]; i/=2; } } pair<int,int>get(int node,int rl,int rr,int sum){ if(tree[node]<=sum) return{rr,tree[node]}; if(rl==rr-1) return{rl,0}; int mid=(rl+rr)/2; if(sum<tree[2*node]) return get(2*node,rl,mid,sum); else{ auto res=get(2*node+1,mid,rr,sum-tree[2*node]); res.second+=tree[2*node]; return res; } } void insert(int a,int b){ l[init[a]]=a; r[init[a]]=b; update(init[a],b-a); } pair<int,int>get(int sum){ auto res=get(1,0,TREE_SIZE,sum); return{res.first,sum-res.second}; } void solve(){ int q; cin>>n>>q; init.resize(n); vector<int>nxt(n); for(int&i:init) cin>>i; stack<pair<int,int>>st; st.push({n+1,n}); for(int i=n-1;i>=0;i--){ while(st.top().first<init[i]) st.pop(); nxt[i]=st.top().second; st.push({init[i],i}); } vector<vector<pair<int,int>>>qrs(n+1); vector<int>ans(q,-1); for(int i=0;i<q;i++){ int t,qi; cin>>t>>qi; t=min(t,n); qrs[t].push_back({qi-1,i}); } for(int curr=0;curr<n;){ insert(curr,nxt[curr]); curr=nxt[curr]; } for(int round=0;round<=n;round++){ for(auto i:qrs[round]){ auto res=get(i.first); ans[i.second]=init[l[res.first]+res.second]; } auto res=get(n/2); if(res.second==0) continue; int nl=l[res.first]+res.second; int nr=r[res.first]; insert(l[res.first],nl); for(int curr=nl;curr<nr;){ int nx=min(nxt[curr],nr); insert(curr,nx); curr=nx; } } for(int i:ans){ if(i==-1) abort(); cout<<i<<"\n"; } } int main(){ ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL); //freopen("input.in","r",stdin);freopen("output.out","w",stdout); int t=1;//cin>>t; while(t--)solve(); return 0; } /* 6 3 1 5 6 2 3 4 1 2 0 4 1 5 2 2 5 6 6 2 1 5 4 6 3 0 1 1 1 0 3 1 3 0 6 10 6 2 2 5 4 3 3 10 10 7 5 2 9 10 8 4 3 6 1 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 2 3 6 1 7 5 8 4 9 10 10 10 5 4 3 10 9 8 7 6 2 1 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 1 2 5 4 3 6 8 7 10 9 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...