oj.uz

Submission #49148

# Submission time Handle Problem Language Result Execution time Memory
49148 2018-05-22T19:40:18 Z khohko Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 41372 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(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;

void add(ll i){
	wx=++C;
	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;
		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;
			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:81:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    return quer2(l+r>>1,r,x->R);
                 ~^~
cake.cpp:82:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else return quer2(l,l+r>>1,x->L);
                       ~^~
cake.cpp:84: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:84: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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1400 ms 24916 KB Output isn't correct
2 Incorrect 766 ms 25080 KB Output isn't correct
3 Incorrect 1045 ms 25080 KB Output isn't correct
4 Incorrect 605 ms 25080 KB Output isn't correct
5 Incorrect 1283 ms 26784 KB Output isn't correct
6 Incorrect 1121 ms 26912 KB Output isn't correct
7 Incorrect 957 ms 27000 KB Output isn't correct
8 Incorrect 646 ms 27000 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 424 ms 27000 KB Output isn't correct
2 Incorrect 320 ms 27000 KB Output isn't correct
3 Incorrect 340 ms 27000 KB Output isn't correct
4 Incorrect 2 ms 27000 KB Output isn't correct
5 Incorrect 640 ms 28688 KB Output isn't correct
6 Incorrect 595 ms 28688 KB Output isn't correct
7 Incorrect 383 ms 28688 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 28688 KB Output isn't correct
2 Incorrect 95 ms 28688 KB Output isn't correct
3 Incorrect 215 ms 28688 KB Output isn't correct
4 Incorrect 253 ms 28688 KB Output isn't correct
5 Incorrect 351 ms 28688 KB Output isn't correct
6 Incorrect 425 ms 28688 KB Output isn't correct
7 Incorrect 420 ms 28688 KB Output isn't correct
8 Incorrect 588 ms 28688 KB Output isn't correct
9 Execution timed out 2071 ms 39476 KB Time limit exceeded
10 Incorrect 1428 ms 39476 KB Output isn't correct
11 Incorrect 1621 ms 39476 KB Output isn't correct
12 Execution timed out 2070 ms 39476 KB Time limit exceeded
13 Incorrect 1842 ms 41372 KB Output isn't correct