Submission #1236865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236865		kaiboy	Cake (CEOI14_cake)	C++20	100 / 100	93 ms	5956 KiB

cake

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 250000;

int aa[N], ii[N], pp[N + 1], qq[N], ll[N], rr[N], tt[N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, i_; cin >> n >> i_, i_--;
	for (int i = 0; i < n; i++)
		cin >> aa[i], ii[--aa[i]] = i;
	for (int a = 0; a < n; a++) {
		pp[ii[a]] = a ? ii[a - 1] : -1;
		qq[ii[a]] = a + 1 < n ? ii[a + 1] : n;
	}
	pp[n] = ii[n - 1];
	int kl = 0;
	for (int i = i_ - 1; i >= 0; i--)
		if (!kl || aa[ll[kl - 1]] < aa[i])
			ll[kl++] = i;
	int kr = 0;
	for (int i = i_ + 1; i < n; i++)
		if (!kr || aa[rr[kr - 1]] < aa[i])
			rr[kr++] = i;
	int qr; cin >> qr;
	while (qr--) {
		char c; cin >> c;
		if (c == 'E') {
			int i, z; cin >> i >> z, i--, z--;
			int p = pp[i], q = qq[i];
			if (p >= 0)
				qq[p] = q;
			pp[q] = p;
			int j = n;
			while (z--)
				aa[j = pp[j]]++;
			pp[i] = pp[j], qq[i] = j;
			aa[i] = aa[pp[i]] + 1;
			qq[pp[i]] = pp[qq[i]] = i;
			if (i == i_)
				continue;
			if (i < i_) {
				int lower = -1, upper = kl;
				while (upper - lower > 1) {
					int h = lower + upper >> 1;
					if (ll[h] > i)
						lower = h;
					else
						upper = h;
				}
				int h_ = lower;
				if (h_ < 0 || aa[ll[h_]] < aa[i]) {
					int k = 0;
					for (int h = kl - 1; h > h_ && aa[i] < aa[ll[h]]; h--)
						tt[k++] = ll[h];
					int kl_ = h_ + 1;
					ll[kl_++] = i;
					while (k--)
						ll[kl_++] = tt[k];
					kl = kl_;
				}
			} else {
				int lower = -1, upper = kr;
				while (upper - lower > 1) {
					int h = lower + upper >> 1;
					if (rr[h] < i)
						lower = h;
					else
						upper = h;
				}
				int h_ = lower;
				if (h_ < 0 || aa[rr[h_]] < aa[i]) {
					int k = 0;
					for (int h = kr - 1; h > h_ && aa[i] < aa[rr[h]]; h--)
						tt[k++] = rr[h];
					int kr_ = h_ + 1;
					rr[kr_++] = i;
					while (k--)
						rr[kr_++] = tt[k];
					kr = kr_;
				}
			}
		} else {
			int i; cin >> i, i--;
			if (i == i_) {
				cout << "0\n";
				continue;
			}
			if (i < i_) {
				int lower = 0, upper = kl;
				while (upper - lower > 1) {
					int h = lower + upper >> 1;
					if (ll[h] >= i)
						lower = h;
					else
						upper = h;
				}
				int a = aa[ll[lower]];
				lower = -1, upper = kr;
				while (upper - lower > 1) {
					int h = lower + upper >> 1;
					if (aa[rr[h]] > a)
						upper = h;
					else
						lower = h;
				}
				int h = upper;
				cout << (h < kr ? rr[h] : n) - i - 1 << '\n';
			} else {
				int lower = 0, upper = kr;
				while (upper - lower > 1) {
					int h = lower + upper >> 1;
					if (rr[h] <= i)
						lower = h;
					else
						upper = h;
				}
				int a = aa[rr[lower]];
				lower = -1, upper = kl;
				while (upper - lower > 1) {
					int h = lower + upper >> 1;
					if (aa[ll[h]] > a)
						upper = h;
					else
						lower = h;
				}
				int h = upper;
				cout << i - (h < kl ? ll[h] : -1) - 1 << '\n';
			}
		}
	}
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50