Submission #58002

#	Time	Username	Problem	Language	Result	Execution time	Memory
58002		MatheusLealV	Cake (CEOI14_cake)	C++17	0 / 100	2084 ms	5888 KiB

cake

#include <bits/stdc++.h>
#define N 250050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
 
int n, a, v[N], ans[N], q, bit[N];

pii val[N];

void update_BIT(int pos, int val)
{
	/*if(val > 0) cout<<"COLOCA "<<pos<<"\n";

	else cout<<"REMOVE "<<pos<<"\n";*/

	for(int i = pos; i < N; i += (i&-i)) bit[i] += val;
}
 
int Find_kth(int x)
{
   int resp = 0;
 
 //   x--;
 
    for(int i = 20; i >= 0; i--)
    {
    	if(resp + (1<<i) >= N) continue;
 
		if(bit[resp + (1 << i)] <= x) 
			x -= bit[resp + (1 << i)], resp = resp + (1 << i);
    }
 
    return resp + 1;
}

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

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

	return sum;
}

int bserch(int x)
{
	int ini = 1, fim = n, mid, best = n;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(querybit(mid) <= x)
		{
			best = mid;

			ini = mid + 1;
		}

		else fim = mid - 1;
	}

	return best;
}

 
inline void process()
{
	int st = a, en = a, cnt = 1;
 
	ans[a] = 0;
 
	while(st > 1 or 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 ++;
	}
}

void query()
{
	int st = a, en = a, cnt = 1;
 
	ans[a] = 0;
 
	while(st > 1 or en < n)
	{ 
		if( (val[st - 1] > val[en + 1] and en < n) or st <= 1)
		{
			ans[en + 1] = cnt;
 
			en ++;
		}
 
		else ans[st - 1] = cnt, st --;
 
		cnt ++;
	}	
}

int esq[N], dir[N];
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
 
	cin>>n>>a;
 
	for(int i = 1; i <= n; i++) cin>>v[i], val[i] = {v[i], 0}, update_BIT(v[i], 1);
 
	query();
 
	cin>>q;
 
	for(int i = 1; i <= q; i++)
	{
		char c; int a, b;
 
		cin>>c>>a;
 
		if(c == 'F')
		{
			query();

			cout<<ans[a]<<"\n";
		}
 
		else
		{
			cin>>b;

			int kth = bserch(n - b + 1);

			int ant = val[a].f;
 
			val[a] = {kth, -i};

			//cout<<(n - b + 1)<<" KTH = "<<kth<<"\n";

			update_BIT(ant, -1);
 
			update_BIT(val[a].f, +1);
 		}
	}
}

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