Submission #250234

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
250234	2020-07-17T09:17:29 Z	Vladikus004	Deda (COCI17_deda)	C++14	140 / 140	981 ms	4984 KB

deda

#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

#	Verdict	Execution time	Memory	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