oj.uz

Submission #278888

# Submission time Handle Problem Language Result Execution time Memory
278888 2020-08-22T02:44:14 Z super_j6 Cake (CEOI14_cake) C++14
0 / 100
 1254 ms 27648 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, 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 2 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 Incorrect 1254 ms 5496 KB Output isn't correct
2 Correct 784 ms 2168 KB Output is correct
3 Incorrect 1072 ms 5772 KB Output isn't correct
4 Correct 794 ms 2424 KB Output is correct
5 Incorrect 1143 ms 7160 KB Output isn't correct
6 Correct 874 ms 7544 KB Output is correct
7 Incorrect 1103 ms 7476 KB Output isn't correct
8 Correct 802 ms 3452 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 10104 KB Output isn't correct
2 Correct 88 ms 9848 KB Output is correct
3 Correct 74 ms 9720 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 173 ms 22520 KB Output isn't correct
6 Incorrect 175 ms 22392 KB Output isn't correct
7 Correct 159 ms 21368 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 1144 KB Output isn't correct
2 Incorrect 73 ms 1272 KB Output isn't correct
3 Incorrect 134 ms 5400 KB Output isn't correct
4 Incorrect 130 ms 5368 KB Output isn't correct
5 Incorrect 215 ms 1916 KB Output isn't correct
6 Incorrect 249 ms 7544 KB Output isn't correct
7 Incorrect 288 ms 3320 KB Output isn't correct
8 Incorrect 529 ms 10744 KB Output isn't correct
9 Incorrect 867 ms 27648 KB Output isn't correct
10 Incorrect 711 ms 5368 KB Output isn't correct
11 Incorrect 699 ms 7800 KB Output isn't correct
12 Incorrect 831 ms 23544 KB Output isn't correct
13 Incorrect 837 ms 27512 KB Output isn't correct