oj.uz

Submission #280204

# Submission time Handle Problem Language Result Execution time Memory
280204 2020-08-22T14:56:59 Z super_j6 Cake (CEOI14_cake) C++14
100 / 100
 1852 ms 34296 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];
int f[m], v[m], b[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;
	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), l--, add(s2, l, l, r);
		else add(s1, r, r, i), r++, 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 = 0; i < m; i++) b[i] = ff(v[i]);
			for(int i = v[r] - v[l] - 2; i < n - 1;){
				if(b[l] > b[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 2 ms 360 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 12 ms 512 KB Output is correct
5 Correct 32 ms 1792 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1832 ms 1552 KB Output is correct
2 Correct 1230 ms 1680 KB Output is correct
3 Correct 1652 ms 1784 KB Output is correct
4 Correct 1519 ms 1684 KB Output is correct
5 Correct 1803 ms 3572 KB Output is correct
6 Correct 1445 ms 3628 KB Output is correct
7 Correct 1685 ms 3620 KB Output is correct
8 Correct 1852 ms 3620 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 13888 KB Output is correct
2 Correct 131 ms 13752 KB Output is correct
3 Correct 131 ms 13724 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 306 ms 33316 KB Output is correct
6 Correct 318 ms 33288 KB Output is correct
7 Correct 322 ms 33144 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 808 KB Output is correct
2 Correct 153 ms 1144 KB Output is correct
3 Correct 293 ms 7064 KB Output is correct
4 Correct 240 ms 7032 KB Output is correct
5 Correct 350 ms 956 KB Output is correct
6 Correct 453 ms 9260 KB Output is correct
7 Correct 457 ms 2168 KB Output is correct
8 Correct 897 ms 13304 KB Output is correct
9 Correct 1433 ms 34272 KB Output is correct
10 Correct 1120 ms 1712 KB Output is correct
11 Correct 1274 ms 4344 KB Output is correct
12 Correct 1435 ms 27788 KB Output is correct
13 Correct 1343 ms 34296 KB Output is correct