oj.uz

Submission #279195

# Submission time Handle Problem Language Result Execution time Memory
279195 2020-08-22T04:57:50 Z super_j6 Cake (CEOI14_cake) C++14
0 / 100
 1186 ms 21624 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 - 4, 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 - (y < k) * (y + 1 - it->f.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 - (x > k) * (it->f.f + 1 - x)}), 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});
	s.insert({{k, k}, 0});
	s.insert({{n + 1, n + 1}, n});
	
	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;
	
	int cnt = -10000000;
	while(q--){
		char t;
		cin >> t;
		if(t == 'F'){
			int x;
			cin >> x;
			pii p = *s.lower_bound({{x, 0}, 0});
			if(cnt > 90) cout << x << ": ";
			cout << (x < k ? p.s + p.f.s - x : p.s + x - p.f.f) << endl;
			cnt++;
		}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] = (d[l] != d[r]) * (d[l] < d[r] ? c[l] : c[r]);
			v[m - 4] *= v[m - 4] != k && !count(f, f + m - 4, v[m - 4]);
			if(cnt > 94) cout << v[m - 4] << endl;
			sort(v, v + m);
			
			l = find(v, v + m, k) - v;
			r = l-- + 1;
			
			if(cnt > 94) cout << v[l] << " " << v[r] << endl;
			
			for(int i = max(d[v[l]], d[v[r]]); 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++;
				if(cnt > 94) cout << i << " " << v[l] << " " << v[r] << endl;
			}
			if(cnt > 94) pr();
		}
	}
	
	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 1085 ms 1144 KB Output isn't correct
2 Correct 802 ms 1180 KB Output is correct
3 Correct 1110 ms 1272 KB Output is correct
4 Correct 819 ms 1180 KB Output is correct
5 Incorrect 1186 ms 2332 KB Output isn't correct
6 Correct 897 ms 2356 KB Output is correct
7 Incorrect 1091 ms 2424 KB Output isn't correct
8 Correct 813 ms 2488 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 8824 KB Output isn't correct
2 Correct 75 ms 8696 KB Output is correct
3 Correct 74 ms 8568 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Incorrect 169 ms 20600 KB Output isn't correct
6 Incorrect 187 ms 20728 KB Output isn't correct
7 Correct 159 ms 20344 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 640 KB Output isn't correct
2 Incorrect 86 ms 888 KB Output isn't correct
3 Incorrect 154 ms 4472 KB Output isn't correct
4 Incorrect 128 ms 4472 KB Output isn't correct
5 Incorrect 234 ms 824 KB Output isn't correct
6 Incorrect 254 ms 5992 KB Output isn't correct
7 Incorrect 296 ms 1656 KB Output isn't correct
8 Incorrect 580 ms 8312 KB Output isn't correct
9 Incorrect 870 ms 21496 KB Output isn't correct
10 Incorrect 723 ms 1656 KB Output isn't correct
11 Incorrect 733 ms 3320 KB Output isn't correct
12 Incorrect 836 ms 17784 KB Output isn't correct
13 Incorrect 859 ms 21624 KB Output isn't correct