#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 250000 + 5;
int n, s;
int val[MAX_N];
int q;
set<pii> vals; // {val, ind}
set<int> ls, rs;
int segtree[4 * MAX_N];
void update(int i, int x, int u = 1, int lo = 1, int hi = n) {
if (lo == hi) {
segtree[u] = x;
return;
}
int mid = (lo + hi) / 2;
if (i <= mid) update(i, x, 2 * u, lo, mid);
else update(i, x, 2 * u + 1, mid + 1, hi);
segtree[u] = max(segtree[2 * u], segtree[2 * u + 1]);
}
int r_walk(int l, int r, int x, int u = 1, int lo = 1, int hi = n) { // First el. in [l, r] s.t. val[i] > x (r + 1 otherwise)
if (l > r) return r + 1;
if (hi < l || r < lo) return r + 1;
if (segtree[u] <= x) return r + 1;
if (lo == hi) return lo;
int mid = (lo + hi) / 2;
int resp = r_walk(l, r, x, 2 * u, lo, mid);
if (resp != r + 1) return resp;
return r_walk(l, r, x, 2 * u + 1, mid + 1, hi);
}
int l_walk(int l, int r, int x, int u = 1, int lo = 1, int hi = n) {
if (l > r) return l - 1;
if (hi < l || r < lo) return l - 1;
if (segtree[u] <= x) return l - 1;
if (lo == hi) return lo;
int mid = (lo + hi) / 2;
int resp = l_walk(l, r, x, 2 * u + 1, mid + 1, hi);
if (resp != l - 1) return resp;
return l_walk(l, r, x, 2 * u, lo, mid);
}
void update2(int i, int new_val) {
val[i] = new_val;
update(i, val[i]);
if (i < s) {
if (ls.count(i)) ls.erase(i);
auto it = ls.upper_bound(i);
if (it != ls.end() && val[*it] > val[i]) return;
while (ls.upper_bound(i) != ls.begin() && val[*next(ls.upper_bound(i), -1)] < val[i])
ls.erase(next(ls.upper_bound(i), -1));
ls.insert(i);
} else {
if (rs.count(i)) rs.erase(i);
auto it = rs.upper_bound(i);
if (it != rs.begin() && val[*next(it, -1)] > val[i]) return;
while (rs.upper_bound(i) != rs.end() && val[*rs.upper_bound(i)] < val[i])
rs.erase(rs.upper_bound(i));
rs.insert(i);
}
}
void update1(int i, int p) {
vector<int> to_erase; // Highest to lowest position
auto it = vals.end();
for (int j = 1; j <= p; j++) {
it--;
if (j != p) to_erase.push_back(it->second);
}
int new_val = it->first + 1;
vals.erase({val[i], i});
vals.insert({new_val, i});
for (int el : to_erase) {
vals.erase({val[el], el});
vals.insert({val[el] + 1, el});
}
for (int el : to_erase) update2(el, val[el] + 1);
update2(i, new_val);
}
int query(int i) {
if (i == s) return 0;
if (i < s) {
int j = *ls.lower_bound(i);
int k = r_walk(s + 1, n, val[j]);
return k - 1 - (i + 1) + 1;
} else {
int j = *next(rs.upper_bound(i), -1);
int k = l_walk(1, s - 1, val[j]);
return i - 1 - (k + 1) + 1;
}
}
void init() {
for (int i = 1; i <= n; i++) {
if (i == s) continue;
vals.insert({val[i], i});
update2(i, val[i]);
}
}
int main() {
// freopen("cake.in", "r", stdin);
// freopen("cake.out", "w", stdout);
cin >> n >> s;
for (int i = 1; i <= n; i++) cin >> val[i];
cin >> q;
init();
// cout << "HELLO" << endl;
// for (pii el : vals) cout << el.second << "," << el.first << " ";
// cout << endl;
// for (int el : ls) cout << el << " ";
// cout << endl;
// for (int el : rs) cout << el << " ";
// cout << endl;
// cout << "HELLO" << endl;
for (int i = 1; i <= q; i++) {
char ch; cin >> ch;
if (ch == 'E') {
int i, p; cin >> i >> p;
if (i == s) continue;
update1(i, p);
// cout << "HELLO" << endl;
// for (pii el : vals) cout << el.second << "," << el.first << " ";
// cout << endl;
// for (int el : ls) cout << el << " ";
// cout << endl;
// for (int el : rs) cout << el << " ";
// cout << endl;
// cout << "HELLO" << endl;
} else {
int i; cin >> i;
cout << query(i) << '\n';
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
2 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Incorrect |
10 ms |
2392 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
657 ms |
2908 KB |
Output is correct |
2 |
Incorrect |
392 ms |
2908 KB |
Output isn't correct |
3 |
Correct |
493 ms |
3072 KB |
Output is correct |
4 |
Correct |
296 ms |
2904 KB |
Output is correct |
5 |
Incorrect |
823 ms |
5860 KB |
Output isn't correct |
6 |
Incorrect |
624 ms |
5876 KB |
Output isn't correct |
7 |
Correct |
538 ms |
5720 KB |
Output is correct |
8 |
Correct |
339 ms |
5720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
210 ms |
9796 KB |
Output is correct |
2 |
Incorrect |
193 ms |
9808 KB |
Output isn't correct |
3 |
Incorrect |
190 ms |
9776 KB |
Output isn't correct |
4 |
Correct |
1 ms |
2392 KB |
Output is correct |
5 |
Correct |
320 ms |
17568 KB |
Output is correct |
6 |
Correct |
322 ms |
17636 KB |
Output is correct |
7 |
Incorrect |
268 ms |
17488 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
88 ms |
2728 KB |
Output isn't correct |
2 |
Incorrect |
86 ms |
2848 KB |
Output isn't correct |
3 |
Incorrect |
176 ms |
7312 KB |
Output isn't correct |
4 |
Correct |
169 ms |
7208 KB |
Output is correct |
5 |
Incorrect |
259 ms |
2900 KB |
Output isn't correct |
6 |
Correct |
285 ms |
8108 KB |
Output is correct |
7 |
Correct |
279 ms |
3412 KB |
Output is correct |
8 |
Correct |
323 ms |
9456 KB |
Output is correct |
9 |
Correct |
1392 ms |
18560 KB |
Output is correct |
10 |
Incorrect |
854 ms |
3576 KB |
Output isn't correct |
11 |
Correct |
959 ms |
6780 KB |
Output is correct |
12 |
Correct |
1311 ms |
16108 KB |
Output is correct |
13 |
Correct |
1138 ms |
18884 KB |
Output is correct |