oj.uz

Submission #280488

# Submission time Handle Problem Language Result Execution time Memory
280488 2020-08-22T20:17:28 Z super_j6 Cake (CEOI14_cake) C++14
100 / 100
 1065 ms 18844 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 find(f, f + m, 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 - 1] = i;
		for(int j = m - 2; ~-j; j--) if(a[f[j]] < a[f[j + 1]]) swap(f[j], f[j + 1]);
	} 
	
	a[0] = a[n + 1] = f[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;
			
			for(int i = ff(x); i < m - 1; i++) swap(f[i], f[i + 1]);
			
			f[m - 1] = x, y++;
			for(int i = m - 2; i >= y; i--) swap(f[i], f[i + 1]);
			
			memcpy(b, f, sizeof(b));
			b[m - 1] = !count(f, f + m - 2, k) * k;
			b[m - 2] = x + ((x < k) - (x > k)) * (qry(x + (x < k) - (x > k)) + 2);
			b[m - 2] *= !count(f, f + m - 2, b[m - 2]);
			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 1 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 9 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 1027 ms 984 KB Output is correct
2 Correct 763 ms 1048 KB Output is correct
3 Correct 1020 ms 1048 KB Output is correct
4 Correct 812 ms 1144 KB Output is correct
5 Correct 1065 ms 2040 KB Output is correct
6 Correct 893 ms 2168 KB Output is correct
7 Correct 1033 ms 2052 KB Output is correct
8 Correct 793 ms 2168 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 7548 KB Output is correct
2 Correct 73 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 166 ms 17656 KB Output is correct
6 Correct 168 ms 17656 KB Output is correct
7 Correct 158 ms 17400 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 640 KB Output is correct
2 Correct 67 ms 768 KB Output is correct
3 Correct 123 ms 3832 KB Output is correct
4 Correct 127 ms 4088 KB Output is correct
5 Correct 195 ms 760 KB Output is correct
6 Correct 231 ms 5240 KB Output is correct
7 Correct 256 ms 1556 KB Output is correct
8 Correct 493 ms 7032 KB Output is correct
9 Correct 811 ms 18820 KB Output is correct
10 Correct 648 ms 1788 KB Output is correct
11 Correct 639 ms 3192 KB Output is correct
12 Correct 770 ms 15480 KB Output is correct
13 Correct 789 ms 18844 KB Output is correct