Submission #234442

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
234442	2020-05-24T08:59:28 Z	ne4eHbKa	Deda (COCI17_deda)	C++17	120 / 140	1000 ms	14072 KB

deda

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}

#define re return

mt19937 rnd(chrono::system_clock().now().time_since_epoch().count());

int rint(int v) {re rnd() % v;}

int n;

#pragma GCC optimize("O3")

struct tree {
    tree *l, *r;
    int v;
    tree(int tl = 1, int tr = n): l(r = 0), v(+2e9) {
        if(tl < tr) {
            int tm = (tl + tr) >> 1;
            l = new tree(tl, tm);
            r = new tree(tm + 1, tr);
        }
    }
    void upd(int p, int x, int tl = 1, int tr = n) {
        umin(v, x);
        if(tl < tr) {
            int tm = (tl + tr) >> 1;
            p <= tm
                ? l->upd(p, x, tl, tm)
                : r->upd(p, x, tm + 1, tr);
        }
    }
    int req(int ql, int qr, int tl = 1, int tr = n) {
        if(ql > qr) re +2e9;
        if(ql == tl && qr == tr) re v;
        int tm = (tl + tr) >> 1;
        re min(l->req(ql, min(tm, qr), tl, tm), 
               r->req(max(tm + 1, ql), qr, tm + 1, tr));
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int q; cin >> n >> q;
    
    tree t {};
    
    while(q--) {
        char tp; cin >> tp;
        if(tp == 'M') {
            int a, x; cin >> x >> a;
            t.upd(a, x);
        } else {
            int y, b; cin >> y >> b; 
            if(t.req(b, n) > y) {
                cout << "-1\n";
                continue;
            }
            int l = b, r = n;
            while(l < r) {
                int m = (l + r) >> 1;
                t.req(l, m) <= y
                    ? r = m
                    : l = m + 1;
            }
            cout << l << '\n';
        }
    }
}

Subtask #1

120.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	10 ms	384 KB	Output is correct
4	Correct	950 ms	14072 KB	Output is correct
5	Correct	659 ms	7388 KB	Output is correct
6	Correct	832 ms	10744 KB	Output is correct
7	Execution timed out	1006 ms	14020 KB	Time limit exceeded