oj.uz

Submission #931411

# Submission time Handle Problem Language Result Execution time Memory
931411 2024-02-21T18:18:24 Z vjudge1 Deda (COCI17_deda) C++17
140 / 140
 75 ms 4520 KB 
#include <bits/stdc++.h>
using i64 = long long;

constexpr int Inf = 1E9 + 1;
struct Item {
    int val;
    Item(int x = Inf) : val(x) {}
};
Item operator+(Item lhs, Item rhs) {
    return Item{std::min(lhs.val, rhs.val)};
}

struct SegTree {
    int n;
    std::vector<Item> tree;
    SegTree(int _n) : n(_n) {
        tree.resize(n * 4);
    }

    void set(int node, int l, int r, int p, Item it) {
        if(r < p || p < l) {
            return;
        } else if(l == r) {
            tree[node] = it;
            return;
        }

        int mid = (l + r) / 2;
        set(node * 2, l, mid, p, it);
        set(node * 2 + 1, mid + 1, r, p, it);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];

        return;
    }

    void set(int p, Item it) {
        set(1, 0, n - 1, p, it);
    }

    int query(int node, int l, int r, int ql, int qv) {
        if(r < ql || tree[node].val > qv) {
            return -1;
        } else if(l == r) {
            return l;
        }

        int mid = (l + r) / 2;
        int g = query(node * 2, l, mid, ql, qv);
        if(g == -1) g = query(node * 2 + 1, mid + 1, r, ql, qv);

        return g;
    }

    int query(int ql, int qv) {
        return query(1, 0, n - 1, ql, qv);
    }
};

void solve() {
    int n, q;
    std::cin >> n >> q;

    SegTree st(n + 1);
    for(int cCc = 1; cCc <= q; cCc++) {
        //std::cerr << "query " << cCc << ":\n";
        char ch;
        std::cin >> ch;
        if(ch == 'M') {
            int x, a;
            std::cin >> x >> a;
            st.set(a, x);
        } else {
            int y, b;
            std::cin >> y >> b;
            std::cout << st.query(b, y) << "\n";
        }
    }
    
    return;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); std::cout.tie(NULL);

    int t = 1; //std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 57 ms 4432 KB Output is correct
5 Correct 66 ms 2760 KB Output is correct
6 Correct 75 ms 3448 KB Output is correct
7 Correct 71 ms 4520 KB Output is correct