oj.uz

Submission #131739

# Submission time Handle Problem Language Result Execution time Memory
131739 2019-07-17T13:56:28 Z oolimry Cake (CEOI14_cake) C++14
100 / 100
 484 ms 10360 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 9 ms 632 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 4824 KB Output is correct
2 Correct 120 ms 4828 KB Output is correct
3 Correct 131 ms 4856 KB Output is correct
4 Correct 105 ms 4860 KB Output is correct
5 Correct 163 ms 5212 KB Output is correct
6 Correct 154 ms 5752 KB Output is correct
7 Correct 143 ms 5368 KB Output is correct
8 Correct 121 ms 5628 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 3064 KB Output is correct
2 Correct 84 ms 3036 KB Output is correct
3 Correct 81 ms 2972 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 137 ms 5340 KB Output is correct
6 Correct 135 ms 5340 KB Output is correct
7 Correct 106 ms 5220 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 888 KB Output is correct
2 Correct 26 ms 888 KB Output is correct
3 Correct 61 ms 1912 KB Output is correct
4 Correct 61 ms 2040 KB Output is correct
5 Correct 72 ms 1912 KB Output is correct
6 Correct 98 ms 3032 KB Output is correct
7 Correct 95 ms 2500 KB Output is correct
8 Correct 77 ms 3660 KB Output is correct
9 Correct 484 ms 10224 KB Output is correct
10 Correct 234 ms 5276 KB Output is correct
11 Correct 285 ms 6264 KB Output is correct
12 Correct 455 ms 9592 KB Output is correct
13 Correct 397 ms 10360 KB Output is correct