oj.uz

Submission #280197

# Submission time Handle Problem Language Result Execution time Memory
280197 2020-08-22T14:52:17 Z super_j6 Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 24952 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <set>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define pii pair<pi, pi>
#define f first
#define s second

const int mxn = 250002, m = 14;
int n, k, q;
int a[mxn];
int f[m], v[m];
set<pii> s;

int ff(int x){
	return x < 1 || x > n ? -1 : find(f, f + m - 4, x) - f;
}

void add(int x, int y, int v, int w){
	auto it = s.lower_bound({{y + 1, 0}, {0, 0}});
	if(it->f.s <= y) s.insert({{it->f.f, y + 1}, {it->s.f - (y < k) * (y + 1 - it->f.s), it->s.s}}), it = s.erase(it);
	while((--it)->f.s >= x) it = s.erase(it);
	if(it->f.f >= x) s.insert({{x - 1, it->f.s}, {it->s.f - (x > k) * (it->f.f + 1 - x), it->s.s}}), it = s.erase(it);
	s.insert({{y, x}, {v, w}});
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		f[m - 3] = i;
		for(int j = m - 4; ~j; j--) if(a[f[j]] < a[f[j + 1]]) swap(f[j], f[j + 1]);
	} 
	
	a[0] = a[n + 1] = f[m - 1] = n + 1;
	s.insert({{0, 0}, {n, n + 1}});
	s.insert({{k, k}, {0, k}});
	s.insert({{n + 1, n + 1}, {n, 0}});
	
	for(int i = 1, l = k - 1, r = k + 1, lw  = r, rw = l; i < n; i++){
		if(a[l] < a[r]) add(l, l, i, lw), l--, lw = r;
		else add(r, r, i, rw), r++, rw = l;
	}
	
	cin >> q;
	
	while(q--){
		char t;
		cin >> t;
		if(t == 'F'){
			int x;
			cin >> x;
			pii p = *s.lower_bound({{x, 0}, {0, 0}});
			cout << (x < k ? p.s.f + p.f.s - x : p.s.f + x - p.f.f) << endl;
		}else{
			int x, y;
			cin >> x >> y;
			y--;
			
			int z = ff(x);
			if(z != m) for(int i = z; i < m - 3; i++) swap(f[i], f[i + 1]);
			
			f[m - 3] = x;
			for(int i = m - 4; i >= y; i--) swap(f[i], f[i + 1]);
			
			int l = 0, r = n + 1;
			for(int i = 0; i < m - 4; i++){
				if(f[i] < k) l = max(l, f[i]);
				if(f[i] > k) r = min(r, f[i]);
			}
			
			memcpy(v, f, sizeof(v));
			v[m - 3] = !count(f, f + m - 4, k) * k;
			v[m - 4] = s.lower_bound({{x, 0}, {0, 0}})->s.s;
			v[m - 4] *= !count(f, f + m - 4, v[m - 4]);
			sort(v, v + m);
			
			l = find(v, v + m, k) - v;
			r = l-- + 1;
			
			int lw = s.lower_bound({{v[l], 0}, {0, 0}})->s.s;
			int rw = s.lower_bound({{v[r], 0}, {0, 0}})->s.s;
			for(int i = v[r] - v[l] - 2; i < n - 1;){
				if(ff(v[l]) > ff(v[r])){
					add(v[l], v[l], ++i, lw);
					if(v[l - 1] < v[l] - 1) add(v[l - 1] + 1, v[l] - 1, i += v[l] - v[l - 1] - 1, lw = v[r]); 
					l--;
				}else{
					add(v[r], v[r], ++i, rw);
					if(v[r] + 1 < v[r + 1]) add(v[r] + 1, v[r + 1] - 1, i += v[r + 1] - v[r] - 1, rw = v[l]); 
					r++;
				} 
			}
		}
	}
	
	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 2072 ms 5328 KB Time limit exceeded
2 Correct 1408 ms 5388 KB Output is correct
3 Execution timed out 2079 ms 5260 KB Time limit exceeded
4 Correct 990 ms 5396 KB Output is correct
5 Execution timed out 2053 ms 6488 KB Time limit exceeded
6 Correct 1873 ms 7032 KB Output is correct
7 Execution timed out 2028 ms 6900 KB Time limit exceeded
8 Correct 915 ms 7032 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 8952 KB Output isn't correct
2 Correct 81 ms 8824 KB Output is correct
3 Correct 76 ms 8824 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 181 ms 20088 KB Output isn't correct
6 Incorrect 185 ms 20088 KB Output isn't correct
7 Correct 163 ms 19832 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 1016 KB Output isn't correct
2 Incorrect 124 ms 1144 KB Output isn't correct
3 Incorrect 211 ms 4856 KB Output isn't correct
4 Incorrect 227 ms 4856 KB Output isn't correct
5 Incorrect 371 ms 1912 KB Output isn't correct
6 Incorrect 409 ms 6912 KB Output isn't correct
7 Incorrect 490 ms 3192 KB Output isn't correct
8 Incorrect 902 ms 9464 KB Output isn't correct
9 Incorrect 1485 ms 24864 KB Output isn't correct
10 Incorrect 1248 ms 5324 KB Output isn't correct
11 Incorrect 1197 ms 7288 KB Output isn't correct
12 Incorrect 1325 ms 21152 KB Output isn't correct
13 Incorrect 1287 ms 24952 KB Output isn't correct