oj.uz

Submission #280486

# Submission time Handle Problem Language Result Execution time Memory
280486 2020-08-22T20:14:36 Z super_j6 Cake (CEOI14_cake) C++14
100 / 100
 1078 ms 21060 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;
	
	int cnt = 0;
	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;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:59:6: warning: unused variable 'cnt' [-Wunused-variable]
   59 |  int cnt = 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 7 ms 512 KB Output is correct
5 Correct 18 ms 1152 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 4728 KB Output is correct
2 Correct 764 ms 1024 KB Output is correct
3 Correct 992 ms 4856 KB Output is correct
4 Correct 789 ms 4856 KB Output is correct
5 Correct 1078 ms 5880 KB Output is correct
6 Correct 883 ms 2048 KB Output is correct
7 Correct 1065 ms 6024 KB Output is correct
8 Correct 821 ms 6024 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 8164 KB Output is correct
2 Correct 73 ms 7416 KB Output is correct
3 Correct 74 ms 7544 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 171 ms 18040 KB Output is correct
6 Correct 169 ms 18040 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 69 ms 1024 KB Output is correct
2 Correct 70 ms 1120 KB Output is correct
3 Correct 123 ms 4372 KB Output is correct
4 Correct 125 ms 4344 KB Output is correct
5 Correct 221 ms 1912 KB Output is correct
6 Correct 223 ms 6136 KB Output is correct
7 Correct 257 ms 2936 KB Output is correct
8 Correct 489 ms 8568 KB Output is correct
9 Correct 824 ms 19580 KB Output is correct
10 Correct 650 ms 3704 KB Output is correct
11 Correct 650 ms 5240 KB Output is correct
12 Correct 768 ms 18332 KB Output is correct
13 Correct 791 ms 21060 KB Output is correct