oj.uz

Submission #280484

# Submission time Handle Problem Language Result Execution time Memory
280484 2020-08-22T20:13:43 Z super_j6 Cake (CEOI14_cake) C++14
0 / 100
 1008 ms 36216 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 find(f, f + m, 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 - 1] = i;
		for(int j = m - 2; ~-j; j--) if(a[f[j]] < a[f[j + 1]]) swap(f[j], f[j + 1]);
	} 
	
	a[0] = a[n + 1] = f[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;
			
			for(int i = ff(x); i < m - 1; i++) swap(f[i], f[i + 1]);
			
			f[m - 1] = x, y++;
			for(int i = m - 2; i >= y; i--) swap(f[i], f[i + 1]);
			
			memcpy(b, f, sizeof(b));
			b[m - 1] = !count(f, f + m - 2, k) * k;
			b[m - 2] = x + ((x < k) - (x > k)) * (qry(x + (x < k) - (x > k)) + 2);
			b[m - 2] *= !count(f, f + m - 2, b[m - 2]);
			sort(b, b + m);
			
			for(int l = ff(k), 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 640 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 2048 KB Execution killed with signal 11
2 Incorrect 974 ms 4984 KB Output isn't correct
3 Runtime error 8 ms 2304 KB Execution killed with signal 11
4 Runtime error 7 ms 2176 KB Execution killed with signal 11
5 Runtime error 15 ms 4352 KB Execution killed with signal 11
6 Incorrect 1008 ms 6520 KB Output isn't correct
7 Runtime error 15 ms 4352 KB Execution killed with signal 11
8 Runtime error 15 ms 4352 KB Execution killed with signal 11

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 60 ms 14840 KB Execution killed with signal 11
2 Incorrect 80 ms 9080 KB Output isn't correct
3 Incorrect 82 ms 8952 KB Output isn't correct
4 Runtime error 3 ms 640 KB Execution killed with signal 11
5 Runtime error 149 ms 36088 KB Execution killed with signal 11
6 Runtime error 147 ms 36088 KB Execution killed with signal 11
7 Incorrect 190 ms 19832 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1152 KB Execution killed with signal 11
2 Runtime error 6 ms 1408 KB Execution killed with signal 11
3 Runtime error 29 ms 7928 KB Execution killed with signal 11
4 Runtime error 33 ms 7928 KB Execution killed with signal 11
5 Runtime error 5 ms 1024 KB Execution killed with signal 11
6 Runtime error 47 ms 10104 KB Execution killed with signal 11
7 Runtime error 8 ms 2048 KB Execution killed with signal 11
8 Runtime error 57 ms 15096 KB Execution killed with signal 11
9 Runtime error 156 ms 36204 KB Execution killed with signal 11
10 Runtime error 4 ms 1024 KB Execution killed with signal 11
11 Runtime error 17 ms 3584 KB Execution killed with signal 11
12 Runtime error 125 ms 29092 KB Execution killed with signal 11
13 Runtime error 154 ms 36216 KB Execution killed with signal 11