제출 #391941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391941		8e7	케이크 (CEOI14_cake)	C++14	100 / 100	902 ms	9108 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];
pii big[11];
vector<pii> vec;

int al, bl;
struct segtree{
	int seg[4 * maxn];
	void init(int cur, int l, int r, int v[]) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = v[l];
			return;
		}
		int mid = (l + r) / 2;
		init(cur * 2, l, mid, v);
		init(cur * 2 + 1, mid, r, v);
		seg[cur] = max(seg[cur * 2], seg[cur * 2 + 1]);
	}
	void modify(int cur, int l, int r, int ind, int val) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = val;
			return;
		}
		int mid = (l + r) / 2;
		if (ind < mid) modify(cur * 2, l, mid, ind, val);
		else modify(cur * 2 + 1, mid, r, ind, val);
		seg[cur] = max(seg[cur * 2], seg[cur * 2 + 1]);
		//cout << l << " " << r << " " << seg[cur] << endl;
	}
	int query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return 0;
		//cout << l << " " << r << " " << ql << " " << qr << endl;
		if (ql <= l && qr >= r) return seg[cur];
		int mid = (l + r) / 2;
		return max(query(cur * 2, l, mid, ql, qr), query(cur * 2 + 1, mid, r, ql, qr));
	}
	int search(int cur, int l, int r, int val, int num) {
		//cout << l << " " << r << " " << val << " " << seg[cur] << endl;
		if (r <= l) return l;
		if (r - l == 1) {
			return max(num, seg[cur]) < val ? r : l;
		}

		int mid = (l + r) / 2;
		if (max(num, seg[cur * 2]) < val) return search(cur * 2 + 1, mid, r, val, max(num, seg[cur * 2]));
		else return search(cur * 2, l, mid, val, num);
	}
} sl, sr;


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];
		vec.push_back(make_pair(arr[i], i));
		if (i < st) orig[0][st - i - 1] = arr[i]; //1 base
		else if (i > st) orig[1][i - st - 1] = arr[i];
	}
	sort(vec.begin(), vec.end());
	for (int i = max(0, n - 10);i < n;i++) {
		big[n - i - 1] = vec[i]; //0~9
	}
	sl.init(1, 0, al, orig[0]);
	sr.init(1, 0, bl, orig[1]);

	int q;
	cin >> q;
	while (q--) {
		char type;
		cin >> type;
		if (type == 'E') {
			int ind, pos;
			cin >> ind>> pos;
			ind--, pos--;
			int orig = min(9, n - 1);
			for (int i = 0;i < min(10, n);i++) {
				if (big[i].ss == ind) {
					orig = i;
					break;
				}
			}

			int val = big[pos].ff + 1;
			for (int i = 0;i < pos;i++) {
				int id = big[i].ss;
				big[i].ff++;
				if (id < st) {
					//cout << "l " << st - id - 1 << " " << big[i].ff << endl;
					sl.modify(1, 0, al, st - id - 1, big[i].ff);
				} else if (id > st) {
					//cout << "r " << id - st - 1 << " " << big[i].ff << endl;
					sr.modify(1, 0, bl, id - st - 1, big[i].ff);
				}
			}
			for (int i = orig;i > pos;i--) big[i] = big[i - 1];
			big[pos].ss = ind;
			big[pos].ff++;
			if (ind < st) {
				//cout << "l " << st - ind - 1 << " " << val << endl;
				sl.modify(1, 0, al, st - ind - 1, val);
			} else if (ind > st) {
				//cout << "r " << ind - st - 1 << " " << val << endl;
				sr.modify(1, 0, bl, ind - st - 1, val);
			}
			/*
			for (int i = 0;i < n;i++) {
				cout << big[i].ff << " " << big[i].ss << endl;
			}
			*/

		} else {
			int ind;
			cin >> ind;
			ind--;
			if (ind == st) {
				cout << 0 << "\n";
			} else if (ind < st) {
				int p = st - ind - 1;
				int pref = sl.query(1, 0, al, 0, p + 1);
				cout << sr.search(1, 0, bl, pref, 0) + p + 1 << "\n";
			} else {
				int p = ind - st - 1;
				int pref = sr.query(1, 0, bl, 0, p + 1);
				cout << sl.search(1, 0, al, pref, 0) + p + 1 << "\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: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50