oj.uz

Submission #391859

# Submission time Handle Problem Language Result Execution time Memory
391859 2021-04-20T04:00:25 Z 8e7 Cake (CEOI14_cake) C++14
35 / 100
 2000 ms 5844 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define ll long long
#define maxn 250005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);
using namespace std;
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
//template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_upate>;

int arr[maxn], a[2][maxn], orig[2][maxn], ord[2][maxn], p[10 * maxn];

int al, bl;
void build() {
	int ind = 1, ti = 1;
	for (int i = 1;i <= al;i++) a[0][i] = max(orig[0][i], a[0][i - 1]);
	for (int i = 1;i <= bl;i++) a[1][i] = max(orig[1][i], a[1][i - 1]);
	for (int i = 1;i <= al;i++) {
		while (ind <= bl && a[0][i] >= a[1][ind]) {
			ord[1][ind++] = ti++;
		}
		ord[0][i] = ti++;
	}
	while (ind <= bl) ord[1][ind++] = ti++;
}
int main() {
	io
	int n, st;
	cin >> n >> st;
	st--;
	al = st, bl = n - 1 - st;
	for (int i = 0;i < n;i++) {
		cin >> arr[i];
		p[arr[i]] = i;
		if (i < st) orig[0][st - i] = arr[i]; //1 base
		else if (i > st) orig[1][i - st] = arr[i];
	}
	build();
	int q;
	cin >> q;
	while (q--) {
		char type;
		cin >> type;
		if (type == 'E') {
			int ind, val;
			cin >> ind >> val;
			ind--, val--;
			for (int i = 0;i < n;i++) {
				if (arr[i] <= n - val && arr[i] > arr[ind]) arr[i]--;
			}
			arr[ind] = n - val;
			for (int i = 0;i < n;i++) {
				if (i < st) orig[0][st - i] = arr[i]; //1 base
				else if (i > st) orig[1][i - st] = arr[i];
			}
			build();
			//for (int i = 0;i < n;i++) cout << arr[i] << " ";
			//cout << endl;
			/*
			p[cur - val] = ind;
			if (ind < st) orig[0][st - ind] = cur - val;
			else if (ind > st) orig[1][ind - st] = cur - val;

			for (int i = 1;i <= al;i++) {
				cout << orig[0][i] << " ";
			}
			cout << endl;
			for (int i = 1;i <= bl;i++) {
				cout << orig[1][i] << " ";
			}
			cout << endl;
	*/

		} else {
			int ind;
			cin >> ind;
			ind--;
			/*
			int lef = st - 1, rig = st + 1;
			if (ind == st) {
				cout << 0 << "\n";
				continue;
			}
			int cnt = 1;
			while (rig - lef < n + 1) {
				int av = lef >= 0 ? arr[lef] : 1<<30;
				int bv = rig < n ? arr[rig] : 1<<30;
				if (av < bv) {
					if (lef == ind) break;
					lef--;
				} else {
					if (rig == ind) break;
					rig++;
				}
				cnt++;
			}
			cout << cnt << "\n";
			*/
			if (ind < st) {
				cout << ord[0][st - ind] << "\n";
			} else if (ind > st) {
				cout << ord[1][ind - st] << "\n";
			} else {
				cout << 0 << "\n";
			}
		}
	}
}
/*
5 3
5 1 2 4 3
17
F 1
F 2
F 3
F 4
F 5
E 2 1
F 1
F 2
F 3
F 4
F 5
E 5 2
F 1
F 2
F 3
F 4
F 5
 */

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 28 ms 388 KB Output is correct
5 Correct 475 ms 564 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2084 ms 460 KB Time limit exceeded
2 Execution timed out 2071 ms 460 KB Time limit exceeded
3 Execution timed out 2081 ms 460 KB Time limit exceeded
4 Execution timed out 2079 ms 464 KB Time limit exceeded
5 Execution timed out 2083 ms 844 KB Time limit exceeded
6 Execution timed out 2072 ms 844 KB Time limit exceeded
7 Execution timed out 2097 ms 844 KB Time limit exceeded
8 Execution timed out 2094 ms 844 KB Time limit exceeded

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 2896 KB Output is correct
2 Correct 249 ms 2716 KB Output is correct
3 Correct 242 ms 2624 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 360 ms 5764 KB Output is correct
6 Correct 372 ms 5844 KB Output is correct
7 Correct 337 ms 5796 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 424 KB Output is correct
2 Correct 1229 ms 588 KB Output is correct
3 Execution timed out 2080 ms 1476 KB Time limit exceeded
4 Execution timed out 2079 ms 1352 KB Time limit exceeded
5 Correct 1502 ms 660 KB Output is correct
6 Execution timed out 2085 ms 1732 KB Time limit exceeded
7 Execution timed out 2086 ms 592 KB Time limit exceeded
8 Execution timed out 2080 ms 2252 KB Time limit exceeded
9 Execution timed out 2083 ms 5236 KB Time limit exceeded
10 Execution timed out 2083 ms 820 KB Time limit exceeded
11 Execution timed out 2088 ms 720 KB Time limit exceeded
12 Execution timed out 2083 ms 4340 KB Time limit exceeded
13 Execution timed out 2088 ms 5192 KB Time limit exceeded