oj.uz

Submission #57904

# Submission time Handle Problem Language Result Execution time Memory
57904 2018-07-16T13:46:00 Z MatheusLealV Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 7400 KB 
#include <bits/stdc++.h>
#define N 250050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, a, v[N], ans[N], q;

int bit[N];

void upd(int x, int v)
{
	for(int i = x; i < N; i += (i&-i)) bit[i] += v;
}

int query(int x)
{
	int sum = 0;

	for(int i = x; i > 0 ;i -= (i&-i)) sum += bit[i];

	return sum;
}

inline void process()
{
	int st = a, en = a, cnt = 1;

	ans[a] = 0;

	while(st > 1 or en < n)
	{
		//cout<<st<<" "<<en<<'\n';

		if( (v[st - 1] > v[en + 1] and en < n) or st <= 1)
		{
			ans[en + 1] = cnt;

			en ++;
		}

		else ans[st - 1] = cnt, st --;

		cnt ++;
	}

	//for(int i = 1; i <= n; i++) cout<<ans[i]<<" \n"[i == n];
}

void update(int id, int e)
{
	vector<pii> val;

	for(int i = 1; i <= n; i++)
	{
		if(i == id) continue;

		if(v[i] <= (n - e + 1)) v[i] --;
	}

	v[id] = (n - e + 1); 

	process();
}

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

	cin>>n>>a;

	for(int i = 1; i <= n; i++) cin>>v[i];

	process();

	cin>>q;

	for(int i = 1; i <= q; i++)
	{
		char c; int a, b;

		cin>>c>>a;

		if(c == 'F') cout<<ans[a]<<'\n';

		else
		{
			cin>>b;

			update(a, b);
		}
	}
}

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 1320 KB Time limit exceeded
2 Execution timed out 2008 ms 2180 KB Time limit exceeded
3 Execution timed out 2021 ms 2828 KB Time limit exceeded
4 Execution timed out 2037 ms 3520 KB Time limit exceeded
5 Execution timed out 2044 ms 3920 KB Time limit exceeded
6 Execution timed out 2037 ms 4056 KB Time limit exceeded
7 Execution timed out 2061 ms 4236 KB Time limit exceeded
8 Execution timed out 2066 ms 4276 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 5456 KB Output is correct
2 Correct 67 ms 5476 KB Output is correct
3 Correct 65 ms 5476 KB Output is correct
4 Incorrect 2 ms 5476 KB Output isn't correct
5 Correct 120 ms 6768 KB Output is correct
6 Incorrect 157 ms 6936 KB Output isn't correct
7 Correct 111 ms 6936 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 247 ms 6936 KB Output isn't correct
2 Correct 414 ms 6936 KB Output is correct
3 Execution timed out 2047 ms 6936 KB Time limit exceeded
4 Execution timed out 2057 ms 6936 KB Time limit exceeded
5 Incorrect 437 ms 6936 KB Output isn't correct
6 Execution timed out 2063 ms 6936 KB Time limit exceeded
7 Execution timed out 2063 ms 6936 KB Time limit exceeded
8 Execution timed out 2048 ms 6936 KB Time limit exceeded
9 Execution timed out 2051 ms 6936 KB Time limit exceeded
10 Incorrect 1709 ms 6936 KB Output isn't correct
11 Execution timed out 2009 ms 6936 KB Time limit exceeded
12 Execution timed out 2070 ms 6936 KB Time limit exceeded
13 Execution timed out 2078 ms 7400 KB Time limit exceeded