oj.uz

Submission #280367

# Submission time Handle Problem Language Result Execution time Memory
280367 2020-08-22T16:50:34 Z super_j6 Cake (CEOI14_cake) C++14
100 / 100
 1067 ms 18696 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;
	
	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;
			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;
}

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 384 KB Output is correct
5 Correct 24 ms 1024 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1038 ms 1144 KB Output is correct
2 Correct 805 ms 1024 KB Output is correct
3 Correct 1028 ms 1144 KB Output is correct
4 Correct 808 ms 1144 KB Output is correct
5 Correct 1067 ms 2024 KB Output is correct
6 Correct 888 ms 2168 KB Output is correct
7 Correct 1047 ms 2168 KB Output is correct
8 Correct 811 ms 2168 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 7544 KB Output is correct
2 Correct 76 ms 7416 KB Output is correct
3 Correct 77 ms 7416 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 167 ms 17648 KB Output is correct
6 Correct 170 ms 17632 KB Output is correct
7 Correct 158 ms 17360 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 632 KB Output is correct
2 Correct 70 ms 768 KB Output is correct
3 Correct 126 ms 3832 KB Output is correct
4 Correct 135 ms 3832 KB Output is correct
5 Correct 214 ms 760 KB Output is correct
6 Correct 231 ms 5112 KB Output is correct
7 Correct 274 ms 1528 KB Output is correct
8 Correct 498 ms 7032 KB Output is correct
9 Correct 816 ms 18632 KB Output is correct
10 Correct 673 ms 1660 KB Output is correct
11 Correct 664 ms 3192 KB Output is correct
12 Correct 789 ms 15380 KB Output is correct
13 Correct 822 ms 18696 KB Output is correct