oj.uz

답안 #234447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
234447 2020-05-24T09:02:48 Z ne4eHbKa Deda (COCI17_deda) C++17
120 / 140
 1000 ms 14072 KB 
#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("Ofast,no-stack-protector,unroll-loops,fast-math,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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 11 ms 384 KB Output is correct
4 Correct 941 ms 14072 KB Output is correct
5 Correct 685 ms 7328 KB Output is correct
6 Correct 918 ms 10872 KB Output is correct
7 Execution timed out 1093 ms 13816 KB Time limit exceeded