oj.uz

답안 #97823

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97823 2019-02-18T18:06:12 Z dalgerok Deda (COCI17_deda) C++17
140 / 140
 151 ms 6876 KB 
#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.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 126 ms 6876 KB Output is correct
5 Correct 126 ms 5368 KB Output is correct
6 Correct 136 ms 6652 KB Output is correct
7 Correct 151 ms 6776 KB Output is correct