Submission #1236840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236840		kaiboy	Cake (CEOI14_cake)	C++20	0 / 100	78 ms	2888 KiB

cake

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 250000;

int aa[N], ii[10], 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];
		if (n - aa[i] < 10)
			ii[n - aa[i]] = i;
	}
	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 q; cin >> q;
	while (q--) {
		char c; cin >> c;
		if (c == 'E') {
			int i, z; cin >> i >> z, i--, z--;
			for (int y = 9; y > z; y--)
				ii[y] = ii[y - 1];
			aa[ii[z] = i] = aa[ii[z - 1]];
			while (z--)
				aa[ii[z]]++;
			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: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50