Submission #994486

#TimeUsernameProblemLanguageResultExecution timeMemory
994486biankAbracadabra (CEOI22_abracadabra)C++14
0 / 100
750 ms33464 KiB
#include <bits/stdc++.h> using namespace std; #define sz(x) int(x.size()) #define all(x) begin(x),end(x) #define forsn(i,s,n) for(int i=int(s);i<int(n);i++) #define forn(i,n) for(int i=0;i<int(n);i++) #define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--) #define dforn(i,n) for(int i=int(n)-1;i>=0;i--) //#define dbg(x) cerr<<#x<<": "<<x<<endl #define pb push_back typedef vector<int> vi; typedef vector<pair<int,int>> vii; struct Node{ int val; int maxi; int sz; int p; Node* l; Node* r; Node(int v){ val=maxi=v,sz=1; p=rand(); l=r=nullptr; } }; int max(Node* u){ if(!u)return 0; return u->maxi; } int size(Node* u){ if(!u)return 0; return u->sz; } void evaluate(Node* u){ if(u){ u->maxi=max({u->val,max(u->l),max(u->r)}); u->sz=1+size(u->l)+size(u->r); } } pair<Node*,Node*> splitk(Node* u, int k){ if(!u) return {nullptr, nullptr}; if(k>=size(u->l)+1){ auto[l,r]=splitk(u->r,k-size(u->l)-1); u->r=l; evaluate(u); return {u,r}; }else{ auto[l,r]=splitk(u->l,k); u->l=r; evaluate(u); return {l,u}; } } Node* merge(Node* l, Node* r){ if(!l) return r; if(!r) return l; if(l->p>r->p){ l->r=merge(l->r,r); evaluate(l); return l; }else{ r->l=merge(l,r->l); evaluate(r); return r; } } void heapify(Node *u){ if(!u)return; Node* maxP=u; if(u->l&&u->l->p>maxP->p) maxP=u->l; if(u->r&&u->r->p>maxP->p) maxP=u->r; if(maxP!=u){ swap(maxP->p,u->p); heapify(maxP); } } Node* build(vi &v, int l, int r){ if(l>r) return nullptr; int m=(l+r)/2; Node* u=new Node(v[m]); u->l=build(v,l,m-1); u->r=build(v,m+1,r); evaluate(u); return u; } void dfs(Node* u){ if(!u) return; dfs(u->l); cerr<<u->val<<' '; dfs(u->r); } pair<Node*,Node*> splitv(Node* u, int v){ if(!u) return {nullptr, nullptr}; if(max(max(u->l),u->val)<=v){ auto[l,r]=splitv(u->r,v); u->r=l; evaluate(u); return {u,r}; }else{ auto[l,r]=splitv(u->l,v); u->l=r; evaluate(u); return {l,u}; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(0)); int n,q; cin>>n>>q; vi v(n); forn(i,n) cin>>v[i]; Node* root=build(v,0,n-1); heapify(root); vector<vii> queries(n+1); forn(idx,q){ int t,i; cin>>t>>i; t=min(t,n),--i; queries[t].pb({i,idx}); } vi res(q); #define dbg(x) dfs(x); cerr<<'\n' forn(i,n+1){ for(auto[p,idx]:queries[i]){ Node *l,*m,*r; tie(l,r)=splitk(root,p); tie(m,r)=splitk(r,1); res[idx]=m->val; root=merge(merge(l,m),r); } Node *l, *m1, *m2, *r; tie(l,r)=splitk(root,n/2); int val=max(l); //dbg(l); //dbg(r); tie(m2,r)=splitv(r,val); //dbg(m2); val=max(m2); tie(l,m1)=splitv(l,val); //dbg(m1); root=merge(merge(l,m2),merge(m1,r)); } forn(i,q) cout<<res[i]<<'\n'; return 0; }

Compilation message (stderr)

Main.cpp: In function 'std::pair<Node*, Node*> splitk(Node*, int)':
Main.cpp:52:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |         auto[l,r]=splitk(u->r,k-size(u->l)-1);
      |             ^
Main.cpp:57:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         auto[l,r]=splitk(u->l,k);
      |             ^
Main.cpp: In function 'std::pair<Node*, Node*> splitv(Node*, int)':
Main.cpp:109:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |         auto[l,r]=splitv(u->r,v);
      |             ^
Main.cpp:114:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |         auto[l,r]=splitv(u->l,v);
      |             ^
Main.cpp: In function 'int main()':
Main.cpp:141:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  141 |         for(auto[p,idx]:queries[i]){
      |                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...