제출 #57983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57983		fredbr	Cake (CEOI14_cake)	C++17	35 / 100	2088 ms	4672 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;

	// cout << "\n";
	// for (int i = 1; i <= n; i++)
	// 	cout << v[i] << " ";
	// cout << "\n\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];

	f();

	int q;
	cin >> q;

	while (q--) {

		char op;
		cin >> op;

		if (op == 'E') {

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

			int pos;
			cin >> pos;

			cout <<d[pos] << "\n";
		}
	}
}

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