Submission #276995

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
276995	2020-08-21T00:20:54 Z	super_j6	Cake (CEOI14_cake)	C++14	35 / 100	2000 ms	2960 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(i != x && 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

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	14 ms	384 KB	Output is correct
5	Correct	264 ms	604 KB	Output is correct

Subtask #2

0.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2072 ms	384 KB	Time limit exceeded
2	Execution timed out	2080 ms	384 KB	Time limit exceeded
3	Execution timed out	2031 ms	384 KB	Time limit exceeded
4	Execution timed out	2059 ms	384 KB	Time limit exceeded
5	Execution timed out	2062 ms	512 KB	Time limit exceeded
6	Execution timed out	2083 ms	512 KB	Time limit exceeded
7	Execution timed out	2082 ms	512 KB	Time limit exceeded
8	Execution timed out	2057 ms	512 KB	Time limit exceeded

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	86 ms	1768 KB	Output is correct
2	Correct	50 ms	1656 KB	Output is correct
3	Correct	51 ms	1532 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	136 ms	2900 KB	Output is correct
6	Correct	138 ms	2960 KB	Output is correct
7	Correct	93 ms	2680 KB	Output is correct

Subtask #4

0.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	408 ms	420 KB	Output is correct
2	Correct	649 ms	484 KB	Output is correct
3	Execution timed out	2020 ms	944 KB	Time limit exceeded
4	Execution timed out	2073 ms	952 KB	Time limit exceeded
5	Correct	790 ms	736 KB	Output is correct
6	Execution timed out	2051 ms	1036 KB	Time limit exceeded
7	Execution timed out	2078 ms	676 KB	Time limit exceeded
8	Execution timed out	2071 ms	1152 KB	Time limit exceeded
9	Execution timed out	2070 ms	2352 KB	Time limit exceeded
10	Execution timed out	2020 ms	1204 KB	Time limit exceeded
11	Execution timed out	2088 ms	772 KB	Time limit exceeded
12	Execution timed out	2058 ms	1968 KB	Time limit exceeded
13	Execution timed out	2082 ms	2348 KB	Time limit exceeded