oj.uz

Submission #909913

# Submission time Handle Problem Language Result Execution time Memory
909913 2024-01-17T15:18:46 Z crafticat Deda (COCI17_deda) C++17
120 / 140
 419 ms 23668 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 in
        if (a <= l && b >= r) {
            //return l;
        }
        // Fully out
        if (a >= r || b <= l) {
            return inf;
        }
        if (minY > k) return inf;

        if (r - 1 <= l) {
            if (minY > k) return inf;
            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,a);
            if (v == inf) v = -1;
            cout << v << "\n";
        }
    }

    return 0;
}

Subtask #1
120.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 436 KB Output isn't correct
2 Correct 2 ms 432 KB Output is correct
3 Correct 8 ms 548 KB Output is correct
4 Correct 398 ms 23668 KB Output is correct
5 Correct 419 ms 13808 KB Output is correct
6 Correct 407 ms 18616 KB Output is correct
7 Correct 398 ms 23452 KB Output is correct