#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 200005
const int INF = 2000000000;
int sg[4*MAXN];
void update(int k, int a, int b, int plc, int val) {
if (b < plc || a > plc)
return ;
if (a == b) {
sg[k] = val;
return ;
}
update(2*k, a, (a+b)/2, plc, val);
update(2*k+1, (a+b)/2+1, b, plc, val);
sg[k] = min(sg[2*k], sg[2*k+1]);
}
int query(int k, int a, int b, int q_l, int q_r, int mx_stops) {
if (b < q_l || a > q_r || sg[k] > mx_stops)
return INF;
if (a == b)
return a;
int leftQ = query(2*k, a, (a+b)/2, q_l, q_r, mx_stops);
if (leftQ != INF)
return leftQ;
int rightQ = query(2*k+1, (a+b)/2+1, b, q_l, q_r, mx_stops);
if (rightQ != INF)
return rightQ;
return INF;
}
int main() {
fast
int N, Q;
cin >> N >> Q;
for (int i = 0; i < 4*MAXN; i++)
sg[i] = INF;
while (Q--) {
char ch;
cin >> ch;
if (ch == 'M') {
int plc, val;
cin >> val >> plc;
update(1, 1, N, plc, val);
} else {
int stops, mn;
cin >> stops >> mn;
int q = query(1, 1, N, mn, N, stops);
if (q == INF)
cout << -1 << "\n";
else
cout << q << "\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3412 KB |
Output is correct |
| 4 |
Correct |
65 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
75 ms |
6512 KB |
Output is correct |
| 6 |
Correct |
96 ms |
6860 KB |
Output is correct |
| 7 |
Correct |
80 ms |
6944 KB |
Output is correct |
