# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
871986 | vjudge1 | Deda (COCI17_deda) | C++17 | 115 ms | 2276 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, 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 y, int b) {
for (int i = b; i / SQ <= b / SQ; i++)
if (a[i] <= y)
return i;
for (int i = b / SQ + 1; i <= n / SQ; i++)
if (mn[i] <= y)
for (int j = i * SQ; j < (i + 1) * SQ; j++)
if (a[j] <= y)
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();
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |