/* IN THE NAME OF GOD */
// Oh, let the bullets fly, oh, let them rain
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200'000, sq = 450, inf = 1'000'000'010;
int out[MAXN + 10], mn_sq[sq + 10], n, q;
void input();
void solve();
void query1(int x, int a);
int query2(int y, int b);
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
input();
solve();
return 0;
}
void input() {
cin >> n >> q;
}
void solve() {
for (int i = 0; i < n; i++)
out[i] = inf;
for (int i = 0; i < sq; i++)
mn_sq[i] = inf;
while (q--) {
char type;
int k1, k2;
cin >> type >> k1 >> k2;
k2--;
if (type == 'M')
query1(k1, k2);
else
cout << query2(k1, k2) << '\n';
}
}
void query1(int x, int a) {
mn_sq[a / sq] = min(mn_sq[a / sq], x);
out[a] = x;
}
int query2(int y, int b) {
int tmp = inf, ptr1 = b;
while (ptr1 % sq && ptr1 < n) {
tmp = min(tmp, out[ptr1]);
if (tmp <= y)
return ptr1 + 1;
ptr1++;
}
int prv = tmp;
for (int i = b / sq + 1; i <= n / sq; i++) {
tmp = min(tmp, mn_sq[i]);
if (tmp <= y) {
int res = prv;
for (int j = i * sq; j < min((i + 1) * sq, n); j++) {
res = min(res, out[j]);
if (res <= y)
return j + 1;
}
}
prv = tmp;
}
return -1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
4 |
Incorrect |
141 ms |
2132 KB |
Output isn't correct |
5 |
Incorrect |
63 ms |
1424 KB |
Output isn't correct |
6 |
Incorrect |
71 ms |
1876 KB |
Output isn't correct |
7 |
Incorrect |
80 ms |
2128 KB |
Output isn't correct |