oj.uz

Submission #280140

# Submission time Handle Problem Language Result Execution time Memory
280140 2020-08-22T14:06:07 Z super_j6 Cake (CEOI14_cake) C++14
100 / 100
 1806 ms 41664 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];
int f[m], v[m];
set<pii> s1, s2;

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

void add(set<pii> &s, 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 - (s == s1 && y < k) * (y + 1 - it->f.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 - (s == s1 && x > k) * (it->f.f + 1 - x)}), 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, b[k] = 0;
	s1.insert({{0, 0}, n});
	s1.insert({{k, k}, 0});
	s1.insert({{n + 1, n + 1}, n});
	s2.insert({{-1, -1}, n});
	for(int i = -1; i <= 1; i++) s2.insert({{k + i, k + i}, k - i});
	s2.insert({{n + 2, n + 2}, 0});
	
	for(int i = 1, l = k - 1, r = k + 1; i < n; i++){
		if(a[l] < a[r]) add(s1, l, l, i), b[l--] = i, add(s2, l, l, r);
		else add(s1, r, r, i), b[r++] = i, add(s2, r, r, l);
	}
	
	cin >> q;
	
	while(q--){
		char t;
		cin >> t;
		if(t == 'F'){
			int x;
			cin >> x;
			pii p = *s1.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] = s2.lower_bound({{x, 0}, 0})->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;
			
			for(int i = v[r] - v[l] - 2; i < n - 1;){
				if(ff(v[l]) > ff(v[r])){
					add(s1, v[l - 1] + 1, v[l], i += v[l] - v[l - 1]); 
					add(s2, v[l - 1], v[l] - 1, v[r]);
					l--;
				}else{
					add(s1, v[r], v[r + 1] - 1, i += v[r + 1] - v[r]); 
					add(s2, v[r] + 1, v[r + 1], v[l]);
					r++;
				} 
			}
		}
	}
	
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 13 ms 512 KB Output is correct
5 Correct 31 ms 1792 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1727 ms 6008 KB Output is correct
2 Correct 1298 ms 6060 KB Output is correct
3 Correct 1728 ms 6056 KB Output is correct
4 Correct 1503 ms 6112 KB Output is correct
5 Correct 1806 ms 8256 KB Output is correct
6 Correct 1451 ms 8720 KB Output is correct
7 Correct 1715 ms 8568 KB Output is correct
8 Correct 1389 ms 8696 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 15608 KB Output is correct
2 Correct 120 ms 15480 KB Output is correct
3 Correct 123 ms 15480 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 301 ms 36772 KB Output is correct
6 Correct 316 ms 36856 KB Output is correct
7 Correct 288 ms 36652 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 1272 KB Output is correct
2 Correct 116 ms 1484 KB Output is correct
3 Correct 216 ms 8184 KB Output is correct
4 Correct 218 ms 8184 KB Output is correct
5 Correct 333 ms 2040 KB Output is correct
6 Correct 414 ms 11128 KB Output is correct
7 Correct 530 ms 3708 KB Output is correct
8 Correct 1105 ms 16112 KB Output is correct
9 Correct 1472 ms 41512 KB Output is correct
10 Correct 1115 ms 5656 KB Output is correct
11 Correct 1123 ms 8612 KB Output is correct
12 Correct 1404 ms 34456 KB Output is correct
13 Correct 1569 ms 41664 KB Output is correct