oj.uz

Submission #58002

# Submission time Handle Problem Language Result Execution time Memory
58002 2018-07-16T15:32:02 Z MatheusLealV Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 5888 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 = n;

	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 165 ms 740 KB Output isn't correct
2 Incorrect 207 ms 740 KB Output isn't correct
3 Incorrect 172 ms 984 KB Output isn't correct
4 Incorrect 145 ms 984 KB Output isn't correct
5 Incorrect 185 ms 1212 KB Output isn't correct
6 Incorrect 191 ms 1212 KB Output isn't correct
7 Incorrect 230 ms 1212 KB Output isn't correct
8 Incorrect 179 ms 1212 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2051 ms 2768 KB Time limit exceeded
2 Execution timed out 2062 ms 2900 KB Time limit exceeded
3 Execution timed out 2033 ms 2900 KB Time limit exceeded
4 Incorrect 2 ms 2900 KB Output isn't correct
5 Execution timed out 2062 ms 5748 KB Time limit exceeded
6 Execution timed out 2063 ms 5888 KB Time limit exceeded
7 Execution timed out 2066 ms 5888 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 259 ms 5888 KB Output isn't correct
2 Incorrect 608 ms 5888 KB Output isn't correct
3 Execution timed out 2054 ms 5888 KB Time limit exceeded
4 Execution timed out 2077 ms 5888 KB Time limit exceeded
5 Incorrect 375 ms 5888 KB Output isn't correct
6 Execution timed out 2084 ms 5888 KB Time limit exceeded
7 Execution timed out 2070 ms 5888 KB Time limit exceeded
8 Incorrect 865 ms 5888 KB Output isn't correct
9 Execution timed out 2077 ms 5888 KB Time limit exceeded
10 Incorrect 1340 ms 5888 KB Output isn't correct
11 Execution timed out 2065 ms 5888 KB Time limit exceeded
12 Execution timed out 2078 ms 5888 KB Time limit exceeded
13 Execution timed out 2033 ms 5888 KB Time limit exceeded