oj.uz

Submission #280222

# Submission time Handle Problem Language Result Execution time Memory
280222 2020-08-22T15:03:00 Z super_j6 Cake (CEOI14_cake) C++14
100 / 100
 1928 ms 39880 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 12 ms 512 KB Output is correct
5 Correct 31 ms 1664 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1834 ms 1556 KB Output is correct
2 Correct 1294 ms 1784 KB Output is correct
3 Correct 1721 ms 1676 KB Output is correct
4 Correct 1928 ms 1688 KB Output is correct
5 Correct 1894 ms 3832 KB Output is correct
6 Correct 1459 ms 3624 KB Output is correct
7 Correct 1848 ms 3616 KB Output is correct
8 Correct 1602 ms 3628 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 13816 KB Output is correct
2 Correct 122 ms 13752 KB Output is correct
3 Correct 130 ms 13664 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 319 ms 33272 KB Output is correct
6 Correct 352 ms 33784 KB Output is correct
7 Correct 302 ms 35420 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 1272 KB Output is correct
2 Correct 117 ms 1444 KB Output is correct
3 Correct 223 ms 7940 KB Output is correct
4 Correct 219 ms 7928 KB Output is correct
5 Correct 361 ms 2004 KB Output is correct
6 Correct 436 ms 10968 KB Output is correct
7 Correct 525 ms 3680 KB Output is correct
8 Correct 902 ms 15468 KB Output is correct
9 Correct 1582 ms 39088 KB Output is correct
10 Correct 1149 ms 4788 KB Output is correct
11 Correct 1126 ms 8084 KB Output is correct
12 Correct 1512 ms 33684 KB Output is correct
13 Correct 1702 ms 39880 KB Output is correct