제출 #391859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391859		8e7	Cake (CEOI14_cake)	C++14	35 / 100	2097 ms	5844 KiB

cake

//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 / 15
• Subtask 2: 0 / 15
• Subtask 3: 20 / 20
• Subtask 4: 0 / 50