Submission #860128

#	Time	Username	Problem	Language	Result	Execution time	Memory
860128		dsyz	Cake (CEOI14_cake)	C++17	100 / 100	1000 ms	41940 KiB

cake

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node {
	ll s,e,m,v;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) / 2;
		v = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void update(ll x,ll val){
		if(s == e){
			v = val;
			return;
		}else{
			if(x > m) r -> update(x,val);
			else l -> update(x,val);
			v = max(l->v,r->v);
		}
	}
	ll rmq(ll x,ll y){
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r -> rmq(x,y);
			else if(y <= m) return l -> rmq(x,y);
			else return max(l -> rmq(x,m),r -> rmq(m + 1,y));
		}
	}
} *root;
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,A;
	cin>>N>>A;
	root = new node(1,N);
	ll D[N + 1], pos[10];
	for(ll i = 1;i <= N;i++){
		cin>>D[i];
		root -> update(i,D[i]);
		if(N - D[i] < 10){ //cake i is among top 10 most delicious
			pos[N - D[i]] = i;
		} 
	}
	ll Q;
	cin>>Q;
	for(ll q = 0;q < Q;q++){
		char t;
		cin>>t;
		if(t == 'E'){
			ll x,e;
			cin>>x>>e;
			ll ps = 10;
			for(ll i = 0;i < 10;i++){
				if(pos[i] == x){
					ps = i;
				}
			}
			root -> update(x,root -> rmq(pos[e - 1],pos[e - 1]) + 1);
			while(ps >= e){
				pos[ps] = pos[ps - 1]; //shifting right
				ps--;
			}
			pos[e - 1] = x;
			for(ll i = 0;i < e - 1;i++){
				root -> update(pos[i],root -> rmq(pos[i],pos[i]) + 1);
			}
		}else if(t == 'F'){
			ll x;
			cin>>x;
			if(x == A){
				cout<<0<<'\n';
				continue;
			}else if(x < A){ //left of starting position
				ll mx = root -> rmq(x,A - 1);
				ll high = N + 1;
				ll low = A;
				while(high - low > 1){
					ll mid = (high + low) / 2;
					if(root -> rmq(A + 1,mid) < mx){
						low = mid;
					}else{
						high = mid;
					}
				}
				cout<<low - x<<'\n';
			}else{ //right of starting position
				ll mx = root -> rmq(A + 1,x);
				ll high = A;
				ll low = 0;
				while(high - low > 1){
					ll mid = (high + low) / 2;
					if(root -> rmq(mid,A - 1) < mx){
						high = mid;
					}else{
						low = mid;
					}
				}
				cout<<x - high<<'\n';
			}
		}
	}
}

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