제출 #1355220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1355220		takoshanava	Deda (COCI17_deda)	C++20	140 / 140	179 ms	5600 KiB

deda

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;

const int INF = 1e18, N = 2e5 + 5;
int seg[4 * N];

void build(int k, int l, int r){
    if(l == r){
        seg[k] = INF;
        return;
    }
    int m = (l + r) / 2;
    build(k* 2, l, m); build(k * 2 + 1, m + 1, r);
    seg[k] = min(seg[k * 2], seg[k * 2 + 1]);
}

void upd(int k, int l, int r, int i, int v){
    if(l == r){
        seg[k] = v;
        return;
    }
    int m = (l + r) / 2;
    if(i <= m) upd(k * 2, l, m, i, v);
    else upd(k * 2 + 1, m + 1, r, i, v);
    seg[k] = min(seg[k * 2], seg[k * 2 + 1]);
}

int get(int k, int l, int r, int s, int Y){
    if(r < s or seg[k] > Y) return -1;
    if(l == r) return l;

    int m = (l + r) / 2;
    int val = get(k * 2, l, m, s, Y);
    if(val != -1) return val;
    return get(k * 2 + 1, m + 1, r, s, Y);
}

signed main() {
    int n, q;
    cin >> n >> q;
    build(1, 1, n);

    while(q--){
        char tp;
        cin >> tp;
        if(tp == 'M'){
            int x, a;
            cin >> x >> a;
            upd(1, 1, n, a, x);
        }else{
            int y, b;
            cin >> y >> b;
            cout << get(1, 1, n, b, y) << endl;
        }
    }
}

• 서브태스크 1: 140 / 140