| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1144726 | Muaath_5 | Cake (CEOI14_cake) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define int ll
#define pii pair<int, int>
const int N = 5e5+1;
// Use template for ordered_set to avoid namespace issues
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int n, a, d[N];
#define seg pii
seg tree[4*N];
seg INF = {1e9, 1e9};
// Update function with proper indentation
void update(int idx, seg val, int l = 1, int r = n, int node = 1) {
if (l == r) {
tree[node] = val;
return;
}
const int mid = (l + r) / 2;
if (idx <= mid)
update(idx, val, l, mid, node * 2);
else
update(idx, val, mid + 1, r, node * 2 + 1);
tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
}
// Query function with proper indentation
seg query(int ql, int qr, int l = 1, int r = n, int node = 1) {
if (ql <= l && r <= qr)
return tree[node];
if (l > qr || r < ql)
return INF;
const int mid = (l + r) / 2;
return min(
query(ql, qr, l, mid, node * 2),
query(ql, qr, mid + 1, r, node * 2 + 1)
);
}
seg cc[N];
map<int, int> cmp;
int g[N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> a;
// Read input array
for (int i = 1; i <= n; i++) {
cin >> d[i];
}
ordered_set<pair<int, int>> oleft, oright;
// Initialize left side of 'a'
for (int i = 1; i < a; i++) {
cc[i] = {n - d[i] + 1, 0};
oleft.insert(cc[i]);
update(i, cc[i]);
}
// Initialize right side of 'a'
for (int i = a + 1; i <= n; i++) {
cc[i] = {n - d[i] + 1, 0};
oright.insert(cc[i]);
update(i, cc[i]);
}
int q;
cin >> q;
int ttt = 1;
while (q--) {
ttt++;
char t;
int i, e;
cin >> t >> i;
if (t == 'F') {
// Simplified handling of 'F' query
if (a == 1 || a == n) {
cout << abs(a - i) << '\n';
continue;
}
if (i == a) {
cout << "0\n";
continue;
}
if (i < a) {
auto suff_max = query(i, a - 1);
cout << (a - i) + oright.size() - oright.order_of_key(suff_max) << '\n';
} else { // i > a
auto pref_max = query(a + 1, i);
cout << (i - a) + oleft.size() - oleft.order_of_key(pref_max) << '\n';
}
} else { // Update query
cin >> e;
// Remove from previous set
if (i < a) oleft.erase(cc[i]);
if (i > a) oright.erase(cc[i]);
// Update value
cc[i] = {e, -ttt};
update(i, cc[i]);
// Re-insert into appropriate set
if (i < a) oleft.insert(cc[i]);
if (i > a) oright.insert(cc[i]);
}
}
return 0;
}