oj.uz

Submission #280139

# Submission time Handle Problem Language Result Execution time Memory
280139 2020-08-22T14:03:47 Z super_j6 Cake (CEOI14_cake) C++14
100 / 100
 1959 ms 41788 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;

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 : s2) 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 - 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);
	}
	
	//pr();
	
	cin >> q;
	
	int cnt = -2 * mxn;
	while(q--){
		char t;
		cin >> t;
		if(t == 'F'){
			int x;
			cin >> x;
			pii p = *s1.lower_bound({{x, 0}, 0});
			if(cnt > 90) cout << x << ": ";
			cout << (x < k ? p.s + p.f.s - x : p.s + x - p.f.f) << endl;
			cnt++;
		}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]);
			if(cnt > 94) cout << x << " " << v[m - 4] << endl;
			sort(v, v + m);
			
			l = find(v, v + m, k) - v;
			r = l-- + 1;
			
			if(cnt > 94) cout << v[l] << " " << v[r] << endl;
			
			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++;
				} 
				if(cnt > 94) cout << i << " " << v[l] << " " << v[r] << endl;
			}
			if(cnt > 94) pr();
		}
	}
	
	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 12 ms 512 KB Output is correct
5 Correct 34 ms 1936 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1778 ms 5920 KB Output is correct
2 Correct 1327 ms 6060 KB Output is correct
3 Correct 1795 ms 6056 KB Output is correct
4 Correct 1499 ms 6056 KB Output is correct
5 Correct 1879 ms 8440 KB Output is correct
6 Correct 1480 ms 8728 KB Output is correct
7 Correct 1959 ms 8568 KB Output is correct
8 Correct 1506 ms 8692 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 15608 KB Output is correct
2 Correct 137 ms 15480 KB Output is correct
3 Correct 123 ms 15480 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 304 ms 36648 KB Output is correct
6 Correct 328 ms 36720 KB Output is correct
7 Correct 307 ms 36576 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 1272 KB Output is correct
2 Correct 120 ms 1484 KB Output is correct
3 Correct 223 ms 8236 KB Output is correct
4 Correct 222 ms 8196 KB Output is correct
5 Correct 339 ms 2200 KB Output is correct
6 Correct 425 ms 11184 KB Output is correct
7 Correct 452 ms 3832 KB Output is correct
8 Correct 872 ms 16352 KB Output is correct
9 Correct 1489 ms 41788 KB Output is correct
10 Correct 1135 ms 5516 KB Output is correct
11 Correct 1174 ms 8696 KB Output is correct
12 Correct 1394 ms 34580 KB Output is correct
13 Correct 1382 ms 41688 KB Output is correct