답안 #342084

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
342084 2021-01-01T10:52:53 Z phathnv Deda (COCI17_deda) C++11
140 / 140
130 ms 7916 KB
#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;
}
# 결과 실행 시간 메모리 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