Submission #58044

#	Time	Username	Problem	Language	Result	Execution time	Memory
58044		fredbr	Cake (CEOI14_cake)	C++17	20 / 100	2086 ms	6288 KiB

cake

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 250001;
 
int n, a;
int v[maxn];
int d[maxn];
 
vector<int> ans;
 
inline void f()
{
	ans = {a};
 
	int l = a-1, r = a+1;
	d[a] = 0;
 
	for (int i = 1; i < n; i++) {
 
		if (l > 0 and r <= n) {
			if (v[l] < v[r])
				d[l] = i, l--, ans.push_back(l+1);
			else 
				d[r] = i, r++, ans.push_back(r-1);
		}
		else if (l == 0)
			d[r] = i, r++, ans.push_back(r-1);
		else d[l] = i, l--, ans.push_back(l+1);
	}
 
	// for (int i : ans)
	// 	cout << i << " ";
	// cout << "\n";
}
 
inline void fix(int pos, int x, int old)
{
	for (int i = 1; i <= n; i++) {
 
		if (i == pos) continue;
		if (v[i] <= x and v[i] > old)
			v[i]--;
	}
	v[pos] = x;
}

int inv[maxn];
int mrk[maxn];
deque<int> q;

void fix2()
{
	memset(mrk, 0, sizeof(mrk));

	deque<int> qq;
	int num = n;
	while (!q.empty()) {

		if (mrk[q.front()]) {
			q.pop_front();
			continue;
		}
		v[q.front()] = num--;
		mrk[q.front()] = 1;
		qq.push_back(q.front());
		q.pop_front();
	}
	// for (int i = 1; i <= n; i++)
	// 	cout << v[i] << " ";
	// cout << "\n";
	f();
	q = qq;
	// cerr << q.size() << "\n";
}

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0);
 
	cin >> n >> a;
 
	for (int i = 1; i <= n; i++)
		cin >> v[i], inv[v[i]] = i;

	if (n > 25000) f();

	for (int i = 1; i <= n; i++)
		q.push_front(inv[i]);
 
	int Q;
	cin >> Q;
 
	while (Q--) {
 
		char op;
		cin >> op;
 
		if (op == 'E') {
 
			int pos, x;
			cin >> pos >> x;

			if (n > 25000)
				fix(pos, n-x+1, v[pos]), f();
			else {

				stack<int> qq;
				while (--x)
					qq.push(q.front()), q.pop_front();
				q.push_front(pos);
				while (!qq.empty())
					q.push_front(qq.top()), qq.pop();
			}
		}
		else {
 
			int pos;
			cin >> pos;
 	
 			if (n > 25000)
				cout <<d[pos] << "\n";
			else {

				fix2();
				cout << d[pos] << "\n";

			}
		}
	}
}

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