Submission #1200214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200214		nguyenan132	Deda (COCI17_deda)	C++20	140 / 140	110 ms	7748 KiB

deda

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 2000000005LL;

struct SegTree {
    int n;
    vector<ll> st;
    SegTree(int _n=0) { init(_n); }
    void init(int _n) {
        n = _n;
        st.assign(4*n+4, INF);
    }
    void update(int p, int l, int r, int pos, ll val) {
        if (l == r) {
            st[p] = val;
            return;
        }
        int m = (l + r) >> 1;
        if (pos <= m) update(p<<1, l, m, pos, val);
        else          update(p<<1|1, m+1, r, pos, val);
        st[p] = min(st[p<<1], st[p<<1|1]);
    }
    void update(int pos, ll val) {
        update(1, 1, n, pos, val);
    }
    int find_first(int p, int l, int r, int ql, ll Y) {
        if (r < ql || st[p] > Y) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = -1;
        if (ql <= m) {
            res = find_first(p<<1, l, m, ql, Y);
            if (res != -1) return res;
        }
        return find_first(p<<1|1, m+1, r, ql, Y);
    }
    int find_first(int ql, ll Y) {
        return find_first(1, 1, n, ql, Y);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    SegTree st(N);

    while (Q--) {
        char type;
        cin >> type;
        if (type == 'M') {
            ll X;
            int A;
            cin >> X >> A;
            st.update(A, X);
        } else if (type == 'D') {
            ll Y;
            int B;
            cin >> Y >> B;
            int ans = st.find_first(B, Y);
            if (ans == -1) cout << -1 << "\n";
            else           cout << ans << "\n";
        }
    }
    return 0;
}

• Subtask 1: 140 / 140