oj.uz

Submission #62744

# Submission time Handle Problem Language Result Execution time Memory
62744 2018-07-30T00:19:55 Z MatheusLealV Cake (CEOI14_cake) C++17
100 / 100
 1402 ms 8508 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 392 KB Output is correct
4 Correct 11 ms 392 KB Output is correct
5 Correct 26 ms 920 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1402 ms 920 KB Output is correct
2 Correct 1150 ms 996 KB Output is correct
3 Correct 1282 ms 996 KB Output is correct
4 Correct 1057 ms 1068 KB Output is correct
5 Correct 1386 ms 1468 KB Output is correct
6 Correct 1279 ms 1472 KB Output is correct
7 Correct 1144 ms 1472 KB Output is correct
8 Correct 961 ms 1472 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 3924 KB Output is correct
2 Correct 151 ms 3924 KB Output is correct
3 Correct 100 ms 3924 KB Output is correct
4 Correct 3 ms 3924 KB Output is correct
5 Correct 168 ms 7436 KB Output is correct
6 Correct 171 ms 7504 KB Output is correct
7 Correct 208 ms 7504 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 7504 KB Output is correct
2 Correct 83 ms 7504 KB Output is correct
3 Correct 133 ms 7504 KB Output is correct
4 Correct 148 ms 7504 KB Output is correct
5 Correct 166 ms 7504 KB Output is correct
6 Correct 288 ms 7504 KB Output is correct
7 Correct 268 ms 7504 KB Output is correct
8 Correct 440 ms 7504 KB Output is correct
9 Correct 1081 ms 8508 KB Output is correct
10 Correct 605 ms 8508 KB Output is correct
11 Correct 677 ms 8508 KB Output is correct
12 Correct 1086 ms 8508 KB Output is correct
13 Correct 952 ms 8508 KB Output is correct