Submission #918237

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
918237	2024-01-29T13:42:27 Z	anarch_y	Deda (COCI17_deda)	C++17	140 / 140	666 ms	6736 KB

deda

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

template<class T> struct SegmentTree{
    T def = 1e9+5;
    vector<T> tree;
    int len;

    SegmentTree(int N){
        int p = ceil(log2(N));
        len = (1<<p);
        tree.resize(2*len, def);
    }

    T f(T a, T b){
        return min(a, b);
    }

    void build(int k, int x, int y){
        if(x == y) return;
        int d = (x+y)/2;
        build(2*k, x, d);
        build(2*k+1, d+1, y);
        tree[k] = f(tree[2*k], tree[2*k+1]);
    }

    void begin(){
        build(1, 0, len-1);
    }

    void set(int id, T val, int k, int x, int y){
        if(id < x or id > y) return;
        if(x == y and x == id){
            tree[x+len] = val; 
            return;
        }
        int d = (x+y)/2;
        if(id <= d) set(id, val, 2*k, x, d);
        else set(id, val, 2*k+1, d+1, y);
        tree[k] = f(tree[2*k], tree[2*k+1]);
    }

    void set(int id, T val){
        set(id, val, 1, 0, len-1);
    }

    T query(int a, int b, int k, int x, int y){
        if(b < x or a > y) return def;
        if(a <= x and y <= b) return tree[k];
        int d = (x+y)/2;
        T s1 = query(a, b, 2*k, x, d);
        T s2 = query(a, b, 2*k+1, d+1, y);
        return f(s1, s2);
    }

    T query(int a, int b){
        return query(a, b, 1, 0, len-1);
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, Q; cin >> N >> Q;
    SegmentTree<int> seg(N+1);
    seg.begin();

    while(Q--){
        char op; cin >> op;
        if(op == 'M'){
            int X, A; cin >> X >> A;
            seg.set(A, X);
        }
        else{
            int Y, B; cin >> Y >> B;
            int L = B, R = N;
            int ans = -1;
            while(L <= R){
                int mid = (L+R)/2;
                if(seg.query(B, mid) <= Y){
                    ans = mid;
                    R = mid-1;
                }
                else L = mid+1;
            }
            cout << ans << "\n";
        }
    }
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	5 ms	520 KB	Output is correct
4	Correct	666 ms	6736 KB	Output is correct
5	Correct	394 ms	5712 KB	Output is correct
6	Correct	470 ms	6228 KB	Output is correct
7	Correct	527 ms	6472 KB	Output is correct