Submission #62736

#	Time	Username	Problem	Language	Result	Execution time	Memory
62736		MatheusLealV	Cake (CEOI14_cake)	C++17	46.67 / 100	2094 ms	75480 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, q, a, v[N], dx[N], soma;

vector<int> best;

vector<pii> ini;

void add(int x, int k)
{
	vector<int> aux;

	int id = 0;

	for(int i = 0; ;i++)
	{
		id = i;

		if(aux.size() == k - 1 or i >= best.size()) break;

		if(best[i] != x) aux.push_back(best[i]);
	}

	aux.push_back(x);

	for(int j = id; j < min(15, (int)best.size()); j++)
		if(best[j] != x) aux.push_back(best[j]);

	best = aux;

	for(int i = best.size() - 2; i >= 0; i--)
		dx[best[i]] = dx[best[i + 1]] + 1;
}

void print()
{
	for(auto x: best) cout<<x<<" ";

	cout<<"\n";
}

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

	cin>>n>>a;

	for(int i = 1; i <= n; i++) cin>>v[i], ini.push_back({-v[i], i}), dx[i] = v[i];

	sort(ini.begin(), ini.end());

	for(int i = 0; i < min(15, (int) ini.size()); i++) best.push_back(ini[i].s);

	best.push_back(0);

	//for(auto x: best) cout<<x<<"\n";

	cin>>q;

	for(int i = 0; i < q; i++)
	{
		char c; int x, y;

		//print();

		//for(int x = 1; x <= n; x++) cout<<dx[x] + soma<<" \n"[x == n];

		//if(i == q) break;

		cin>>c>>x;

		if(c == 'E')
		{
			cin>>y;

			add(x, y);
		}

		else
		{
			if(a == x)
			{
				cout<<"0\n";

				continue;
			}

			int maior = 0;

			for(int i = min(a, x); i <= max(a, x); i++) if(i != a) maior = max(maior, dx[i]);

			if(x < a)
			{
				int ans = a - x;

				for(int j = a + 1; j <= n; j++)
				{
					if(dx[j] > maior) break;

					ans ++;
				}

				cout<<ans<<"\n";
			}

			else
			{
				int ans = x - a;

				for(int j = a - 1; j >= 1; j--)
				{
					if(dx[j] > maior) break;
					
					ans ++;
				}

				cout<<ans<<"\n";
			}
		}
		
	}
}

Compilation message (stderr)

cake.cpp: In function 'void add(int, int)':
cake.cpp:24:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(aux.size() == k - 1 or i >= best.size()) break;
      ~~~~~~~~~~~^~~~~~~~
cake.cpp:24:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(aux.size() == k - 1 or i >= best.size()) break;
                             ~~^~~~~~~~~~~~~~

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