#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MXN = 200 * 1000 + 3;
array<int, 2> t[MXN << 2];
int n, q;
void update(int v, int tl, int tr, int pos, int val) {
if(tl == tr)
return t[v] = {val, pos}, void();
int tm = (tl + tr) >> 1;
if(pos <= tm)
update(v << 1, tl, tm, pos, val);
else
update(v << 1|1, tm + 1, tr, pos, val);
t[v] = min(t[v << 1], t[v << 1|1]);
}
void upd(int x, int val) { update(1, 1, n, x, val); }
array<int, 2> query(int v, int tl, int tr, int l, int r, int y) {
if(l > tr || r < tl)
return array<int, 2>{(int) 1e9 + 4, -1};
if(tl == tr)
return t[v];
if(l <= tl && tr <= r) {
if(t[v][0] > y)
return array<int, 2>{(int) 1e9 + 4, -1};
int tm = (tl + tr) >> 1;
auto q1 = t[v << 1];
if(q1[0] <= y)
return query(v << 1, tl, tm, l, r, y);
else
return query(v << 1|1, tm + 1, tr, l, r, y);
}
int tm = (tl + tr) >> 1;
auto q1 = t[v << 1];
//cout << tl << ' ' << tr << " range: " << q1[0] << ' ' << q2[0] << endl;
if(q1[0] <= y)
return query(v << 1, tl, tm, l, r, y);
else
return query(v << 1|1, tm + 1, tr, l, r, y);
}
int query(int x, int y) {
auto ok = query(1, 1, n, x, n, y);
//cout << ok[0] << ' ' << ok[1] << '\n';
if(ok[0] > y)
return -1;
return ok[1];
}
signed main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
memset(t, 0x5f, sizeof t);
cin >> n >> q;
while(q--) {
char c; cin >> c;
if(c == 'M') {
int a, x;
cin >> x >> a;
upd(a, x);
} else {
int y, x;
cin >> y >> x;
cout << query(x, y) << '\n';
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
6484 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
6484 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
6484 KB |
Output isn't correct |
| 4 |
Incorrect |
59 ms |
7420 KB |
Output isn't correct |
| 5 |
Incorrect |
74 ms |
7132 KB |
Output isn't correct |
| 6 |
Incorrect |
70 ms |
7264 KB |
Output isn't correct |
| 7 |
Incorrect |
70 ms |
7244 KB |
Output isn't correct |
