Submission #62744

#	Time	Username	Problem	Language	Result	Execution time	Memory
62744		MatheusLealV	Cake (CEOI14_cake)	C++17	100 / 100	1402 ms	8508 KiB

cake

#include <bits/stdc++.h>
#define l (2*nod)
#define r (2*nod + 1)
#define mid ((a + b)/2)
#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, tree[4*N];

vector<int> best;

vector<pii> ini;

void upd(int nod, int a, int b, int i, int x)
{
	if(a == b) tree[nod] = x;

	else
	{
		if(i <= mid) upd(l, a, mid, i, x);

		else upd(r, mid + 1, b, i, x);

		tree[nod] = max(tree[l], tree[r]);
	}
}

int query(int nod, int a, int b, int i, int j)
{
	if(j < a or i > b) return 0;

	if(i <= a and j >= b) return tree[nod];

	return max(query(l, a, mid, i, j), query(r, mid + 1, b, i, j));
}

int findR(int nod, int a, int b, int i, int val)
{
	if(tree[nod] <= val or b <= i) return -1;

	if(a == b) return a;

	if(tree[l] > val)
	{
		int k = findR(l, a, mid, i, val);

		if(k >= 0) return k;
	}

	return findR(r, mid + 1, b, i, val);
}

int findL(int nod, int a, int b, int i, int val)
{
	if(tree[nod] <= val or a >= i) return -1;

	if(a == b) return a;

	if(tree[r] > val)
	{
		int k = findL(r, mid + 1, b, i, val);

		if(k >= 0) return k;
	}

	return findL(l, a, mid, i, val);
}

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;

		upd(1, 0, n, best[i], dx[best[i]]);
	}
}

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];

		upd(1, 0, n, 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);

	cin>>q;

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

		cin>>c>>x;

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

			add(x, y);
		}

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

				continue;
			}

			if(x < a)
			{
				int maior = query(1, 0, n, x, a - 1);

				int R = findR(1, 0, n, a, maior);

				if(R == -1) R = n + 1;

				int ans = (a - x) + (R - a) - 1;

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

			else
			{
				int maior = query(1, 0, n, a + 1, x), L = findL(1, 0, n, a, maior);

				if(L == -1) L = 0;

				int ans = (x - a) + (a - L) - 1;

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

Compilation message (stderr)

cake.cpp: In function 'void add(int, int)':
cake.cpp:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(aux.size() == k - 1 or i >= best.size()) break;
      ~~~~~~~~~~~^~~~~~~~
cake.cpp:82: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: 20 / 20
• Subtask 4: 50 / 50