oj.uz

Submission #280153

# Submission time Handle Problem Language Result Execution time Memory
280153 2020-08-22T14:14:02 Z super_j6 Cake (CEOI14_cake) C++14
0 / 100
 1189 ms 7416 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);
		else add(r, r, i, r);
	}
	
	cin >> q;
	
	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;
			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;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1110 ms 4764 KB Output isn't correct
2 Correct 830 ms 4856 KB Output is correct
3 Correct 1116 ms 4768 KB Output is correct
4 Correct 855 ms 4768 KB Output is correct
5 Incorrect 1189 ms 5208 KB Output isn't correct
6 Correct 998 ms 5464 KB Output is correct
7 Incorrect 1079 ms 5240 KB Output isn't correct
8 Correct 1046 ms 5468 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 2680 KB Output isn't correct
2 Incorrect 49 ms 2584 KB Output isn't correct
3 Incorrect 42 ms 2552 KB Output isn't correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 88 ms 4420 KB Output isn't correct
6 Incorrect 77 ms 4472 KB Output isn't correct
7 Incorrect 75 ms 4216 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 948 KB Output isn't correct
2 Incorrect 72 ms 960 KB Output isn't correct
3 Incorrect 125 ms 1656 KB Output isn't correct
4 Incorrect 120 ms 1656 KB Output isn't correct
5 Incorrect 269 ms 1848 KB Output isn't correct
6 Incorrect 233 ms 2736 KB Output isn't correct
7 Incorrect 277 ms 2472 KB Output isn't correct
8 Incorrect 515 ms 3204 KB Output isn't correct
9 Incorrect 800 ms 7324 KB Output isn't correct
10 Incorrect 713 ms 5260 KB Output isn't correct
11 Incorrect 693 ms 6136 KB Output isn't correct
12 Incorrect 842 ms 7416 KB Output isn't correct
13 Incorrect 816 ms 6616 KB Output isn't correct