Submission #105062

#	Time	Username	Problem	Language	Result	Execution time	Memory
105062		groeneprof	Cake (CEOI14_cake)	C++14	0 / 100	1073 ms	21692 KiB

cake

#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
#define st ts[tree]
using namespace std;
const bool debug = 0;
vector<int> ts[2];
int N, A, Q;
vector<int> d;
int update(int i, int val, int u = 0, int L = 0, int R = N, int tree = -1){
	if(tree == -1) tree = (i>=A)?1:0;
	//cout<<"u "<<i<<" "<<val<<" "<<u<<" "<<L<<" "<<R<<" "<<tree<<endl;
	if(i<L||i>R){
		return st[u];
	}
	if(L==R){
		return st[u] = val;
	}
	st[u] = max(update(i, val, u*2+1, L, (L+R)/2, tree), update(i, val, u*2+2, (L+R)/2+1, R, tree));
	//cout<<"u "<<i<<" "<<val<<" "<<u<<" "<<L<<" "<<R<<" "<<tree<<"updates to "<<st[u]<<endl;
	return st[u];
}
int query(int i, int j, int u = 0, int L = 0, int R = N, int tree = -1){
	if(tree == -1) tree = (i>=A)?1:0;
	//cout<<"q "<<i<<" "<<j<<" "<<u<<" "<<L<<" "<<R<<" "<<tree<<" "<<st[u]<<endl;
	if(j<L||i>R){
		return 0;
	}
	if(L>=i&&R<=j){
		return st[u];
	}
	return max(query(i, j, u*2+1, L, (L+R)/2, tree), query(i, j, u*2+2, (L+R)/2+1, R, tree));
}
int binsearch1(int val, int u = 0, int L = 0, int R = N, int tree = 1){ //search to the right of a
	if(L == R) {
		return L;
	}
	if(st[u*2+1] > val){ //the element we are looking for is in the first subtree
		return binsearch1(val, u*2+1, L, (L+R)/2, tree);
	}
	else{ //not
		return binsearch1(val, u*2+2, (L+R)/2+1, R, tree);
	}
} 
int binsearch0(int val, int u = 0, int L = 0, int R = N, int tree = 0){
	//cout<<"bs "<<val<<" "<<u<<" "<<L<<" "<<R<<" "<<tree<<endl;
	if(L==R){
		return L;
	}
	if(st[u*2+2] > val){ //it's in the right subtree
		return binsearch0(val, u*2+2, (L+R)/2+1, R, tree);
	}
	else{
		return binsearch0(val, u*2+1, L, (L+R)/2, tree);
	}
}




signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>A;
	A--;
	d.resize(N);
	ts[0].resize(4*N, 0);
	ts[1].resize(4*N, 0);
	vector<int> top;
	F(i, N){
		int a;
		cin>>a;
		d[i]=a;
		update(i,a);
	}
	H((int)(1e18));
	update(N, 1e18);
	cin>>Q;
	auto copy = d;
	sort(copy.begin(), copy.end());
	//cout<<"aaaaaaaa"<<endl;
	FR(i, N-10, N){
		top.push_back(copy[i]);
	}
	//cout<<"bbbbbbbbbb"<<endl;
	F(i, Q){
		char c;
		cin>>c;
		if(c=='E'){
			int j, e;
			cin>>j>>e;
			j--;
			e--;

			vector<int>::iterator it = find(top.begin(), top.end(), j);
			//cout<<"aaaa"<<endl;
			if(it!=top.end()){
				//cout<<"bbbb"<<endl;
				if(e==0){
					//cout<<"cccc"<<endl;
					d[j] = d[top[0]]+(int)(1<<15);
					if(j!=A) update(j, d[j]);
					top.insert(top.begin()+e, j);
					//cout<<"cccc"<<endl;
				}
				else{
					top.insert(top.begin()+e, j);
					if(d[top[e-1]]-d[top[e+1]]==1){
						int start = d[0]+(int)(20*(1<<15));
						for(int k = 0; k<11; k++){
							d[top[k]] = start-k*(int)(1<<15);
							if(top[k]!=A)update(top[k], d[top[k]]);
						}
					}
					else{
						d[j] = (d[top[e-1]]+d[top[e+1]])/2;
						if(j!=A) update(j, d[j]);
					}
				}
				top.erase(it+1);
			}
			else{
				P("eeee");
				if(e==0){
					P("ffff");
					d[j] = d[top[0]]+(int)(1<<15);
					if(j!=A) update(j, d[j]);
					top.insert(top.begin()+e, j);
				}
				else{
					P("ggGG");
					top.insert(top.begin()+e, j);
					if(d[top[e-1]]-d[top[e+1]]==1){
						int start = d[0]+(int)(20*(1<<15));
						//cout<<"nice"<<endl;
						for(int k = 0; k<11 && k<(int)(top.size()); k++){
							d[top[k]] = start-k*(int)(1ll<<15ll);
							if(top[k]!=A) update(top[k], d[top[k]]);
						}
					}
					else{
						d[j] = (d[top[e-1]]+d[top[e+1]])/2ll;
						if(j!=A) update(j, d[j]);
					}
				}
				top.erase(top.end()-1);
			}
		}
		else if(c == 'F'){
			int b;
			cin>>b;
			b--;
			if(b == A){
				cout<<0<<endl;
				continue;
			}
			else if(b<A){
				P(1);
				int M = query(b, A);
				H(M);
				int C  = binsearch1(M);
				H(C << "-" << b);
				cout<<min(N-1,C-1)-b<<endl;
			}
			else{
				P(0);
				int M = query(A, b);
				H(M);
				int C = binsearch0(M);
				H(C);
				if(d[C]>M) C++;
				cout<<b-C<<endl;
			}
		}
	}
	return 0;
}

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