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