oj.uz

Submission #280370

# Submission time Handle Problem Language Result Execution time Memory
280370 2020-08-22T16:58:40 Z super_j6 Cake (CEOI14_cake) C++14
100 / 100
 1074 ms 18680 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], b[m];
set<pii> s;
 
int ff(int x){
	return x < 1 || x > n ? -1 : find(f, f + m - 4, x) - f;
}
 
void add(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 - (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 - (x > k) * (it->f.f + 1 - x)}), it = s.erase(it);
	s.insert({{y, x}, v});
}
 
int qry(int x){
	pii p = *s.lower_bound({{x, 0}, 0});
	return p.s + (x < k ? p.f.s - x : x - p.f.f);
}
 
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;
	s.insert({{0, 0}, n}), s.insert({{k, k}, 0}), s.insert({{n + 1, n + 1}, n});
	
	for(int i = 1, l = k - 1, r = k + 1; i < n; i++){
		if(a[l] < a[r]) add(l, l, i), l--;
		else add(r, r, i), r++;
	}
	
	cin >> q;
	
	while(q--){
		char t;
		cin >> t;
		if(t == 'F'){
			int x;
			cin >> x;
			cout << qry(x) << endl;
		}else{
			int x, y;
			cin >> x >> y;
			y--;
			
			for(int i = ff(x); 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]);
			
			memcpy(b, f, sizeof(b));
			b[m - 3] = !count(f, f + m - 4, k) * k;
			b[m - 4] = x + ((x < k) - (x > k)) * (qry(x + (x < k) - (x > k)) + 2);
			b[m - 4] *= !count(f, f + m - 4, b[m - 4]);
			sort(b, b + m);
			
			for(int l = find(b, b + m, k) - b, r = l, i = b[++r] - b[--l] - 2; i < n - 1;){
				if(ff(b[l]) > ff(b[r])) add(b[l - 1] + 1, b[l], i += b[l] - b[l - 1]), l--;
				else add(b[r], b[r + 1] - 1, i += b[r + 1] - b[r]), r++;
			}
		}
	}
	
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 10 ms 384 KB Output is correct
5 Correct 18 ms 1024 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1062 ms 996 KB Output is correct
2 Correct 802 ms 1048 KB Output is correct
3 Correct 1038 ms 1144 KB Output is correct
4 Correct 810 ms 1148 KB Output is correct
5 Correct 1074 ms 2040 KB Output is correct
6 Correct 890 ms 2168 KB Output is correct
7 Correct 1045 ms 2168 KB Output is correct
8 Correct 815 ms 2272 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 7544 KB Output is correct
2 Correct 80 ms 7416 KB Output is correct
3 Correct 74 ms 7416 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 167 ms 17656 KB Output is correct
6 Correct 170 ms 17656 KB Output is correct
7 Correct 159 ms 17400 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 632 KB Output is correct
2 Correct 69 ms 888 KB Output is correct
3 Correct 126 ms 3832 KB Output is correct
4 Correct 130 ms 3832 KB Output is correct
5 Correct 218 ms 760 KB Output is correct
6 Correct 234 ms 5116 KB Output is correct
7 Correct 265 ms 1528 KB Output is correct
8 Correct 503 ms 7032 KB Output is correct
9 Correct 836 ms 18680 KB Output is correct
10 Correct 668 ms 1572 KB Output is correct
11 Correct 672 ms 3084 KB Output is correct
12 Correct 792 ms 15224 KB Output is correct
13 Correct 815 ms 18680 KB Output is correct