Submission #276993

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
276993	2020-08-21T00:17:01 Z	super_j6	Cake (CEOI14_cake)	C++14	0 / 100	2000 ms	2940 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 = 250001;
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	2070 ms	760 KB	Time limit exceeded
2	Execution timed out	2083 ms	712 KB	Time limit exceeded
3	Execution timed out	2054 ms	760 KB	Time limit exceeded
4	Execution timed out	2074 ms	764 KB	Time limit exceeded
5	Execution timed out	2077 ms	896 KB	Time limit exceeded
6	Execution timed out	2095 ms	896 KB	Time limit exceeded
7	Execution timed out	2090 ms	896 KB	Time limit exceeded
8	Execution timed out	2097 ms	640 KB	Time limit exceeded

Subtask #3

0.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	81 ms	1912 KB	Output is correct
2	Correct	78 ms	1656 KB	Output is correct
3	Correct	57 ms	1528 KB	Output is correct
4	Incorrect	1 ms	288 KB	Output isn't correct
5	Correct	145 ms	2940 KB	Output is correct
6	Incorrect	128 ms	2940 KB	Output isn't correct
7	Incorrect	101 ms	2808 KB	Output isn't correct

Subtask #4

0.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	392 ms	668 KB	Output isn't correct
2	Incorrect	645 ms	504 KB	Output isn't correct
3	Execution timed out	2073 ms	1016 KB	Time limit exceeded
4	Execution timed out	2071 ms	1216 KB	Time limit exceeded
5	Incorrect	767 ms	1016 KB	Output isn't correct
6	Execution timed out	2073 ms	1168 KB	Time limit exceeded
7	Execution timed out	2058 ms	916 KB	Time limit exceeded
8	Execution timed out	2097 ms	1280 KB	Time limit exceeded
9	Execution timed out	2082 ms	2524 KB	Time limit exceeded
10	Execution timed out	2068 ms	1792 KB	Time limit exceeded
11	Execution timed out	2045 ms	772 KB	Time limit exceeded
12	Execution timed out	2080 ms	2088 KB	Time limit exceeded
13	Execution timed out	2093 ms	2424 KB	Time limit exceeded