제출 #234401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234401		VEGAnn	Deda (COCI17_deda)	C++14	140 / 140	148 ms	5752 KiB

deda

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int N = 200100;
const int oo = 2e9;
int n, q, st[4 * N], fd;

void build(int v, int l, int r){
    st[v] = oo;
    if (l == r) return;

    int md = (l + r) >> 1;

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);
}

void update(int v, int l, int r, int ps, int vl){
    if (l == r){
        st[v] = vl;
        return;
    }

    int md = (l + r) >> 1;

    if (ps <= md)
        update(v + v, l, md, ps, vl);
    else update(v + v + 1, md + 1, r, ps, vl);

    st[v] = min(st[v + v], st[v + v + 1]);
}

void real_search(int v, int l, int r, int vl){
    if (l == r){
        fd = l + 1;
        return;
    }

    int md = (l + r) >> 1;

    if (st[v + v] <= vl)
        real_search(v + v, l, md, vl);
    else real_search(v + v + 1, md + 1, r, vl);
}

void search(int v, int tl, int tr, int l, int r, int vl){
    if (fd > 0 || l > r) return;

    if (tl == l && tr == r){
        if (st[v] <= vl)
            real_search(v, l, r, vl);
        return;
    }

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

    search(v + v, tl, md, l, min(r, md), vl);
    search(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> q;

    build(1, 0, n - 1);

    for (; q; q--){
        char tp; int a, b; cin >> tp >> a >> b;

        b--;

        if (tp == 'M')
            update(1, 0, n - 1, b, a);
        else {
            fd = -1;
            search(1, 0, n - 1, b, n - 1, a);

            cout << fd << '\n';
        }
    }

    return 0;
}

• Subtask 1: 140 / 140