oj.uz

Submission #234401

# Submission time Handle Problem Language Result Execution time Memory
234401 2020-05-24T07:04:19 Z VEGAnn Deda (COCI17_deda) C++14
140 / 140
 148 ms 5752 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 147 ms 5752 KB Output is correct
5 Correct 122 ms 2168 KB Output is correct
6 Correct 117 ms 3320 KB Output is correct
7 Correct 148 ms 3508 KB Output is correct