oj.uz

Submission #280302

# Submission time Handle Problem Language Result Execution time Memory
280302 2020-08-22T15:43:13 Z super_j6 Cake (CEOI14_cake) C++14
100 / 100
 1030 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, pi>
#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, int w){
	auto it = s.lower_bound({{y + 1, 0}, {0, 0}});
	if(it->f.s <= y) s.insert({{it->f.f, y + 1}, {it->s.f - (y < k) * (y + 1 - it->f.s), it->s.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.f - (x > k) * (it->f.f + 1 - x), it->s.s}}), it = s.erase(it);
	s.insert({{y, x}, {v, w}});
}
 
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, n + 1}});
	s.insert({{k, k}, {0, k}});
	s.insert({{n + 1, n + 1}, {n, 0}});
	
	for(int i = 1, l = k - 1, r = k + 1; i < n; i++){
		if(a[l] < a[r]) add(l, l, i, r), l--;
		else add(r, r, i, l), r++;
	}
	
	cin >> q;
	
	int cnt = 0;
	while(q--){
		char t;
		cin >> t;
		if(t == 'F'){
			int x;
			cin >> x;
			pii p = *s.lower_bound({{x, 0}, {0, 0}});
			cout << (x < k ? p.s.f + p.f.s - x : p.s.f + x - p.f.f) << endl;
		}else{
			int x, y;
			cin >> x >> y;
			y--;
			
			int z = ff(x);
			if(z != m) for(int i = z; 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]);
			
			int l = 0, r = n + 1;
			for(int i = 0; i < m - 4; i++){
				if(f[i] < k) l = max(l, f[i]);
				if(f[i] > k) r = min(r, f[i]);
			}
			
			memcpy(b, f, sizeof(b));
			b[m - 3] = !count(f, f + m - 4, k) * k;
			b[m - 4] = s.lower_bound({{x + (x < k) - (x > k), 0}, {0, 0}})->s.s;
			if(b[m - 4] == k) b[m - 4] += (x < k) - (x > k);
			b[m - 4] *= !count(f, f + m - 4, b[m - 4]);
			sort(b, b + m);
			
			l = lower_bound(b, b + m, k) - b;
			r = l-- + 1;
			
			for(int 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], b[r]), l--;
				else add(b[r], b[r + 1] - 1, i += b[r + 1] - b[r], b[l]), r++;
			}
		}
	}
	
	return 0;
}

Compilation message

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1006 ms 896 KB Output is correct
2 Correct 746 ms 1144 KB Output is correct
3 Correct 988 ms 1144 KB Output is correct
4 Correct 776 ms 1144 KB Output is correct
5 Correct 1030 ms 2040 KB Output is correct
6 Correct 865 ms 2056 KB Output is correct
7 Correct 1010 ms 2048 KB Output is correct
8 Correct 772 ms 2048 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 7572 KB Output is correct
2 Correct 79 ms 7416 KB Output is correct
3 Correct 75 ms 7416 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 169 ms 17656 KB Output is correct
6 Correct 171 ms 17656 KB Output is correct
7 Correct 163 ms 17400 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 640 KB Output is correct
2 Correct 68 ms 768 KB Output is correct
3 Correct 131 ms 3832 KB Output is correct
4 Correct 129 ms 3960 KB Output is correct
5 Correct 197 ms 760 KB Output is correct
6 Correct 234 ms 5228 KB Output is correct
7 Correct 252 ms 1456 KB Output is correct
8 Correct 475 ms 7044 KB Output is correct
9 Correct 817 ms 18808 KB Output is correct
10 Correct 643 ms 1556 KB Output is correct
11 Correct 643 ms 3116 KB Output is correct
12 Correct 778 ms 15548 KB Output is correct
13 Correct 795 ms 18808 KB Output is correct