oj.uz

Submission #280217

# Submission time Handle Problem Language Result Execution time Memory
280217 2020-08-22T15:00:48 Z super_j6 Cake (CEOI14_cake) C++14
92.5 / 100
 2000 ms 36812 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];
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 = 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 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 14 ms 580 KB Output is correct
5 Correct 34 ms 1804 KB Output is correct

Subtask #2
7.5 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1806 ms 4512 KB Output is correct
2 Correct 1440 ms 4472 KB Output is correct
3 Correct 1979 ms 4784 KB Output is correct
4 Correct 1791 ms 4512 KB Output is correct
5 Execution timed out 2081 ms 6392 KB Time limit exceeded
6 Correct 1645 ms 6312 KB Output is correct
7 Correct 1882 ms 6448 KB Output is correct
8 Correct 1634 ms 6324 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 15224 KB Output is correct
2 Correct 138 ms 15084 KB Output is correct
3 Correct 128 ms 15096 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 362 ms 35692 KB Output is correct
6 Correct 325 ms 35704 KB Output is correct
7 Correct 304 ms 35576 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 1192 KB Output is correct
2 Correct 119 ms 1532 KB Output is correct
3 Correct 285 ms 7892 KB Output is correct
4 Correct 229 ms 8060 KB Output is correct
5 Correct 396 ms 2100 KB Output is correct
6 Correct 524 ms 10872 KB Output is correct
7 Correct 580 ms 3676 KB Output is correct
8 Correct 866 ms 15736 KB Output is correct
9 Correct 1532 ms 36728 KB Output is correct
10 Correct 1124 ms 4600 KB Output is correct
11 Correct 1177 ms 7136 KB Output is correct
12 Correct 1433 ms 30528 KB Output is correct
13 Correct 1586 ms 36812 KB Output is correct