Submission #57898

#	Time	Username	Problem	Language	Result	Execution time	Memory
57898		MatheusLealV	Cake (CEOI14_cake)	C++17	10 / 100	2085 ms	4264 KiB

cake

#include <bits/stdc++.h>
#define N 100050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, a, v[N], ans[N], q;

int bit[N];

void upd(int x, int v)
{
	for(int i = x; i < N; i += (i&-i)) bit[i] += v;
}

int query(int x)
{
	int sum = 0;

	for(int i = x; i > 0 ;i -= (i&-i)) sum += bit[i];

	return sum;
}

inline void process()
{
	int st = a, en = a, cnt = 1;

	ans[a] = 0;

	while(st > 1 or en < n)
	{
		//cout<<st<<" "<<en<<'\n';

		if( (v[st - 1] > v[en + 1] and en < n) or st <= 1)
		{
			ans[en + 1] = cnt;

			en ++;
		}

		else ans[st - 1] = cnt, st --;

		cnt ++;
	}

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

void update(int id, int e)
{
	vector<pii> val;

	for(int i = 1; i <= n; i++)
	{
		if(i == id) continue;

		val.push_back({v[i], i});
	}

	sort(val.rbegin(), val.rend());

	for(int i = e - 1; i < n; i++)
	{
		v[val[i].s] --;
	}


	v[id] = (n - e + 1); 

	process();
}

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

	cin>>n>>a;

	for(int i = 1; i <= n; i++) cin>>v[i];

	process();

	cin>>q;

	for(int i = 1; i <= q; i++)
	{
		char c; int a, b;

		cin>>c>>a;

		if(c == 'F') cout<<ans[a]<<'\n';

		else
		{
			cin>>b;

			update(a, b);
		}
	}
}

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