Submission #131739

#	Time	Username	Problem	Language	Result	Execution time	Memory
131739		oolimry	Cake (CEOI14_cake)	C++14	100 / 100	484 ms	10360 KiB

cake

#include <bits/stdc++.h>

using namespace std;

const int N = 250005;
static int tree[2 * N];

void update(int i, int x){
	i += N;
	while(i > 0){
		tree[i] = max(tree[i],x);
		i >>= 1;
	}
}

int query(int l, int r){
	int ans = -123;
	for(l += N, r += N;l < r;l >>= 1, r >>= 1){
		if(l&1){
			ans = max(ans, tree[l]);
			l++;
		}
		if(r&1){
			r--;
			ans = max(ans, tree[r]);
		}
	}
	return ans;
}

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, a;
	cin >> n >> a;
	int best[11];
	fill(best,best+11,-1);
	for(int i = 0;i < n;i++){
		int x;
		cin >> x;
		update(i+1,x);
		if(n - x < 11) best[n-x] = i+1; 
	}
	update(0,102345678);
	update(n+1,102345679);
	int q;
	cin >> q;
	
	for(int qq = 0;qq < q;qq++){
		char cc;
		cin >> cc;
		if(cc == 'F'){
			int x;
			cin >> x;
			if(x == a){
				cout << "0\n";
			}
			else if(x < a){
				int bound = query(x,a);
				int low = a;
				int high = n+1;
				while(true){
					if(low == high - 1) break;
					int s = (low + high) / 2;
					if(query(a+1,s+1) > bound) high = s;
					else low = s;
				}
				cout << high - x - 1 << "\n";
			}
			else{
				int bound = query(a+1,x+1);
				int low = 0;
				int high = a;
				while(true){
					if(low == high - 1) break;
					int s = (low + high) / 2;
					if(query(s,a) > bound) low = s;
					else high = s;
				}
				cout << x - low - 1 << "\n";
			}
		}
		else{
			int x, y;
			cin >> x >> y;
			int start = 10;
			for(int i = 0;i < 10;i++){
				if(best[i] == x){
					start = i;
					break;
				}
			}
			
			for(int i = start;i >= y;i--){
				best[i] = best[i-1];
			}
			
			best[y-1] = x;
			for(int i = 0;i < y - 1;i++){
				update(best[i], query(best[i],best[i]+1) + 1);
				//cout << best[i] << " " << query(best[i],best[i]+1) + 1;
			}
			update(x, query(best[y],best[y]+1) + 1);
			//cout << x << " " << best[u
		}
	}
	return 0;
}

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