oj.uz

Submission #280108

# Submission time Handle Problem Language Result Execution time Memory
280108 2020-08-22T13:36:39 Z super_j6 Cake (CEOI14_cake) C++14
0 / 100
 1728 ms 41852 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];
int f[m], v[m];
set<pii> s1, s2;

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 : s1) 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(set<pii> &s, 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, b[k] = 0;
	s1.insert({{0, 0}, n});
	s1.insert({{k, k}, 0});
	s1.insert({{n + 1, n + 1}, n});
	s2.insert({{-1, -1}, n});
	for(int i = -1; i <= 1; i++) s2.insert({{k + i, k + i}, k - i});
	s2.insert({{n + 2, n + 2}, 0});
	
	for(int i = 1, l = k - 1, r = k + 1; i < n; i++){
		if(a[l] < a[r]) add(s1, l, l, i), b[l--] = i, add(s2, l, l, r);
		else add(s1, r, r, i), b[r++] = i, add(s2, r, r, l);
	}
	
	//pr();
	
	cin >> q;
	
	int cnt = -2 * mxn;
	while(q--){
		char t;
		cin >> t;
		if(t == 'F'){
			int x;
			cin >> x;
			pii p = *s1.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] = s2.lower_bound({{x, 0}, 0})->s;
			v[m - 4] *= !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 = v[r] - v[l] - 2; i < n - 1;){
				if(ff(v[l]) > ff(v[r])){
					add(s1, v[l - 1] + 1, v[l], i += v[l] - v[l - 1]); 
					add(s2, v[l - 1], v[l] - 1, v[r]);
					l--;
				}else{
					add(s1, v[r], v[r + 1] - 1, i += v[r + 1] - v[r]); 
					add(s2, v[r] + 1, v[r + 1], v[l]);
					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 Correct 1 ms 384 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1728 ms 6120 KB Output isn't correct
2 Correct 1309 ms 6200 KB Output is correct
3 Incorrect 1671 ms 6244 KB Output isn't correct
4 Correct 1302 ms 6200 KB Output is correct
5 Incorrect 1695 ms 8312 KB Output isn't correct
6 Correct 1345 ms 8856 KB Output is correct
7 Incorrect 1660 ms 8968 KB Output isn't correct
8 Correct 1302 ms 9080 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 15736 KB Output isn't correct
2 Correct 120 ms 15488 KB Output is correct
3 Correct 121 ms 15492 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 291 ms 36832 KB Output isn't correct
6 Incorrect 290 ms 36728 KB Output isn't correct
7 Correct 284 ms 36472 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 129 ms 1292 KB Output isn't correct
2 Incorrect 125 ms 1528 KB Output isn't correct
3 Incorrect 209 ms 8184 KB Output isn't correct
4 Incorrect 243 ms 8184 KB Output isn't correct
5 Incorrect 308 ms 2040 KB Output isn't correct
6 Incorrect 411 ms 11128 KB Output isn't correct
7 Incorrect 407 ms 3832 KB Output isn't correct
8 Incorrect 783 ms 16384 KB Output isn't correct
9 Incorrect 1308 ms 41852 KB Output isn't correct
10 Incorrect 1028 ms 5716 KB Output isn't correct
11 Incorrect 1027 ms 8700 KB Output isn't correct
12 Incorrect 1235 ms 34680 KB Output isn't correct
13 Incorrect 1276 ms 41848 KB Output isn't correct