Submission #931411

#	Time	Username	Problem	Language	Result	Execution time	Memory
931411		vjudge1	Deda (COCI17_deda)	C++17	140 / 140	75 ms	4520 KiB

deda

#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 / 140