oj.uz

Submission #280285

# Submission time Handle Problem Language Result Execution time Memory
280285 2020-08-22T15:33:36 Z super_j6 Cake (CEOI14_cake) C++14
100 / 100
 1092 ms 21308 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], v[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(v, f, sizeof(v));
			v[m - 3] = !count(f, f + m - 4, k) * k;
			v[m - 4] = s.lower_bound({{x + (x < k) - (x > k), 0}, {0, 0}})->s.s;
			if(v[m - 4] == k) v[m - 4] += (x < k) - (x > k);
			v[m - 4] *= !count(f, f + m - 4, v[m - 4]);
			sort(v, v + m);
			
			l = find(v, v + m, k) - v;
			r = l-- + 1;
			
			for(int i = v[r] - v[l] - 2; i < n - 1;){
				if(ff(v[l]) > ff(v[r])){
					add(v[l - 1] + 1, v[l], i += v[l] - v[l - 1], v[r]); 
					l--;
				}else{
					add(v[r], v[r + 1] - 1, i += v[r + 1] - v[r], v[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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 19 ms 1152 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1060 ms 5368 KB Output is correct
2 Correct 836 ms 5472 KB Output is correct
3 Correct 1047 ms 5388 KB Output is correct
4 Correct 825 ms 5388 KB Output is correct
5 Correct 1092 ms 6612 KB Output is correct
6 Correct 921 ms 7032 KB Output is correct
7 Correct 1064 ms 6908 KB Output is correct
8 Correct 831 ms 7160 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 8952 KB Output is correct
2 Correct 77 ms 8824 KB Output is correct
3 Correct 78 ms 8824 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 174 ms 20120 KB Output is correct
6 Correct 178 ms 20088 KB Output is correct
7 Correct 167 ms 19228 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 1016 KB Output is correct
2 Correct 77 ms 1272 KB Output is correct
3 Correct 155 ms 4856 KB Output is correct
4 Correct 134 ms 4860 KB Output is correct
5 Correct 212 ms 1940 KB Output is correct
6 Correct 242 ms 6724 KB Output is correct
7 Correct 269 ms 3196 KB Output is correct
8 Correct 517 ms 8832 KB Output is correct
9 Correct 882 ms 21308 KB Output is correct
10 Correct 693 ms 3576 KB Output is correct
11 Correct 701 ms 4996 KB Output is correct
12 Correct 850 ms 16120 KB Output is correct
13 Correct 820 ms 20208 KB Output is correct