oj.uz

Submission #909915

# Submission time Handle Problem Language Result Execution time Memory
909915 2024-01-17T15:23:15 Z crafticat Deda (COCI17_deda) C++17
140 / 140
 439 ms 20244 KB 
#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.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 8 ms 348 KB Output is correct
4 Correct 401 ms 20244 KB Output is correct
5 Correct 376 ms 10368 KB Output is correct
6 Correct 439 ms 15232 KB Output is correct
7 Correct 426 ms 20008 KB Output is correct