Submission #278888

#	Time	Username	Problem	Language	Result	Execution time	Memory
278888		super_j6	Cake (CEOI14_cake)	C++14	0 / 100	1254 ms	27648 KiB

cake

#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, int>
#define f first
#define s second

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

void pr(){
	for(int i = 0; i < m; i++) cout << f[i] << " ";
	cout << endl;
	for(int i = 0; i < m; i++) cout << v[i] << " ";
	cout << endl;
	for(pii i : s) cout << i.f.s << " " << i.f.f << " " << i.s << endl;
	cout << endl;
}

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

void add(int x, int y, int v){
	auto it = s.lower_bound({{y + 1, 0}, 0});
	if(it->f.s <= y) s.insert({{it->f.f, y + 1}, it->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}), it = s.erase(it);
	s.insert({{y, x}, v});
}

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});
	s.insert({{k, k}, 0});
	s.insert({{n + 1, n + 1}, n});
	
	b[k] = d[k - 1] = d[k + 1] = 0, c[k - 1] = k + 1, c[k + 1] = k - 1;
	for(int i = 1, l = k - 1, r = k + 1; i < n; i++){
		if(a[l] < a[r]) add(l, l, i), b[l--] = i, c[l] = r, d[l] = i;
		else add(r, r, i), b[r++] = i, c[r] = l, d[r] = i;
	}
	
	//pr();
	
	cin >> q;
	
	while(q--){
		char t;
		cin >> t;
		if(t == 'F'){
			int x;
			cin >> x;
			pii p = *s.lower_bound({{x, 0}, 0});
			cout << (x < k ? p.s + p.f.s - x : p.s + 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] = (d[l] != d[r]) * (d[l] < d[r] ? c[l] : c[r]);
			v[m - 4] *= v[m - 4] != k && !count(f, f + m - 4, v[m - 4]);
			sort(v, v + m);
			
			l = find(v, v + m, k) - v;
			r = l-- + 1;
			
			//cout << v[l] << " " << v[r] << endl;
			//pr();
			
			for(int i = max(d[v[l]], d[v[r]]); i < n - 1;){
				if(ff(v[l]) > ff(v[r])) add(v[l - 1] + 1, v[l], i += v[l] - v[l - 1]), l--;
				else add(v[r], v[r + 1] - 1, i += v[r + 1] - v[r]), r++;
				//cout << i << " " << v[l] << " " << v[r] << endl;
			}
			//pr();
		}
	}
	
	return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50