Submission #49154

#TimeUsernameProblemLanguageResultExecution timeMemory
49154khohkoCake (CEOI14_cake)C++14
83.33 / 100
2009 ms30844 KiB
#include <bits/stdc++.h> //glhf nikabb u suck #pragma GCC optimize("O3") using namespace std; #define ll int #define lol long long #define pb push_back //#define mp make_pair #define fr first #define sc second #define MAX ((lol)(1e9+100)) #define MX ((lol)(4e9+100)) #define ARRS ((lol)(1e6+100)) #define ARS ((lol)(1e3+100)) #define HS ((lol)(233)) #define MOD ((lol)(1e9+9)) #define EP ((double)(1e-9)) #define EPS ((double)(1e-8)) #define pb push_back #define PI ((double)3.141592653) #define LG 21 using namespace std; struct node{ node *L,*R; ll x; node(){ L=R=NULL; x=-MAX; } void updt(){ x=-MAX; if(L)x=max(x,L->x); if(R)x=max(x,R->x); } }; ll wi,wx,wl,wr; void updt(ll l,ll r,node *& x){ if(wi<l||r-1<wi)return; if(!x)x=new node(); if(l==r-1){ x->x=wx; return; } updt(l,l+r>>1,x->L); updt(l+r>>1,r,x->R); x->updt(); } ll quer(ll l,ll r,node *& x){ if(wr<l||r-1<wl)return -MAX; if(!x)return -MAX; if(wl<=l&&r-1<=wr)return x->x; return max(quer(l,l+r>>1,x->L),quer(l+r>>1,r,x->R)); } ll quer1(ll l,ll r,node *& x){ if(wr<l||r-1<wl)return MAX; if(!x)return MAX; if(wl<=l&&r-1<=wr){ if(x->x<wx)return MAX; if(l==r-1)return l; else if(x->L->x>=wx) return quer1(l,l+r>>1,x->L); else return quer1(l+r>>1,r,x->R); } return min(quer1(l,l+r>>1,x->L),quer1(l+r>>1,r,x->R)); } ll quer2(ll l,ll r,node *& x){ if(wr<l||r-1<wl)return -MAX; if(!x)return -MAX; if(wl<=l&&r-1<=wr){ if(x->x<wx)return -MAX; if(l==r-1)return l; //cout<<l<<" "<<r<<" "<<x->R->x<<" < "<<wx<<endl; if(x->R->x>=wx) return quer2(l+r>>1,r,x->R); else return quer2(l,l+r>>1,x->L); } return max(quer2(l,l+r>>1,x->L),quer2(l+r>>1,r,x->R)); } ll C; node *rt=NULL; set<pair<ll,ll> > st; stack<pair<ll,ll> > sk; ll n,s; ll f[ARRS]; void add(ll i){ wx=++C; f[i]=wx; wi=i; updt(0,n,rt); st.insert({wx,i}); } int main(){ ios::sync_with_stdio(0); cin>>n>>s; n+=2; for(int i=1; i<=n-2; i++){ cin>>wx; wi=i; f[i]=wx; updt(0,n,rt); st.insert({wx,i}); } wi=0; wx=MAX; updt(0,n,rt); wi=n-1; updt(0,n,rt); while(st.size()>10)st.erase(st.begin()); ll qr; char q; C=n+2; cin>>qr; while(qr--){ cin>>q; if(q=='F'){ ll x; cin>>x; if(x==s) cout<<0<<endl; else if(x<s){ wl=x; wr=s-1; wx=quer(0,n,rt); wl=s+1; wr=MAX; ll t=quer1(0,n,rt); //cout<<x<<" -> "<<t<<" "<<wx<<" "<<x<<" "<<s-1<<endl; cout<<t-x-1<<endl; } else { wl=s+1; wr=x; wx=quer(0,n,rt); wl=-MAX; wr=s-1; ll t=quer2(0,n,rt); //cout<<x<<" -> "<<t<<" "<<wx<<" "<<x<<" "<<s-1<<endl; cout<<x-t-1<<endl; } } else { ll i,c; cin>>i>>c; if(st.find({f[i],i})!=st.end()) st.erase({f[i],i}); c--; while(c--){ sk.push((*--st.end())); st.erase(--st.end()); } add(i); while(sk.size()){ auto k=sk.top(); sk.pop(); add(k.sc); } while(st.size()>10)st.erase(st.begin()); } } }

Compilation message (stderr)

cake.cpp: In function 'void updt(int, int, node*&)':
cake.cpp:47:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt(l,l+r>>1,x->L);
         ~^~
cake.cpp:48:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt(l+r>>1,r,x->R);
       ~^~
cake.cpp: In function 'int quer(int, int, node*&)':
cake.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  return max(quer(l,l+r>>1,x->L),quer(l+r>>1,r,x->R));
                    ~^~
cake.cpp:57:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  return max(quer(l,l+r>>1,x->L),quer(l+r>>1,r,x->R));
                                      ~^~
cake.cpp: In function 'int quer1(int, int, node*&)':
cake.cpp:67:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    return quer1(l,l+r>>1,x->L);
                   ~^~
cake.cpp:68:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else return quer1(l+r>>1,r,x->R);
                     ~^~
cake.cpp:70:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  return min(quer1(l,l+r>>1,x->L),quer1(l+r>>1,r,x->R));
                     ~^~
cake.cpp:70:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  return min(quer1(l,l+r>>1,x->L),quer1(l+r>>1,r,x->R));
                                        ~^~
cake.cpp: In function 'int quer2(int, int, node*&)':
cake.cpp:82:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    return quer2(l+r>>1,r,x->R);
                 ~^~
cake.cpp:83:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else return quer2(l,l+r>>1,x->L);
                       ~^~
cake.cpp:85:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  return max(quer2(l,l+r>>1,x->L),quer2(l+r>>1,r,x->R));
                     ~^~
cake.cpp:85:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  return max(quer2(l,l+r>>1,x->L),quer2(l+r>>1,r,x->R));
                                        ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...