//khodaya khodet komak kon
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimise ("ofast")
#pragma GCC optimise("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 250000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;
const ll LOG = 25;
int n, q, tim[N], lazy[N << 2], s, a[N], koj[N];
vector<int> Top;
void modify(int id, int x){
lazy[id] = x;
}
void shift(int id){
if (lazy[id] == -1) return;
modify(id << 1, lazy[id]);
modify(id << 1 | 1, lazy[id]);
lazy[id] = -1;
}
void SET(int id, int lq, int rq, int x, int l, int r){
if (rq <= l || r <= lq) return;
if (lq <= l && r <= rq){
modify(id, x);
return;
}
int md = (l + r) >> 1;
shift(id);
SET(id << 1, lq, rq, x, l, md);
SET(id << 1 | 1, lq, rq, x, md, r);
}
int get(int id, int lq, int rq, int l, int r){
if (rq <= l || r <= lq) return 0;
if (lq <= l && r <= rq){
return lazy[id];
}
shift(id);
int md = (l + r) >> 1;
return (get(id << 1, lq, rq, l, md) + get(id << 1 | 1, lq, rq, md, r));
}
inline void build(){
int l = s - 1, r = s + 1;
SET(1, s, s + 1, l, 1, n + 1);
while (l != 0 || r != n + 1){
//cout << l << ' ' << r << '\n';
if (a[l] < a[r]){
SET(1, l, l + 1, r, 1, n + 1);
l--;
}else{
SET(1, r, r + 1, l, 1, n + 1);
r++;
}
}
}
inline void APPEND(int x, int y){
vector<int> t;
bool f = 0;
for (auto u:Top){
if (u == x) f = 1;
else t.pb(u);
}
Top.clear();
if (f){
int pnt = 0;
for (int i = 0; i <= min(n - 1, 9); i++){
if (i == min(n - 1, 9) - (n - y)) Top.pb(x);
else Top.pb(t[pnt++]);
}
return;
}
int pnt = 1;
for (int i = 0; i <= min(n - 1, 9); i++){
if (i == min(n - 1, 9) - (n - y)) t.pb(x);
else t.pb(Top[i]);
}
}
inline void solve(int x, int y){
APPEND(x, y);
Top.pb(0);
Top.pb(n + 1);
//cout << "YES\n";
//for (auto u:Top) cout << u << ' ';
//cout << '\n';
if (x == s) return;
int l, r;
bool f = 0;
if (x > s) l = get(1, x, x + 1, 1, n + 1), r = x;
else l = x, r = get(1, x, x + 1, 1, n + 1), f = 1;
int pnt = min(n - 1, 9) - (n - y);
//cout << "YES" << endl;
//cout << pnt << '\n';
while (l > 0 || r < n + 1){
//cout << l << ' ' << r << endl;
if (f){
int mn = n + 1, id = -1;
for (int i = pnt + 1; i < Top.size(); i++){
if (Top[i] >= r){
if (mn == n + 1) {mn = Top[i]; id = i;}
else if (mn > Top[i]){
mn = Top[i];
id = i;
}
}
}
//cout << mn << '\n';
SET(1, r, mn, l, 1, n + 1);
SET(1, l, l + 1, mn, 1, n + 1);
r = mn;
f = 0;
pnt = id;
l--;
}else{
int mx = 0, id = -1;
for (int i = pnt + 1; i < Top.size(); i++){
if (Top[i] <= l){
if (mx < Top[i]) mx = Top[i], id = i;
}
}
//cout << mx << endl;
SET(1, mx + 1, l + 1, r, 1, n + 1);
SET(1, r, r + 1, mx, 1, n + 1);
l = mx;
f = 1;
pnt = id;
r++;
}
}
//cout << "YES2" << endl;
Top.pop_back();
Top.pop_back();
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> s;
a[0] = n + 1, a[n + 1] = n + 1;
memset(lazy, -1, sizeof lazy);
for (int i = 1; i <= n; i++){
cin >> a[i];
koj[a[i]] = i;
}
for (int i = min(9, n - 1); i >= 0; i--){
Top.pb(koj[n - i]);
}
cin >> q;
build();
while (q--){
char c;
cin >> c;
if (c == 'F'){
int x;
cin >> x;
int id = get(1, x, x + 1, 1, n + 1);
cout << abs(id - x) - 1 << '\n';
}else{
int x, y;
cin >> x >> y;
y = n - y + 1;
//cout << "YES" << endl;
solve(x, y);
//cout << "YES2" << endl;
}
}
return 0;
}
/*
5 3
5 1 2 4 3
1
E 2 1
*/
/*
5 3
5 1 2 4 3
7
E 2 1
E 5 2
F 1
F 2
F 3
F 4
F 5
*/
Compilation message
cake.cpp:8:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
#pragma GCC optimise ("ofast")
cake.cpp:9:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
#pragma GCC optimise("unroll-loops")
cake.cpp: In function 'void APPEND(int, int)':
cake.cpp:90:6: warning: unused variable 'pnt' [-Wunused-variable]
int pnt = 1;
^~~
cake.cpp: In function 'void solve(int, int)':
cake.cpp:116:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = pnt + 1; i < Top.size(); i++){
~~^~~~~~~~~~~~
cake.cpp:134:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = pnt + 1; i < Top.size(); i++){
~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
4216 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
4216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
448 ms |
8800 KB |
Output isn't correct |
| 2 |
Incorrect |
449 ms |
8824 KB |
Output isn't correct |
| 3 |
Incorrect |
417 ms |
8824 KB |
Output isn't correct |
| 4 |
Correct |
636 ms |
8952 KB |
Output is correct |
| 5 |
Incorrect |
514 ms |
9184 KB |
Output isn't correct |
| 6 |
Incorrect |
490 ms |
9756 KB |
Output isn't correct |
| 7 |
Incorrect |
464 ms |
9264 KB |
Output isn't correct |
| 8 |
Correct |
717 ms |
9888 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
70 ms |
7032 KB |
Output isn't correct |
| 2 |
Incorrect |
75 ms |
6904 KB |
Output isn't correct |
| 3 |
Incorrect |
70 ms |
6888 KB |
Output isn't correct |
| 4 |
Correct |
8 ms |
4216 KB |
Output is correct |
| 5 |
Incorrect |
129 ms |
9508 KB |
Output isn't correct |
| 6 |
Incorrect |
116 ms |
9336 KB |
Output isn't correct |
| 7 |
Correct |
104 ms |
9080 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
44 ms |
4856 KB |
Output isn't correct |
| 2 |
Incorrect |
42 ms |
4856 KB |
Output isn't correct |
| 3 |
Incorrect |
81 ms |
5752 KB |
Output isn't correct |
| 4 |
Incorrect |
85 ms |
5752 KB |
Output isn't correct |
| 5 |
Incorrect |
107 ms |
5692 KB |
Output isn't correct |
| 6 |
Incorrect |
142 ms |
6932 KB |
Output isn't correct |
| 7 |
Incorrect |
190 ms |
6392 KB |
Output isn't correct |
| 8 |
Incorrect |
231 ms |
7672 KB |
Output isn't correct |
| 9 |
Incorrect |
514 ms |
14328 KB |
Output isn't correct |
| 10 |
Incorrect |
340 ms |
9212 KB |
Output isn't correct |
| 11 |
Incorrect |
389 ms |
10104 KB |
Output isn't correct |
| 12 |
Incorrect |
512 ms |
13448 KB |
Output isn't correct |
| 13 |
Incorrect |
470 ms |
14356 KB |
Output isn't correct |
