oj.uz

Submission #105060

# Submission time Handle Problem Language Result Execution time Memory
105060 2019-04-10T11:36:15 Z groeneprof Cake (CEOI14_cake) C++14
0 / 100
 1140 ms 21784 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-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.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 189 ms 1024 KB Output isn't correct
2 Incorrect 242 ms 1188 KB Output isn't correct
3 Incorrect 217 ms 1152 KB Output isn't correct
4 Correct 240 ms 1272 KB Output is correct
5 Incorrect 372 ms 2304 KB Output isn't correct
6 Incorrect 276 ms 2424 KB Output isn't correct
7 Incorrect 282 ms 2424 KB Output isn't correct
8 Correct 194 ms 2304 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 278 ms 8972 KB Output isn't correct
2 Incorrect 264 ms 8568 KB Output isn't correct
3 Incorrect 257 ms 8696 KB Output isn't correct
4 Correct 3 ms 384 KB Output is correct
5 Incorrect 384 ms 20712 KB Output isn't correct
6 Incorrect 377 ms 20576 KB Output isn't correct
7 Incorrect 326 ms 20216 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 696 KB Output isn't correct
2 Incorrect 65 ms 1028 KB Output isn't correct
3 Incorrect 141 ms 4472 KB Output isn't correct
4 Incorrect 159 ms 4468 KB Output isn't correct
5 Incorrect 163 ms 860 KB Output isn't correct
6 Incorrect 265 ms 5940 KB Output isn't correct
7 Incorrect 303 ms 1692 KB Output isn't correct
8 Incorrect 233 ms 8236 KB Output isn't correct
9 Incorrect 1140 ms 21784 KB Output isn't correct
10 Incorrect 650 ms 1736 KB Output isn't correct
11 Incorrect 651 ms 3452 KB Output isn't correct
12 Incorrect 989 ms 17652 KB Output isn't correct
13 Incorrect 816 ms 21744 KB Output isn't correct