Submission #49153

#	Time	Username	Problem	Language	Result	Execution time	Memory
49153		khohko	Cake (CEOI14_cake)	C++17	83.33 / 100	2053 ms	30736 KiB

cake

#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));
                                        ~^~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 33.333333 / 50