#include <bits/stdc++.h>
using namespace std;
const int N = 200'000 + 7, SQ = 450;
int n, q, a[N], mn[SQ];
void read_input() {
cin >> n >> q;
}
void change(int x, int y) {
a[y] = x;
mn[y / SQ] = min(mn[y / SQ], x);
}
int get(int x, int y) {
for (int i = y; i / SQ <= y / SQ; i++)
if (a[i] <= x)
return i;
for (int i = y / SQ + 1; i < SQ; i++)
if (mn[i] <= x)
for (int j = i * SQ; j < (i + 1) * SQ; j++)
if (a[j] <= x)
return j;
return -1;
}
void pre_process() {
fill(a, a + N, 1e9 + 1);
fill(mn, mn + SQ, 1e9 + 1);
}
void solve() {
while (q--) {
char c;
int x, y;
cin >> c >> x >> y;
if (c == 'M')
change(x, y - 1);
else {
int t = get(x, y - 1);
cout << (t == -1 ? -1 : t + 1) << '\n';
}
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
read_input();
pre_process();
solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
2 ms |
1116 KB |
Output is correct |
4 |
Incorrect |
119 ms |
2220 KB |
Output isn't correct |
5 |
Correct |
64 ms |
1920 KB |
Output is correct |
6 |
Correct |
70 ms |
1992 KB |
Output is correct |
7 |
Incorrect |
74 ms |
2112 KB |
Output isn't correct |