oj.uz

Submission #883293

# Submission time Handle Problem Language Result Execution time Memory
883293 2023-12-05T05:00:26 Z vjudge1 Deda (COCI17_deda) C++17
140 / 140
 75 ms 8044 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 200'000;
const int INF = 2'000'000'000;

int n, q;
int mn[4 * N + 10];

int get(int st, int en, int y, int id = 1, int l = 1, int r = n + 1) {
    if (en <= l || r <= st || y < mn[id])
        return -1;
    if (l + 1 == r)
        return l;
    int mid = (l + r) >> 1;
    int case1 = get(st, en, y, id << 1, l, mid);
    if (case1 != -1)
        return case1;
    return get(st, en, y, id << 1 | 1, mid, r);
}

void update(int idx, int val, int id = 1, int l = 1, int r = n + 1) {
    if (idx < l || r <= idx)
        return;
    if (l + 1 == r) {
        mn[id] = val;
        return;
    }
    int mid = (l + r) >> 1;
    update(idx, val, id << 1, l, mid);
    update(idx, val, id << 1 | 1, mid, r);
    mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
}

void init() {
    fill(mn + 1, mn + 4 * n + 10, INF);
}

void query() {
    char type;
    cin >> type;
    int a, b;
    cin >> a >> b;
    if (type == 'M')
        update(b, a);
    else
        cout << get(b, n + 1, a) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    init();
    while (q--)
        query();
    cout.flush();
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 63 ms 8044 KB Output is correct
5 Correct 70 ms 6732 KB Output is correct
6 Correct 72 ms 6980 KB Output is correct
7 Correct 75 ms 8020 KB Output is correct