답안 #49150

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49150 2018-05-22T19:45:16 Z khohko 케이크 (CEOI14_cake) C++17
0 / 100
2000 ms 41684 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;

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;
			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));
                                        ~^~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1037 ms 25024 KB Output isn't correct
2 Correct 553 ms 25224 KB Output is correct
3 Correct 772 ms 25236 KB Output is correct
4 Correct 392 ms 25236 KB Output is correct
5 Incorrect 1109 ms 26768 KB Output isn't correct
6 Correct 936 ms 26876 KB Output is correct
7 Correct 772 ms 26876 KB Output is correct
8 Correct 517 ms 26928 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 404 ms 26928 KB Output is correct
2 Correct 331 ms 26928 KB Output is correct
3 Correct 267 ms 26928 KB Output is correct
4 Incorrect 2 ms 26928 KB Output isn't correct
5 Correct 623 ms 28848 KB Output is correct
6 Incorrect 713 ms 28936 KB Output isn't correct
7 Correct 428 ms 28936 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 120 ms 28936 KB Output isn't correct
2 Correct 96 ms 28936 KB Output is correct
3 Correct 230 ms 28936 KB Output is correct
4 Correct 282 ms 28936 KB Output is correct
5 Incorrect 339 ms 28936 KB Output isn't correct
6 Correct 435 ms 28936 KB Output is correct
7 Correct 393 ms 28936 KB Output is correct
8 Correct 517 ms 28936 KB Output is correct
9 Execution timed out 2037 ms 40040 KB Time limit exceeded
10 Incorrect 1306 ms 40040 KB Output isn't correct
11 Correct 1647 ms 40040 KB Output is correct
12 Execution timed out 2028 ms 40040 KB Time limit exceeded
13 Incorrect 1605 ms 41684 KB Output isn't correct