oj.uz

Submission #278855

# Submission time Handle Problem Language Result Execution time Memory
278855 2020-08-22T01:32:31 Z super_j6 Cake (CEOI14_cake) C++14
0 / 100
 821 ms 42232 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 = 13;
int n, k, q;
int a[mxn], b[mxn], c[mxn], d[mxn];
int f[m], v[m];
set<pii> s;

void pr(){
	for(int i = 0; i < m; i++) cout << f[i] << " ";
	cout << endl;
	for(int i = 0; i < m; i++) cout << v[i] << " ";
	cout << endl;
	for(pii i : s) cout << i.f.s << " " << i.f.f << " " << i.s << endl;
	cout << endl;
}

int ff(int x){
	return x < 1 || x > n ? -1 : 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}), 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}), it = s.erase(it);
	s.insert({{y, x}, v});
}

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 + 1});
	s.insert({{k, k}, 0});
	s.insert({{n + 1, n + 1}, n + 1});
	
	b[k] = d[k - 1] = d[k + 1] = 0, c[k - 1] = k + 1, c[k + 1] = k - 1;
	for(int i = 1, l = k - 1, r = k + 1; i < n; i++){
		if(a[l] < a[r]) add(l, l, i), b[l--] = i, c[l] = r, d[l] = i;
		else add(r, r, i), b[r++] = i, c[r] = l, d[r] = i;
	}
	
	//pr();
	
	cin >> q;
	
	while(q--){
		char t;
		cin >> t;
		if(t == 'F'){
			int x;
			cin >> x;
			pii p = *s.lower_bound({{x, 0}, 0});
			cout << (x < k ? p.s + p.f.s - x : p.s + 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]);
			
			memcpy(v, f, sizeof(v));
			
			int l = 0, r = n + 1;
			for(int i = 0; i < m; i++){
				if(f[i] < k) l = max(l, f[i]);
				if(f[i] > k) r = min(r, f[i]);
			}
			
			v[m - 2] = !count(f, f + m, k) * k;
			v[m - 3] = (d[l] != d[r]) * (d[l] < d[r] ? c[l] : c[r]);
			sort(v, v + m);
			
			l = find(v, v + m, k) - v;
			r = l-- + 1;
			
			for(int i = min(b[v[l]], b[v[r]]) - 1; i < n - 1;){
				if(ff(v[l]) > ff(v[r])) add(v[l - 1] + 1, v[l], i += v[l] - v[l - 1]), l--;
				else add(v[r], v[r + 1] - 1, i += v[r + 1] - v[r]), r++;
			}
			//pr();
		}
	}

	return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Runtime error 3 ms 640 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2336 KB Execution killed with signal 11
2 Correct 778 ms 5528 KB Output is correct
3 Runtime error 10 ms 2560 KB Execution killed with signal 11
4 Correct 821 ms 5532 KB Output is correct
5 Runtime error 17 ms 4992 KB Execution killed with signal 11
6 Runtime error 58 ms 5240 KB Execution killed with signal 11
7 Runtime error 19 ms 5112 KB Execution killed with signal 11
8 Correct 820 ms 7544 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 17272 KB Execution killed with signal 11
2 Runtime error 84 ms 18296 KB Execution killed with signal 11
3 Correct 75 ms 10000 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Runtime error 170 ms 42224 KB Execution killed with signal 11
6 Runtime error 176 ms 42232 KB Execution killed with signal 11
7 Correct 160 ms 22776 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1152 KB Execution killed with signal 11
2 Runtime error 6 ms 1536 KB Execution killed with signal 11
3 Runtime error 33 ms 9080 KB Execution killed with signal 11
4 Runtime error 34 ms 9208 KB Execution killed with signal 11
5 Runtime error 4 ms 1024 KB Execution killed with signal 11
6 Runtime error 45 ms 11640 KB Execution killed with signal 11
7 Runtime error 8 ms 2432 KB Execution killed with signal 11
8 Runtime error 68 ms 17272 KB Execution killed with signal 11
9 Runtime error 173 ms 42200 KB Execution killed with signal 11
10 Runtime error 4 ms 1024 KB Execution killed with signal 11
11 Runtime error 14 ms 4116 KB Execution killed with signal 11
12 Runtime error 131 ms 33784 KB Execution killed with signal 11
13 Runtime error 178 ms 42232 KB Execution killed with signal 11