# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
871991 | vjudge1 | Deda (COCI17_deda) | C++17 | 116 ms | 2128 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 200'000 + 7, SQ = 450;
int n, q, s[N], mn[SQ + 7];
void read_input() {
cin >> n >> q;
}
void change(int x, int a) {
s[a] = x;
mn[a / SQ] = min(mn[a / SQ], x);
}
int get(int y, int b) {
for (int i = b; i / SQ <= b / SQ; i++)
if (s[i] <= y)
return i;
for (int i = b / SQ + 1; i <= (n - 1) / SQ; i++)
if (mn[i] <= y) {
for (int j = i * SQ; j < (i + 1) * SQ; j++)
if (s[j] <= y)
return j;
assert(false);
}
return -1;
}
void pre_process() {
fill(s, s + N, 1e9 + 1);
fill(mn, mn + SQ + 7, 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();
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |