# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1152906 | amirrezashoon | Deda (COCI17_deda) | C11 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
const int MAX_N = 2e5 + 7, MAX_M = 321, MAX_V = 1e5 + 7, LOG_N = 19, inf = 2e9 + 7;
const long long INF = 1e18;
int n, q, ind, val, L, R, y, b, a, x, seg[4 * MAX_N], ans[MAX_N];
void build(int l = 0, int r = n, int u = 1) {
if (r - l == 1) {
seg[u] = inf;
return;
}
int mid = (l + r) / 2;
build(l, mid, 2 * u);
build(mid, r, 2 * u + 1);
seg[u] = inf;
}
void update(int l = 0, int r = n, int u = 1) {
if (r - l == 1) {
seg[u] = val;
return;
}
int mid = (l + r) / 2;
if (ind < mid)
update(l, mid, 2 * u);
else
update(mid, r, 2 * u + 1);
seg[u] = min(seg[2 * u], seg[2 * u + 1]);
}
void get(int l = 0, int r = n, int u = 1) {
if (L <= l && r <= R) {
if (seg[u] <= y)
R = r;
else {
L = r;
return;
}
}
if (R <= l || r <= L)
return;
if (r - l >= 2) {
int mid = (l + r) / 2;
get(l, mid, 2 * u);
get(mid, r, 2 * u + 1);
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> q;
build();
fill(ans, ans + n + 1, inf);
while (q--) {
char type;
cin >> type;
if (type == 'M') {
cin >> x >> a;
a--;
ind = a, val = x;
update();
ans[a] = x;
}
else {
cin >> y >> b;
L = b - 1, R = n;
get();
if (L >= R || ans[L] > y)
cout << -1 << '\n';
else
cout << L + 1 << '\n';
}
}
}