Submission #58013

#	Time	Username	Problem	Language	Result	Execution time	Memory
58013		fredbr	Cake (CEOI14_cake)	C++17	0 / 100	2072 ms	20064 KiB

cake

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> ii;
typedef pair<int, ii> pii;

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";
}

set<pii> st;
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;

	// cout << "\n";
	// for (int i = 1; i <= n; i++)
	// 	cout << v[i] << " ";
	// cout << "\n\n";
}

int tmd[maxn];

inline void fix2()
{
	int at= n;
	for (pii x : st)
		v[x.ss.ss] = at--;


	
	f();

	for (int i = 1; i <= n; i++)
		v[i] = n-v[i]+1;	
	st.clear();
	for (int i = 1; i <= n; i++) 
		st.insert({v[i],{tmd[i], i}});
}


int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin >> n >> a;


	for (int i = 1; i <= n; i++)
		cin >> v[i], st.insert({n-v[i]+1,{0, i}}), v[i] = n-v[i]+1;

	int q;
	cin >> q;

	int tim = -1;
	while (q--) {

		char op;
		cin >> op;

		if (op == 'E') {

			if (n > 25000) {

				int pos, x;
				cin >> pos >> x;
				fix(pos, n-x+1, v[pos]);
				f();
			}
			else {

				int pos, x;
				cin >> pos >> x;

				st.erase(pii(v[pos], ii(tmd[pos], pos)));
				st.insert(pii(x, ii(tim, pos)));
				tmd[pos] = tim;
				v[pos] = x;

				// fix2();
			}
		}
		else {

			int pos;
			cin >> pos;

			if (n > 25000)
				cout <<d[pos] << "\n";
			else {

				fix2();
				// f();
				cout <<d[pos] << "\n";
			}
		}
		tim--;
	}
}

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