oj.uz

Submission #278859

# Submission time Handle Problem Language Result Execution time Memory
278859 2020-08-22T01:40:47 Z super_j6 Cake (CEOI14_cake) C++14
0 / 100
 793 ms 40568 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], 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]);
			
			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]);
			}
			
			memcpy(v, f, sizeof(v));
			v[m - 3] = !count(f, f + m - 4, k) * k;
			v[m - 4] = (d[l] != d[r]) * (d[l] < d[r] ? c[l] : c[r]);
			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 = 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 2048 KB Execution killed with signal 11
2 Correct 771 ms 1176 KB Output is correct
3 Runtime error 10 ms 2304 KB Execution killed with signal 11
4 Correct 775 ms 1184 KB Output is correct
5 Runtime error 17 ms 4608 KB Execution killed with signal 11
6 Runtime error 60 ms 4728 KB Execution killed with signal 11
7 Runtime error 18 ms 4608 KB Execution killed with signal 11
8 Correct 793 ms 2424 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 16504 KB Execution killed with signal 11
2 Runtime error 86 ms 17016 KB Execution killed with signal 11
3 Correct 74 ms 8568 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Runtime error 171 ms 40440 KB Execution killed with signal 11
6 Runtime error 176 ms 40568 KB Execution killed with signal 11
7 Correct 158 ms 20372 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1152 KB Execution killed with signal 11
2 Runtime error 6 ms 1408 KB Execution killed with signal 11
3 Runtime error 33 ms 8608 KB Execution killed with signal 11
4 Runtime error 33 ms 8696 KB Execution killed with signal 11
5 Runtime error 4 ms 1024 KB Execution killed with signal 11
6 Runtime error 45 ms 11084 KB Execution killed with signal 11
7 Runtime error 8 ms 2304 KB Execution killed with signal 11
8 Runtime error 69 ms 16632 KB Execution killed with signal 11
9 Runtime error 169 ms 40340 KB Execution killed with signal 11
10 Runtime error 4 ms 1024 KB Execution killed with signal 11
11 Runtime error 19 ms 3840 KB Execution killed with signal 11
12 Runtime error 132 ms 32376 KB Execution killed with signal 11
13 Runtime error 172 ms 40312 KB Execution killed with signal 11