oj.uz

Submission #57898

# Submission time Handle Problem Language Result Execution time Memory
57898 2018-07-16T13:41:56 Z MatheusLealV Cake (CEOI14_cake) C++17
10 / 100
 2000 ms 4264 KB 
#include <bits/stdc++.h>
#define N 100050
#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;

		val.push_back({v[i], i});
	}

	sort(val.rbegin(), val.rend());

	for(int i = e - 1; i < n; i++)
	{
		v[val[i].s] --;
	}


	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 3 ms 376 KB Output is correct
2 Incorrect 2 ms 376 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 1164 KB Time limit exceeded
2 Execution timed out 2074 ms 1164 KB Time limit exceeded
3 Execution timed out 2057 ms 1164 KB Time limit exceeded
4 Execution timed out 2079 ms 1164 KB Time limit exceeded
5 Execution timed out 2073 ms 1728 KB Time limit exceeded
6 Execution timed out 2064 ms 1728 KB Time limit exceeded
7 Execution timed out 2074 ms 1728 KB Time limit exceeded
8 Execution timed out 2058 ms 1728 KB Time limit exceeded

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1199 ms 4196 KB Output is correct
2 Correct 1181 ms 4196 KB Output is correct
3 Correct 1173 ms 4196 KB Output is correct
4 Correct 2 ms 4196 KB Output is correct
5 Runtime error 14 ms 4196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 15 ms 4196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 24 ms 4196 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 4196 KB Time limit exceeded
2 Execution timed out 2064 ms 4196 KB Time limit exceeded
3 Execution timed out 2064 ms 4196 KB Time limit exceeded
4 Execution timed out 2066 ms 4196 KB Time limit exceeded
5 Execution timed out 2075 ms 4196 KB Time limit exceeded
6 Execution timed out 2062 ms 4196 KB Time limit exceeded
7 Execution timed out 2067 ms 4196 KB Time limit exceeded
8 Execution timed out 2073 ms 4264 KB Time limit exceeded
9 Runtime error 14 ms 4264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Execution timed out 2083 ms 4264 KB Time limit exceeded
11 Execution timed out 2085 ms 4264 KB Time limit exceeded
12 Runtime error 15 ms 4264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 15 ms 4264 KB Execution killed with signal 11 (could be triggered by violating memory limits)