oj.uz

Submission #62742

# Submission time Handle Problem Language Result Execution time Memory
62742 2018-07-30T00:17:34 Z MatheusLealV Cake (CEOI14_cake) C++17
0 / 100
 1002 ms 19476 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);

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

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 928 ms 860 KB Output is correct
2 Incorrect 799 ms 860 KB Output isn't correct
3 Correct 853 ms 1036 KB Output is correct
4 Incorrect 765 ms 1044 KB Output isn't correct
5 Correct 938 ms 1304 KB Output is correct
6 Incorrect 943 ms 1336 KB Output isn't correct
7 Correct 899 ms 1532 KB Output is correct
8 Incorrect 834 ms 1532 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 3864 KB Output is correct
2 Incorrect 92 ms 3864 KB Output isn't correct
3 Incorrect 86 ms 3864 KB Output isn't correct
4 Incorrect 2 ms 3864 KB Output isn't correct
5 Incorrect 159 ms 7748 KB Output isn't correct
6 Correct 157 ms 7872 KB Output is correct
7 Incorrect 137 ms 7872 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 7872 KB Output isn't correct
2 Correct 61 ms 7872 KB Output is correct
3 Correct 125 ms 7872 KB Output is correct
4 Incorrect 125 ms 7872 KB Output isn't correct
5 Incorrect 164 ms 7872 KB Output isn't correct
6 Correct 241 ms 7872 KB Output is correct
7 Correct 241 ms 7872 KB Output is correct
8 Incorrect 445 ms 7872 KB Output isn't correct
9 Incorrect 1002 ms 12476 KB Output isn't correct
10 Incorrect 535 ms 12476 KB Output isn't correct
11 Correct 683 ms 12476 KB Output is correct
12 Correct 981 ms 14572 KB Output is correct
13 Incorrect 813 ms 19476 KB Output isn't correct