oj.uz

Submission #105061

# Submission time Handle Problem Language Result Execution time Memory
105061 2019-04-10T11:45:38 Z groeneprof Cake (CEOI14_cake) C++14
0 / 100
 1012 ms 21724 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);
						//cout<<"nice"<<endl;
						for(int k = 0; k<11 && k<top.size(); 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-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;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:148:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int k = 0; k<11 && k<top.size(); k++){
                              ~^~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 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 184 ms 1116 KB Output isn't correct
2 Incorrect 221 ms 1152 KB Output isn't correct
3 Incorrect 190 ms 1152 KB Output isn't correct
4 Correct 200 ms 1272 KB Output is correct
5 Incorrect 210 ms 2344 KB Output isn't correct
6 Incorrect 237 ms 2360 KB Output isn't correct
7 Incorrect 222 ms 2304 KB Output isn't correct
8 Correct 211 ms 2304 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 236 ms 8824 KB Output isn't correct
2 Incorrect 237 ms 8696 KB Output isn't correct
3 Incorrect 220 ms 8828 KB Output isn't correct
4 Correct 3 ms 384 KB Output is correct
5 Incorrect 325 ms 20700 KB Output isn't correct
6 Incorrect 313 ms 20644 KB Output isn't correct
7 Incorrect 338 ms 20512 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 716 KB Output isn't correct
2 Incorrect 60 ms 888 KB Output isn't correct
3 Incorrect 130 ms 4472 KB Output isn't correct
4 Incorrect 165 ms 4576 KB Output isn't correct
5 Incorrect 199 ms 760 KB Output isn't correct
6 Incorrect 310 ms 6052 KB Output isn't correct
7 Incorrect 293 ms 1784 KB Output isn't correct
8 Incorrect 191 ms 8352 KB Output isn't correct
9 Incorrect 1012 ms 21720 KB Output isn't correct
10 Incorrect 569 ms 1792 KB Output isn't correct
11 Incorrect 710 ms 3448 KB Output isn't correct
12 Incorrect 896 ms 17760 KB Output isn't correct
13 Incorrect 860 ms 21724 KB Output isn't correct