oj.uz

Submission #280351

# Submission time Handle Problem Language Result Execution time Memory
280351 2020-08-22T16:36:20 Z super_j6 Cake (CEOI14_cake) C++14
100 / 100
 1160 ms 19580 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];
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;
}
 
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 qry(int x){
	pii p = *s.lower_bound({{x, 0}, 0});
	return p.s + (x < k ? p.f.s - x : x - p.f.f);
}
 
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});
	
	for(int i = 1, l = k - 1, r = k + 1; i < n; i++){
		if(a[l] < a[r]) add(l, l, i), l--;
		else add(r, r, i), r++;
	}
	
	cin >> q;
	
	int cnt = 0;
	while(q--){
		char t;
		cin >> t;
		if(t == 'F'){
			int x;
			cin >> x;
			cout << qry(x) << 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] = x + ((x < k) - (x > k)) * (qry(x + (x < k) - (x > k)) + 2);
			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]), l--;
				else add(b[r], b[r + 1] - 1, i += b[r + 1] - b[r]), r++;
			}
		}
	}
	
	return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 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 512 KB Output is correct
5 Correct 18 ms 1152 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1077 ms 1380 KB Output is correct
2 Correct 831 ms 1432 KB Output is correct
3 Correct 1063 ms 1528 KB Output is correct
4 Correct 817 ms 1408 KB Output is correct
5 Correct 1101 ms 2404 KB Output is correct
6 Correct 924 ms 2436 KB Output is correct
7 Correct 1160 ms 2444 KB Output is correct
8 Correct 817 ms 2444 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 8056 KB Output is correct
2 Correct 85 ms 7928 KB Output is correct
3 Correct 86 ms 7876 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 181 ms 18040 KB Output is correct
6 Correct 181 ms 18064 KB Output is correct
7 Correct 162 ms 18336 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 1020 KB Output is correct
2 Correct 72 ms 1144 KB Output is correct
3 Correct 128 ms 4344 KB Output is correct
4 Correct 143 ms 4272 KB Output is correct
5 Correct 217 ms 1296 KB Output is correct
6 Correct 246 ms 5696 KB Output is correct
7 Correct 289 ms 1992 KB Output is correct
8 Correct 503 ms 7952 KB Output is correct
9 Correct 841 ms 19580 KB Output is correct
10 Correct 709 ms 2488 KB Output is correct
11 Correct 685 ms 4040 KB Output is correct
12 Correct 847 ms 16196 KB Output is correct
13 Correct 820 ms 19528 KB Output is correct