oj.uz

Submission #280330

# Submission time Handle Problem Language Result Execution time Memory
280330 2020-08-22T16:16:46 Z super_j6 Cake (CEOI14_cake) C++14
0 / 100
 1144 ms 18736 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] = x + ((x < k) - (x > k)) * (fp(x + (x < k) - (x > k))->s.f + 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], 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
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 1 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 1086 ms 1016 KB Output isn't correct
2 Correct 829 ms 1144 KB Output is correct
3 Incorrect 1047 ms 1144 KB Output isn't correct
4 Correct 810 ms 1144 KB Output is correct
5 Incorrect 1144 ms 2040 KB Output isn't correct
6 Correct 938 ms 2168 KB Output is correct
7 Incorrect 1076 ms 2168 KB Output isn't correct
8 Correct 812 ms 2056 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 7544 KB Output isn't correct
2 Correct 75 ms 7512 KB Output is correct
3 Correct 75 ms 7420 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Incorrect 170 ms 17692 KB Output isn't correct
6 Incorrect 173 ms 17656 KB Output isn't correct
7 Correct 161 ms 17400 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 764 KB Output isn't correct
2 Incorrect 77 ms 760 KB Output isn't correct
3 Incorrect 138 ms 3832 KB Output isn't correct
4 Incorrect 138 ms 4088 KB Output isn't correct
5 Incorrect 236 ms 888 KB Output isn't correct
6 Incorrect 244 ms 5112 KB Output isn't correct
7 Incorrect 286 ms 1568 KB Output isn't correct
8 Incorrect 520 ms 7032 KB Output isn't correct
9 Incorrect 920 ms 18656 KB Output isn't correct
10 Incorrect 733 ms 1636 KB Output isn't correct
11 Incorrect 718 ms 3192 KB Output isn't correct
12 Incorrect 856 ms 15540 KB Output isn't correct
13 Incorrect 842 ms 18736 KB Output isn't correct