제출 #97823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97823		dalgerok	Deda (COCI17_deda)	C++17	140 / 140	151 ms	6876 KiB

deda

#include<bits/stdc++.h>
using namespace std;


const int N = 2e5 + 5, INF = 2e9;



int n, m, t[4 * N];


void update(int v, int l, int r, int pos, int val){
    if(l == r){
        t[v] = val;
        return;
    }
    int mid = (r + l) >> 1;
    if(pos <= mid){
        update(v + v, l, mid, pos, val);
    }
    else{
        update(v + v + 1, mid + 1, r, pos, val);
    }
    t[v] = min(t[v + v], t[v + v + 1]);
}

int get(int v, int l, int r, int tl, int tr, int val){
    if(l > r || l > tr || tl > r || t[v] > val){
        return -1;
    }
    if(l == r){
        return l;
    }
    int mid = (r + l) >> 1;
    int x = get(v + v, l, mid, tl, tr, val);
    if(x == -1){
        x = get(v + v + 1, mid + 1, r, tl, tr, val);
    }
    return x;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        update(1, 1, n, i, INF);
    }
    while(m--){
        char c;
        cin >> c;
        if(c == 'M'){
            int x, y;
            cin >> x >> y;
            update(1, 1, n, y, x);
        }
        else{
            int x, y;
            cin >> x >> y;
            cout << get(1, 1, n, y, n, x) << "\n";
        }
    }
}

• Subtask 1: 140 / 140