oj.uz

Submission #57901

# Submission time Handle Problem Language Result Execution time Memory
57901 2018-07-16T13:43:16 Z MatheusLealV Cake (CEOI14_cake) C++17
10 / 100
 2000 ms 7476 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;

		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 2 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 2064 ms 908 KB Time limit exceeded
2 Execution timed out 2040 ms 1152 KB Time limit exceeded
3 Execution timed out 2077 ms 1152 KB Time limit exceeded
4 Execution timed out 2056 ms 1204 KB Time limit exceeded
5 Execution timed out 2056 ms 1552 KB Time limit exceeded
6 Execution timed out 2078 ms 1552 KB Time limit exceeded
7 Execution timed out 2067 ms 1572 KB Time limit exceeded
8 Execution timed out 2074 ms 1572 KB Time limit exceeded

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1238 ms 3876 KB Output is correct
2 Correct 1334 ms 3876 KB Output is correct
3 Correct 1259 ms 3876 KB Output is correct
4 Correct 3 ms 3876 KB Output is correct
5 Execution timed out 2077 ms 7256 KB Time limit exceeded
6 Execution timed out 2065 ms 7476 KB Time limit exceeded
7 Execution timed out 2075 ms 7476 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 7476 KB Time limit exceeded
2 Execution timed out 2073 ms 7476 KB Time limit exceeded
3 Execution timed out 2071 ms 7476 KB Time limit exceeded
4 Execution timed out 2072 ms 7476 KB Time limit exceeded
5 Execution timed out 2064 ms 7476 KB Time limit exceeded
6 Execution timed out 2069 ms 7476 KB Time limit exceeded
7 Execution timed out 2068 ms 7476 KB Time limit exceeded
8 Execution timed out 2066 ms 7476 KB Time limit exceeded
9 Execution timed out 2052 ms 7476 KB Time limit exceeded
10 Execution timed out 2057 ms 7476 KB Time limit exceeded
11 Execution timed out 2071 ms 7476 KB Time limit exceeded
12 Execution timed out 2051 ms 7476 KB Time limit exceeded
13 Execution timed out 2069 ms 7476 KB Time limit exceeded