#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], b[mxn];
int f[m], v[m];
set<pii> s1, s2;
void pr(){
for(int i = 0; i < m; i++) cout << f[i] << " ";
cout << endl;
for(int i = 0; i < m; i++) cout << v[i] << " ";
cout << endl;
for(pii i : s1) cout << i.f.s << " " << i.f.f << " " << i.s << endl;
cout << endl;
}
int ff(int x){
return x < 1 || x > n ? -1 : find(f, f + m - 4, x) - f;
}
void add(set<pii> &s, 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 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, b[k] = 0;
s1.insert({{0, 0}, n});
s1.insert({{k, k}, 0});
s1.insert({{n + 1, n + 1}, n});
s2.insert({{-1, -1}, n});
for(int i = -1; i <= 1; i++) s2.insert({{k + i, k + i}, k - i});
s2.insert({{n + 2, n + 2}, 0});
for(int i = 1, l = k - 1, r = k + 1; i < n; i++){
if(a[l] < a[r]) add(s1, l, l, i), b[l--] = i, add(s2, l, l, r);
else add(s1, r, r, i), b[r++] = i, add(s2, r, r, l);
}
//pr();
cin >> q;
int cnt = -2 * mxn;
while(q--){
char t;
cin >> t;
if(t == 'F'){
int x;
cin >> x;
pii p = *s1.lower_bound({{x, 0}, 0});
if(cnt > 90) cout << x << ": ";
cout << (x < k ? p.s + p.f.s - x : p.s + x - p.f.f) << endl;
cnt++;
}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]);
int l = 0, r = n + 1;
for(int i = 0; i < m - 4; i++){
if(f[i] < k) l = max(l, f[i]);
if(f[i] > k) r = min(r, f[i]);
}
memcpy(v, f, sizeof(v));
v[m - 3] = !count(f, f + m - 4, k) * k;
v[m - 4] = s2.lower_bound({{x, 0}, 0})->s;
v[m - 4] *= !count(f, f + m - 4, v[m - 4]);
if(cnt > 94) cout << v[m - 4] << endl;
sort(v, v + m);
l = find(v, v + m, k) - v;
r = l-- + 1;
if(cnt > 94) cout << v[l] << " " << v[r] << endl;
for(int i = v[r] - v[l] - 2; i < n - 1;){
if(ff(v[l]) > ff(v[r])){
add(s1, v[l - 1] + 1, v[l], i += v[l] - v[l - 1]);
add(s2, v[l - 1], v[l] - 1, v[r]);
l--;
}else{
add(s1, v[r], v[r + 1] - 1, i += v[r + 1] - v[r]);
add(s2, v[r] + 1, v[r + 1], v[l]);
r++;
}
if(cnt > 94) cout << i << " " << v[l] << " " << v[r] << endl;
}
if(cnt > 94) pr();
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1728 ms |
6120 KB |
Output isn't correct |
2 |
Correct |
1309 ms |
6200 KB |
Output is correct |
3 |
Incorrect |
1671 ms |
6244 KB |
Output isn't correct |
4 |
Correct |
1302 ms |
6200 KB |
Output is correct |
5 |
Incorrect |
1695 ms |
8312 KB |
Output isn't correct |
6 |
Correct |
1345 ms |
8856 KB |
Output is correct |
7 |
Incorrect |
1660 ms |
8968 KB |
Output isn't correct |
8 |
Correct |
1302 ms |
9080 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
123 ms |
15736 KB |
Output isn't correct |
2 |
Correct |
120 ms |
15488 KB |
Output is correct |
3 |
Correct |
121 ms |
15492 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Incorrect |
291 ms |
36832 KB |
Output isn't correct |
6 |
Incorrect |
290 ms |
36728 KB |
Output isn't correct |
7 |
Correct |
284 ms |
36472 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
129 ms |
1292 KB |
Output isn't correct |
2 |
Incorrect |
125 ms |
1528 KB |
Output isn't correct |
3 |
Incorrect |
209 ms |
8184 KB |
Output isn't correct |
4 |
Incorrect |
243 ms |
8184 KB |
Output isn't correct |
5 |
Incorrect |
308 ms |
2040 KB |
Output isn't correct |
6 |
Incorrect |
411 ms |
11128 KB |
Output isn't correct |
7 |
Incorrect |
407 ms |
3832 KB |
Output isn't correct |
8 |
Incorrect |
783 ms |
16384 KB |
Output isn't correct |
9 |
Incorrect |
1308 ms |
41852 KB |
Output isn't correct |
10 |
Incorrect |
1028 ms |
5716 KB |
Output isn't correct |
11 |
Incorrect |
1027 ms |
8700 KB |
Output isn't correct |
12 |
Incorrect |
1235 ms |
34680 KB |
Output isn't correct |
13 |
Incorrect |
1276 ms |
41848 KB |
Output isn't correct |