Submission #1069644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069644		caterpillow	Hamburg Steak (JOI20_hamburg)	C++17	0 / 100	2 ms	860 KiB

hamburg

#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].y1 < 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].y1 << endl;
            return 0;
        }
    }
}

Compilation message (stderr)

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

• Subtask 1: 0 / 1
• Subtask 2: 0 / 1
• Subtask 3: 0 / 3
• Subtask 4: 0 / 6
• Subtask 5: 0 / 1
• Subtask 6: 0 / 3
• Subtask 7: 0 / 6
• Subtask 8: 0 / 79