oj.uz

Submission #105052

# Submission time Handle Problem Language Result Execution time Memory
105052 2019-04-10T10:18:35 Z groeneprof Cake (CEOI14_cake) C++14
0 / 100
 1046 ms 28096 KB 
#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]]+(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]+20*(1<<15);
						for(int k = 0; k<11; k++){
							d[top[k]] = start-k*(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]]+(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]+20*(1<<15);
						for(int k = 0; k<11; k++){
							d[top[k]] = start-k*(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(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)-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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 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 215 ms 4804 KB Output isn't correct
2 Incorrect 242 ms 4892 KB Output isn't correct
3 Incorrect 231 ms 4956 KB Output isn't correct
4 Incorrect 178 ms 4984 KB Output isn't correct
5 Incorrect 272 ms 6064 KB Output isn't correct
6 Incorrect 248 ms 5992 KB Output isn't correct
7 Incorrect 273 ms 6136 KB Output isn't correct
8 Incorrect 229 ms 6136 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 293 ms 10196 KB Output isn't correct
2 Incorrect 244 ms 9976 KB Output isn't correct
3 Incorrect 245 ms 10092 KB Output isn't correct
4 Incorrect 3 ms 356 KB Output isn't correct
5 Incorrect 396 ms 23024 KB Output isn't correct
6 Incorrect 334 ms 22904 KB Output isn't correct
7 Incorrect 331 ms 22904 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 1016 KB Output isn't correct
2 Incorrect 65 ms 1284 KB Output isn't correct
3 Incorrect 145 ms 5368 KB Output isn't correct
4 Incorrect 145 ms 5416 KB Output isn't correct
5 Incorrect 194 ms 2040 KB Output isn't correct
6 Incorrect 289 ms 7592 KB Output isn't correct
7 Incorrect 302 ms 3404 KB Output isn't correct
8 Incorrect 168 ms 10748 KB Output isn't correct
9 Incorrect 1004 ms 27948 KB Output isn't correct
10 Incorrect 638 ms 5496 KB Output isn't correct
11 Incorrect 716 ms 7644 KB Output isn't correct
12 Incorrect 1046 ms 23720 KB Output isn't correct
13 Incorrect 893 ms 28096 KB Output isn't correct