답안 #136846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136846 2019-07-26T10:55:18 Z KCSC Deda (COCI17_deda) C++14
140 / 140
868 ms 8080 KB
#include <bits/stdc++.h>
using namespace std;

const int DIM = 200005;
const int INF = 0x3f3f3f3f;

int sgt[DIM * 4];

void update(int nd, int le, int ri, int ps, int vl) {
    if (le == ri)
        sgt[nd] = vl;
    else {
        int md = (le + ri) / 2;
        if (ps <= md)
            update(nd * 2, le, md, ps, vl);
        else
            update(nd * 2 + 1, md + 1, ri, ps, vl);
        sgt[nd] = min(sgt[nd * 2], sgt[nd * 2 + 1]);
    }
}

int query2(int nd, int le, int ri, int vl) {
    if (sgt[nd] > vl)
        return INF;
    if (le == ri)
        return le;
    else {
        int md = (le + ri) / 2;
        int val = query2(nd * 2, le, md, vl);
        if (val == INF)
            val = query2(nd * 2 + 1, md + 1, ri, vl);
        return val;
    }
}

int query(int nd, int le, int ri, int st, int en, int vl) {
    if (en < le || ri < st || sgt[nd] > vl)
        return INF;
    if (st <= le && ri <= en)
        return query2(nd, le, ri, vl);
    else {
        int md = (le + ri) / 2;
        int val = query(nd * 2, le, md, st, en, vl);
        if (val == INF)
            val = query(nd * 2 + 1, md + 1, ri, st, en, vl);
        return val;
    }
}

int main(void) {
 //   freopen("deda.in", "r", stdin);
 //   freopen("deda.out", "w", stdout);
    int n, q;
    cin >> n >> q;
    memset(sgt, INF, sizeof sgt);
    for (int i = 1; i <= q; ++i) {
        char t; int a, b;
        cin >> t >> a >> b;
        if (t == 'M')
            update(1, 1, n, b, a);
        else {
            int val = query(1, 1, n, b, n, a);
            if (val == INF)
                val = -1;
            cout << val << "\n";
        }
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3580 KB Output is correct
2 Correct 6 ms 3448 KB Output is correct
3 Correct 20 ms 3576 KB Output is correct
4 Correct 868 ms 8080 KB Output is correct
5 Correct 679 ms 7724 KB Output is correct
6 Correct 746 ms 8068 KB Output is correct
7 Correct 768 ms 7952 KB Output is correct