oj.uz

Submission #280319

# Submission time Handle Problem Language Result Execution time Memory
280319 2020-08-22T16:07:48 Z super_j6 Cake (CEOI14_cake) C++14
100 / 100
 1114 ms 18712 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;
}

set<pii>::iterator 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 1091 ms 896 KB Output is correct
2 Correct 859 ms 1024 KB Output is correct
3 Correct 1031 ms 1056 KB Output is correct
4 Correct 801 ms 1144 KB Output is correct
5 Correct 1083 ms 2040 KB Output is correct
6 Correct 891 ms 2052 KB Output is correct
7 Correct 1114 ms 2060 KB Output is correct
8 Correct 794 ms 2048 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 7636 KB Output is correct
2 Correct 75 ms 7416 KB Output is correct
3 Correct 75 ms 7416 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 174 ms 17656 KB Output is correct
6 Correct 176 ms 17696 KB Output is correct
7 Correct 166 ms 17400 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 760 KB Output is correct
2 Correct 71 ms 760 KB Output is correct
3 Correct 127 ms 3880 KB Output is correct
4 Correct 125 ms 3912 KB Output is correct
5 Correct 202 ms 760 KB Output is correct
6 Correct 229 ms 5112 KB Output is correct
7 Correct 266 ms 1568 KB Output is correct
8 Correct 502 ms 7032 KB Output is correct
9 Correct 843 ms 18712 KB Output is correct
10 Correct 667 ms 1788 KB Output is correct
11 Correct 663 ms 3100 KB Output is correct
12 Correct 809 ms 15456 KB Output is correct
13 Correct 880 ms 18680 KB Output is correct