oj.uz

답안 #57988

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57988 2018-07-16T15:17:41 Z MatheusLealV 케이크 (CEOI14_cake) C++17
0 / 100
 2000 ms 5948 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];

void update_BIT(int pos, int val)
{
	//cout<<"COLOCA "<<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;
}

 
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 ++;
	}
}

pii val[N];

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;


			//cout<<n - b + 1<<" th = "<<Find_kth(n - b + 1)<<"\n";

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

			val[a] = {kth, i};
			update_BIT(val[a].f, -1);

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

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 2 ms 524 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 139 ms 812 KB Output isn't correct
2 Correct 140 ms 872 KB Output is correct
3 Incorrect 149 ms 892 KB Output isn't correct
4 Correct 131 ms 892 KB Output is correct
5 Incorrect 164 ms 1232 KB Output isn't correct
6 Incorrect 200 ms 1232 KB Output isn't correct
7 Incorrect 195 ms 1252 KB Output isn't correct
8 Correct 150 ms 1252 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2059 ms 3016 KB Time limit exceeded
2 Execution timed out 2070 ms 3016 KB Time limit exceeded
3 Execution timed out 2060 ms 3016 KB Time limit exceeded
4 Incorrect 2 ms 3016 KB Output isn't correct
5 Execution timed out 2043 ms 5904 KB Time limit exceeded
6 Execution timed out 2041 ms 5904 KB Time limit exceeded
7 Execution timed out 2057 ms 5904 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 382 ms 5904 KB Output isn't correct
2 Incorrect 681 ms 5904 KB Output isn't correct
3 Execution timed out 2032 ms 5904 KB Time limit exceeded
4 Execution timed out 2060 ms 5904 KB Time limit exceeded
5 Incorrect 509 ms 5904 KB Output isn't correct
6 Execution timed out 2049 ms 5904 KB Time limit exceeded
7 Execution timed out 2066 ms 5904 KB Time limit exceeded
8 Incorrect 620 ms 5904 KB Output isn't correct
9 Execution timed out 2021 ms 5904 KB Time limit exceeded
10 Incorrect 1569 ms 5904 KB Output isn't correct
11 Execution timed out 2066 ms 5904 KB Time limit exceeded
12 Execution timed out 2072 ms 5904 KB Time limit exceeded
13 Execution timed out 2069 ms 5948 KB Time limit exceeded