Submission #909915

#	Time	Username	Problem	Language	Result	Execution time	Memory
909915		crafticat	Deda (COCI17_deda)	C++17	140 / 140	439 ms	20244 KiB

deda

#include <bits/stdc++.h>

using namespace std;

constexpr int inf = 1e9 + 7;

struct Segment {
    Segment *left = nullptr, *right = nullptr;
    int minY = inf;
    int l, r, mid;

    Segment(int l, int r) : l(l), r(r), mid((l + r) / 2) {
        if (r - 1 > l) {
            left = new Segment(l,mid);
            right = new Segment(mid,r);
        }
    }

    void checkForUpdates() {
        minY = min(left->minY,right->minY);
    }

    void update(int x, int u) {
        if (r - 1 <= l) {
            minY = u;
            return;
        }

        if (x >= mid) {
            right->update(x,u);
        } else {
            left->update(x,u);
        }
        checkForUpdates();
    }

    int get(int a, int b, int k) {

        // Fully out
        if (a >= r || b <= l) {
            return inf;
        }
        if (minY > k) return inf;

        if (r - 1 <= l) {
            return l;
        }

        if (left->minY <= k) {
            int v = left->get(a,b,k);
            if (v == inf) return right->get(a,b,k);
            return v;
        }
        else
            return right->get(a,b,k);
    }
};

int main() {
    int n, m; cin >> n >> m;

    Segment seg(0,n + 1);
    for (int i = 0; i < m; i++) {
        char t; cin >> t;
        if (t == 'M') {
            int a, b; cin >> a >> b;
            seg.update(b,a);
        } else {
            int a, b; cin >> a >> b;
            int v = seg.get(b,n + 1,a);
            if (v == inf) v = -1;
            cout << v << "\n";
        }
    }

    return 0;
}

• Subtask 1: 140 / 140