oj.uz

Submission #58000

# Submission time Handle Problem Language Result Execution time Memory
58000 2018-07-16T15:31:17 Z MatheusLealV Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 18712 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, bit[N];

pii val[N];

void update_BIT(int pos, int val)
{
	/*if(val > 0) cout<<"COLOCA "<<pos<<"\n";

	else cout<<"REMOVE "<<pos<<"\n";*/

	for(int i = pos; i < N; i += (i&-i)) bit[i] += val;
}
 
int Find_kth(int x)
{
   int resp = 0;
 
 //   x--;
 
    for(int i = 20; i >= 0; i--)
    {
    	if(resp + (1<<i) >= N) continue;
 
		if(bit[resp + (1 << i)] <= x) 
			x -= bit[resp + (1 << i)], resp = resp + (1 << i);
    }
 
    return resp + 1;
}

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

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

	return sum;
}

int bserch(int x)
{
	int ini = 1, fim = n, mid, best = val[x].f;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(querybit(mid) <= x)
		{
			best = mid;

			ini = mid + 1;
		}

		else fim = mid - 1;
	}

	return best;
}

 
inline void process()
{
	int st = a, en = a, cnt = 1;
 
	ans[a] = 0;
 
	while(st > 1 or 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 ++;
	}
}

void query()
{
	int st = a, en = a, cnt = 1;
 
	ans[a] = 0;
 
	while(st > 1 or en < n)
	{ 
		if( (val[st - 1] > val[en + 1] and en < n) or st <= 1)
		{
			ans[en + 1] = cnt;
 
			en ++;
		}
 
		else ans[st - 1] = cnt, st --;
 
		cnt ++;
	}	
}

int esq[N], dir[N];
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
 
	cin>>n>>a;
 
	for(int i = 1; i <= n; i++) cin>>v[i], val[i] = {v[i], 0}, update_BIT(v[i], 1);
 
	query();
 
	cin>>q;
 
	for(int i = 1; i <= q; i++)
	{
		char c; int a, b;
 
		cin>>c>>a;
 
		if(c == 'F')
		{
			query();

			cout<<ans[a]<<"\n";
		}
 
		else
		{
			cin>>b;

			int kth = bserch(n - b + 1);

			int ant = val[a].f;
 
			val[a] = {kth, -i};

			//cout<<(n - b + 1)<<" KTH = "<<kth<<"\n";

			update_BIT(ant, -1);
 
			update_BIT(val[a].f, +1);
 		}
	}
}

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 Incorrect 205 ms 2584 KB Output isn't correct
2 Incorrect 200 ms 2816 KB Output isn't correct
3 Incorrect 159 ms 2816 KB Output isn't correct
4 Incorrect 160 ms 2936 KB Output isn't correct
5 Incorrect 258 ms 3152 KB Output isn't correct
6 Incorrect 291 ms 3368 KB Output isn't correct
7 Incorrect 339 ms 3428 KB Output isn't correct
8 Incorrect 189 ms 3664 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2011 ms 5852 KB Time limit exceeded
2 Execution timed out 2040 ms 6336 KB Time limit exceeded
3 Execution timed out 2047 ms 7036 KB Time limit exceeded
4 Incorrect 2 ms 7036 KB Output isn't correct
5 Execution timed out 2071 ms 11680 KB Time limit exceeded
6 Execution timed out 2055 ms 13236 KB Time limit exceeded
7 Execution timed out 2062 ms 14848 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 14848 KB Output isn't correct
2 Incorrect 464 ms 14848 KB Output isn't correct
3 Execution timed out 2064 ms 14848 KB Time limit exceeded
4 Execution timed out 2049 ms 14848 KB Time limit exceeded
5 Incorrect 565 ms 14848 KB Output isn't correct
6 Execution timed out 2044 ms 14848 KB Time limit exceeded
7 Execution timed out 2065 ms 14848 KB Time limit exceeded
8 Incorrect 948 ms 14848 KB Output isn't correct
9 Execution timed out 2045 ms 18556 KB Time limit exceeded
10 Incorrect 1287 ms 18556 KB Output isn't correct
11 Execution timed out 2063 ms 18556 KB Time limit exceeded
12 Execution timed out 2069 ms 18556 KB Time limit exceeded
13 Execution timed out 2033 ms 18712 KB Time limit exceeded