Submission #49155

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49155	2018-05-22T20:08:20 Z	khohko	Cake (CEOI14_cake)	C++17	100 / 100	1555 ms	30720 KB

cake

#include <bits/stdc++.h>
//glhf nikabb u suck
#pragma GCC optimize("O3")
using namespace std;
#define ll int 
#define lol int 
#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);
	scanf("%d %d",&n,&s);
	n+=2;
	for(int i=1; i<=n-2; i++){
		//cin>>wx;
		scanf("%d",&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;
	scanf("%d",&qr);
	while(qr--){
			scanf("%c",&q);
			scanf("%c",&q);
		if(q=='F'){
			ll x;
			//cin>>x;
			scanf("%d",&x);
			if(x==s)
				printf("0\n");
				//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;
				printf("%d\n",t-x-1);
			}
			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;
				printf("%d\n",x-t-1);
				//cout<<x-t-1<<endl;
			}
		}
		else {
			ll i,c;
			//cin>>i>>c;
			scanf("%d %d",&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

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));
                                        ~^~
cake.cpp: In function 'int main()':
cake.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&s);
  ~~~~~^~~~~~~~~~~~~~~
cake.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&wx);
   ~~~~~^~~~~~~~~~
cake.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&qr);
  ~~~~~^~~~~~~~~~
cake.cpp:129:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%c",&q);
    ~~~~~^~~~~~~~~
cake.cpp:130:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%c",&q);
    ~~~~~^~~~~~~~~
cake.cpp:134:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~
cake.cpp:163:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&i,&c);
    ~~~~~^~~~~~~~~~~~~~~

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	3 ms	356 KB	Output is correct
3	Correct	3 ms	560 KB	Output is correct
4	Correct	9 ms	740 KB	Output is correct
5	Correct	23 ms	1716 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	649 ms	1716 KB	Output is correct
2	Correct	391 ms	1756 KB	Output is correct
3	Correct	469 ms	1776 KB	Output is correct
4	Correct	277 ms	1788 KB	Output is correct
5	Correct	718 ms	3452 KB	Output is correct
6	Correct	573 ms	3588 KB	Output is correct
7	Correct	519 ms	3588 KB	Output is correct
8	Correct	336 ms	3588 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	304 ms	12684 KB	Output is correct
2	Correct	174 ms	12684 KB	Output is correct
3	Correct	153 ms	12684 KB	Output is correct
4	Correct	2 ms	12684 KB	Output is correct
5	Correct	781 ms	29864 KB	Output is correct
6	Correct	560 ms	29864 KB	Output is correct
7	Correct	288 ms	29864 KB	Output is correct

Subtask #4

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	29864 KB	Output is correct
2	Correct	53 ms	29864 KB	Output is correct
3	Correct	168 ms	29864 KB	Output is correct
4	Correct	157 ms	29864 KB	Output is correct
5	Correct	176 ms	29864 KB	Output is correct
6	Correct	277 ms	29864 KB	Output is correct
7	Correct	215 ms	29864 KB	Output is correct
8	Correct	419 ms	29864 KB	Output is correct
9	Correct	1555 ms	30644 KB	Output is correct
10	Correct	681 ms	30644 KB	Output is correct
11	Correct	747 ms	30644 KB	Output is correct
12	Correct	1369 ms	30644 KB	Output is correct
13	Correct	1206 ms	30720 KB	Output is correct