oj.uz

Submission #49151

# Submission time Handle Problem Language Result Execution time Memory
49151 2018-05-22T19:50:37 Z khohko Cake (CEOI14_cake) C++17
83.3333 / 100
 2000 ms 30784 KB 
#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);

	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;
			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);
			}
		}
	}



}

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

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 432 KB Output is correct
4 Correct 11 ms 596 KB Output is correct
5 Correct 30 ms 1696 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 1696 KB Output is correct
2 Correct 515 ms 1788 KB Output is correct
3 Correct 549 ms 1788 KB Output is correct
4 Correct 251 ms 1788 KB Output is correct
5 Correct 901 ms 3340 KB Output is correct
6 Correct 755 ms 3468 KB Output is correct
7 Correct 638 ms 3468 KB Output is correct
8 Correct 271 ms 3468 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 12524 KB Output is correct
2 Correct 311 ms 12572 KB Output is correct
3 Correct 322 ms 12572 KB Output is correct
4 Correct 2 ms 12572 KB Output is correct
5 Correct 717 ms 29684 KB Output is correct
6 Correct 692 ms 29868 KB Output is correct
7 Correct 601 ms 29868 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 29868 KB Output is correct
2 Correct 102 ms 29868 KB Output is correct
3 Correct 276 ms 29868 KB Output is correct
4 Correct 275 ms 29868 KB Output is correct
5 Correct 331 ms 29868 KB Output is correct
6 Correct 501 ms 29868 KB Output is correct
7 Correct 402 ms 29868 KB Output is correct
8 Correct 370 ms 29868 KB Output is correct
9 Execution timed out 2059 ms 30548 KB Time limit exceeded
10 Correct 1086 ms 30548 KB Output is correct
11 Correct 1586 ms 30548 KB Output is correct
12 Execution timed out 2078 ms 30548 KB Time limit exceeded
13 Correct 1936 ms 30784 KB Output is correct