oj.uz

Submission #280390

# Submission time Handle Problem Language Result Execution time Memory
280390 2020-08-22T17:12:48 Z super_j6 Cake (CEOI14_cake) C++14
100 / 100
 1051 ms 18808 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 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 1033 ms 992 KB Output is correct
2 Correct 785 ms 1024 KB Output is correct
3 Correct 1004 ms 1024 KB Output is correct
4 Correct 813 ms 1144 KB Output is correct
5 Correct 1051 ms 1920 KB Output is correct
6 Correct 906 ms 2048 KB Output is correct
7 Correct 1032 ms 2168 KB Output is correct
8 Correct 805 ms 2060 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 7636 KB Output is correct
2 Correct 76 ms 7416 KB Output is correct
3 Correct 75 ms 7432 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 193 ms 17692 KB Output is correct
6 Correct 195 ms 17656 KB Output is correct
7 Correct 187 ms 17400 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 632 KB Output is correct
2 Correct 70 ms 768 KB Output is correct
3 Correct 144 ms 3960 KB Output is correct
4 Correct 129 ms 3832 KB Output is correct
5 Correct 201 ms 760 KB Output is correct
6 Correct 225 ms 5240 KB Output is correct
7 Correct 260 ms 1528 KB Output is correct
8 Correct 481 ms 7032 KB Output is correct
9 Correct 811 ms 18808 KB Output is correct
10 Correct 652 ms 1580 KB Output is correct
11 Correct 640 ms 3196 KB Output is correct
12 Correct 771 ms 15352 KB Output is correct
13 Correct 781 ms 18680 KB Output is correct