Submission #342084

#	Time	Username	Problem	Language	Result	Execution time	Memory
342084		phathnv	Deda (COCI17_deda)	C++11	140 / 140	130 ms	7916 KiB

deda

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct TsegmentTree{
    int n;
    vector <int> d;
    void update(int id, int l, int r, int pos, int val){
        if (pos < l || r < pos)
            return;
        if (l == r){
            d[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, pos, val);
        update(id << 1 | 1, mid + 1, r, pos, val);
        d[id] = min(d[id << 1], d[id << 1 | 1]);
    }
    int findPos(int id, int l, int r, int pos, int val){
        if (d[id] > val || r < pos)
            return -1;
        if (l == r)
            return l;
        int mid = (l + r) >> 1;
        int res = findPos(id << 1, l, mid, pos, val);
        if (res == -1)
            res = findPos(id << 1 | 1, mid + 1, r, pos, val);
        return res;
    }

    void init(int _n){
        n = _n;
        d.assign(n * 4 + 1, 1e9);
    }
    void update(int pos, int val){
        update(1, 1, n, pos, val);
    }
    int findPos(int pos, int val){
        return findPos(1, 1, n, pos, val);
    }
};

int n, q;

void ReadInput(){
    cin >> n >> q;
}

void Solve(){
    TsegmentTree st;
    st.init(n);
    while (q--){
        char type;
        cin >> type;
        if (type == 'M'){
            int x, a;
            cin >> x >> a;
            st.update(a, x);
        } else {
            int y, b;
            cin >> y >> b;
            cout << st.findPos(b, y) << '\n';
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ReadInput();
    Solve();
    return 0;
}

• Subtask 1: 140 / 140