oj.uz

Submission #62736

# Submission time Handle Problem Language Result Execution time Memory
62736 2018-07-29T23:51:09 Z MatheusLealV Cake (CEOI14_cake) C++17
46.6667 / 100
 2000 ms 75480 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 560 KB Output is correct
3 Correct 4 ms 608 KB Output is correct
4 Correct 6 ms 608 KB Output is correct
5 Correct 28 ms 1032 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 5472 KB Output is correct
2 Correct 411 ms 10052 KB Output is correct
3 Correct 320 ms 14512 KB Output is correct
4 Correct 347 ms 18972 KB Output is correct
5 Correct 388 ms 23948 KB Output is correct
6 Correct 368 ms 29048 KB Output is correct
7 Correct 373 ms 33952 KB Output is correct
8 Correct 351 ms 38948 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 41344 KB Time limit exceeded
2 Execution timed out 2083 ms 42892 KB Time limit exceeded
3 Execution timed out 2051 ms 44460 KB Time limit exceeded
4 Correct 4 ms 44460 KB Output is correct
5 Execution timed out 2058 ms 48572 KB Time limit exceeded
6 Execution timed out 2065 ms 50100 KB Time limit exceeded
7 Execution timed out 2071 ms 52352 KB Time limit exceeded

Subtask #4
16.666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 52352 KB Output is correct
2 Correct 89 ms 52352 KB Output is correct
3 Correct 1052 ms 52352 KB Output is correct
4 Correct 877 ms 52352 KB Output is correct
5 Correct 168 ms 52376 KB Output is correct
6 Execution timed out 2071 ms 55336 KB Time limit exceeded
7 Correct 572 ms 55952 KB Output is correct
8 Correct 261 ms 59456 KB Output is correct
9 Execution timed out 2081 ms 64144 KB Time limit exceeded
10 Correct 471 ms 64672 KB Output is correct
11 Execution timed out 2064 ms 69168 KB Time limit exceeded
12 Execution timed out 2078 ms 72808 KB Time limit exceeded
13 Execution timed out 2094 ms 75480 KB Time limit exceeded