Submission #276994

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
276994	2020-08-21T00:17:55 Z	super_j6	Cake (CEOI14_cake)	C++14	0 / 100	2000 ms	2992 KB

cake

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 250002;
int n, k, q;
int a[mxn], b[mxn];

void sol(){
	b[k] = 0;
	for(int i = 1, l = k - 1, r = k + 1; i < n; i++){
		if(a[l] < a[r]) b[l--] = i;
		else b[r++] = i;
	}
}

void pr(){
	for(int i = 1; i <= n; i++) cout << a[i] << " ";
	cout << endl;
	for(int i = 1; i <= n; i++) cout << b[i] << " ";
	cout << endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i]--;
	} 
	a[0] = a[n + 1] = n;
	
	sol();
	//pr();
	
	cin >> q;
	
	while(q--){
		char t;
		cin >> t;
		if(t == 'F'){
			int x;
			cin >> x;
			cout << b[x] << endl;
		}else{
			int x, y;
			cin >> x >> y;
			y = n - y;
			for(int i = 1; i <= n; i++){
				if(a[i] >= min(a[x], y) && a[i] <= max(a[x], y)){
					a[i] += 2 * (a[x] > y) - 1;
				}
			}
			a[x] = y;
			//pr();
			sol();
		}
	}

	return 0;
}

Subtask #1

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Incorrect	1 ms	384 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	2076 ms	384 KB	Time limit exceeded
2	Execution timed out	2080 ms	384 KB	Time limit exceeded
3	Execution timed out	2058 ms	384 KB	Time limit exceeded
4	Execution timed out	2093 ms	384 KB	Time limit exceeded
5	Execution timed out	2079 ms	512 KB	Time limit exceeded
6	Execution timed out	2083 ms	512 KB	Time limit exceeded
7	Execution timed out	2090 ms	512 KB	Time limit exceeded
8	Execution timed out	2082 ms	512 KB	Time limit exceeded

Subtask #3

0.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	1784 KB	Output is correct
2	Correct	52 ms	1656 KB	Output is correct
3	Correct	48 ms	1532 KB	Output is correct
4	Incorrect	0 ms	384 KB	Output isn't correct
5	Correct	137 ms	2992 KB	Output is correct
6	Incorrect	127 ms	2936 KB	Output isn't correct
7	Correct	90 ms	2876 KB	Output is correct

Subtask #4

0.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	388 ms	504 KB	Output isn't correct
2	Incorrect	638 ms	504 KB	Output isn't correct
3	Execution timed out	2098 ms	768 KB	Time limit exceeded
4	Execution timed out	2098 ms	768 KB	Time limit exceeded
5	Incorrect	775 ms	888 KB	Output isn't correct
6	Execution timed out	2064 ms	1164 KB	Time limit exceeded
7	Execution timed out	2078 ms	912 KB	Time limit exceeded
8	Execution timed out	2075 ms	1152 KB	Time limit exceeded
9	Execution timed out	2078 ms	2348 KB	Time limit exceeded
10	Execution timed out	2080 ms	1344 KB	Time limit exceeded
11	Execution timed out	2083 ms	844 KB	Time limit exceeded
12	Execution timed out	2070 ms	2084 KB	Time limit exceeded
13	Execution timed out	2073 ms	2468 KB	Time limit exceeded