oj.uz

Submission #280321

# Submission time Handle Problem Language Result Execution time Memory
280321 2020-08-22T16:11:17 Z super_j6 Cake (CEOI14_cake) C++14
100 / 100
 1066 ms 18728 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], b[m];
set<pii> s;
 
int ff(int x){
	return x < 1 || x > n ? -1 : find(f, f + m - 4, x) - f;
}

auto fp(int x){
	return s.lower_bound({{x, 0}, {0, 0}});
}
 
void add(int x, int y, int v, int w){
	auto it = fp(y + 1);
	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), l--;
		else add(r, r, i, l), r++;
	}
	
	cin >> q;
	
	int cnt = 0;
	while(q--){
		char t;
		cin >> t;
		if(t == 'F'){
			int x;
			cin >> x;
			pii p = *fp(x);
			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]);
			
			memcpy(b, f, sizeof(b));
			b[m - 3] = !count(f, f + m - 4, k) * k;
			b[m - 4] = fp(x + (x < k) - (x > k))->s.s;
			if(b[m - 4] == k) b[m - 4] += (x < k) - (x > k);
			b[m - 4] *= !count(f, f + m - 4, b[m - 4]);
			sort(b, b + m);
			
			for(int l = find(b, b + m, k) - b, r = l, i = b[++r] - b[--l] - 2; i < n - 1;){
				if(ff(b[l]) > ff(b[r])) add(b[l - 1] + 1, b[l], i += b[l] - b[l - 1], b[r]), l--;
				else add(b[r], b[r + 1] - 1, i += b[r + 1] - b[r], b[l]), r++;
			}
		}
	}
	
	return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:60:6: warning: unused variable 'cnt' [-Wunused-variable]
   60 |  int cnt = 0;
      |      ^~~

Subtask #1
15.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 Correct 1 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 19 ms 1024 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1030 ms 1016 KB Output is correct
2 Correct 780 ms 1144 KB Output is correct
3 Correct 1028 ms 1144 KB Output is correct
4 Correct 784 ms 1144 KB Output is correct
5 Correct 1066 ms 2040 KB Output is correct
6 Correct 868 ms 2168 KB Output is correct
7 Correct 1052 ms 2168 KB Output is correct
8 Correct 783 ms 2168 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 7620 KB Output is correct
2 Correct 77 ms 7444 KB Output is correct
3 Correct 75 ms 7416 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 173 ms 17580 KB Output is correct
6 Correct 192 ms 17688 KB Output is correct
7 Correct 163 ms 17520 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 760 KB Output is correct
2 Correct 69 ms 760 KB Output is correct
3 Correct 127 ms 3832 KB Output is correct
4 Correct 128 ms 3832 KB Output is correct
5 Correct 201 ms 760 KB Output is correct
6 Correct 233 ms 5112 KB Output is correct
7 Correct 262 ms 1528 KB Output is correct
8 Correct 524 ms 7168 KB Output is correct
9 Correct 835 ms 18624 KB Output is correct
10 Correct 691 ms 1660 KB Output is correct
11 Correct 732 ms 3192 KB Output is correct
12 Correct 783 ms 15312 KB Output is correct
13 Correct 808 ms 18728 KB Output is correct