oj.uz

답안 #82331

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
82331 2018-10-30T02:33:32 Z Leonardo_Paes Deda (COCI17_deda) C++11
140 / 140
 618 ms 10248 KB 
#include <bits/stdc++.h>

using namespace std;

#define MAXN 200100

int vet[MAXN], tree[4*MAXN];

void update(int node, int l, int r, int idx, int val){

    if(idx<l or idx>r){
        return;
    }

    if(l==idx and r==idx){
        tree[node]=val;
        return;
    }
    int mid = (l+r)>>1;

    update(2*node, l, mid, idx, val);
    update(2*node+1, mid+1, r, idx, val);
    tree[node] = min(tree[2*node], tree[2*node+1]);
}

int query(int node, int tl, int tr, int l, int val){

    if(l > tr){
        return 0x3f3f3f3f;
    }

    if(tree[node]>val){
        return 0x3f3f3f3f;
    }

    if(tl==tr){
        return tl;
    }

    int mid = (tl+tr) >> 1;

    int p1 = query(2*node, tl, mid, l, val);

    if(p1 == 0x3f3f3f3f){
        return query(2*node+1, mid+1, tr, l, val);
    }
    return p1;
}
int n, q;
int main(){

    cin >> n >> q;

    // build

    memset(vet, 0x3f3f3f3f, sizeof vet);
    memset(tree, 0x3f3f3f3f, sizeof tree);

    for(int i=1; i<=q; i++){
        char o;

        cin >> o;

        if(o=='M'){
            int x, a;

            cin >> x >> a;

            update(1, 1, n, a, x);
        }
        if(o=='D'){
            int y, b;

            cin >> y >> b;

            int ans = query(1, 1, n, b, y);

            if(ans==0x3f3f3f3f){
                cout << -1 << endl;
            }
            else{
                cout << query(1, 1, n, b, y) << endl;
            }
        }
    }
    return 0;
}

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4312 KB Output is correct
2 Correct 6 ms 4312 KB Output is correct
3 Correct 17 ms 4548 KB Output is correct
4 Correct 618 ms 9124 KB Output is correct
5 Correct 522 ms 9876 KB Output is correct
6 Correct 539 ms 10200 KB Output is correct
7 Correct 577 ms 10248 KB Output is correct