oj.uz

답안 #250234

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250234 2020-07-17T09:17:29 Z Vladikus004 Deda (COCI17_deda) C++14
140 / 140
 981 ms 4984 KB 
#include <bits/stdc++.h>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 200000 + 3;
int n, q, t[N * 4];

void build(int v, int tl, int tr){
    if (tl == tr){
        t[v] = inf;
    }else{
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm);
        build(v * 2 + 1, tm + 1, tr);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
}

int get_min(int v, int tl, int tr, int l, int r){
    if (l > r) return inf;
    if (tl == l && tr == r){
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return min(get_min(v * 2, tl, tm, l, min(r, tm)),
               get_min(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r));
}

void up(int v, int tl, int tr, int ind, int val){
    if (tl == tr){
        t[v] = val;
        return;
    }
    int tm = (tl + tr) / 2;
    if (ind <= tm) up(v * 2, tl, tm, ind, val);
    else up(v * 2 + 1, tm + 1, tr, ind, val);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n >> q;
    build(1, 0, n - 1);
    while (q--){
        char c;
        int x, y;
        cin >> c >> x >> y;
            swap(x, y);
        if (c == 'M'){
            up(1, 0, n - 1, x - 1, y);
        }else{
            --x;
            int l = x, r = n;
            while (l < r){
                int mid = (l + r) / 2;
                if (get_min(1, 0, n - 1, l, mid) <= y) r = mid;
                else l = mid + 1;
            }
            if (r != n){
            cout << r + 1 << "\n";
            }else{
            cout << -1 << "\n";
            }
        }
    }
}

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 981 ms 4984 KB Output is correct
5 Correct 613 ms 3576 KB Output is correct
6 Correct 723 ms 4728 KB Output is correct
7 Correct 833 ms 4856 KB Output is correct