Submission #342084

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
342084	2021-01-01T10:52:53 Z	phathnv	Deda (COCI17_deda)	C++11	140 / 140	130 ms	7916 KB

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.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	2 ms	492 KB	Output is correct
4	Correct	95 ms	7916 KB	Output is correct
5	Correct	112 ms	5996 KB	Output is correct
6	Correct	111 ms	7020 KB	Output is correct
7	Correct	130 ms	7916 KB	Output is correct