oj.uz

Submission #1069649

# Submission time Handle Problem Language Result Execution time Memory
1069649 2024-08-22T07:41:57 Z caterpillow Hamburg Steak (JOI20_hamburg) C++17
0 / 100
 2 ms 860 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'

struct Rect {
    int x1, x2, y1, y2;

    Rect operator+(const Rect& b) const {
        return {max(x1, b.x1), min(x2, b.x2), max(y1, b.y1), min(y2, b.y2)};
    }
};

const int inf = 1e9 + 1;
const Rect id = {0, inf, 0, inf};

struct SegTree {
    int n;
    vt<Rect> seg;
    void init(int _n) {
        n = _n;
        seg.assign(2 * n, id);
    }
    void upd(int i, Rect v) {
        seg[i += n] = v;
        while (i /= 2) seg[i] = seg[2 * i] + seg[2 * i + 1];
    }
    bool valid() {
        Rect& r = seg[1];
        return r.x1 <= r.x2 && r.y1 <= r.y2;
    }
};

main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, k; cin >> n >> k;
    vt<Rect> rects(n);
    for (auto& [x1, x2, y1, y2] : rects) cin >> x1 >> y1 >> x2 >> y2;
    vt<int> ord(n);
    iota(all(ord), 0);

    sort(all(ord), [&] (int i, int j) { return rects[i].x2 < rects[j].x2; });
    SegTree seg1, seg2;
    seg1.init(n), seg2.init(n);
    F0R (i, n) seg2.upd(i, rects[i]);

    for (int i : ord) {
        seg1.upd(i, rects[i]);
        seg2.upd(i, id);
        if (seg1.valid() && seg2.valid()) {
            cout << seg1.seg[1].x1 << " " << seg1.seg[1].y1 << endl;
            if (k == 2) cout << seg2.seg[1].x1 << " " << seg2.seg[1].y1 << endl;
            return 0;
        }
    }

    sort(all(ord), [&] (int i, int j) { return rects[i].y2 < rects[j].y2; });
    seg1.init(n), seg2.init(n);
    F0R (i, n) seg2.upd(i, rects[i]);

    for (int i : ord) {
        seg1.upd(i, rects[i]);
        seg2.upd(i, id);
        if (seg1.valid() && seg2.valid()) {
            cout << seg1.seg[1].x1 << " " << seg1.seg[1].y1 << endl;
            if (k == 2) cout << seg2.seg[1].x1 << " " << seg2.seg[1].y2 << endl;
            return 0;
        }
    }

    assert(0);
}

Compilation message

hamburg.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main() {
      | ^~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 860 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 860 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 856 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 860 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 860 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 856 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -