Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- using namespace std;
- class X {
- public:
- friend bool operator==(X &x1, X &x2) {
- return (x1.type == x2.type && x1.coord == x2.coord && x1.lo == x2.lo && x1.hi == x2.hi);
- }
- int coord;
- int type;
- int lo;
- int hi;
- X(int c, int t, int l, int h) {
- coord = c;
- type = t;
- lo = l;
- hi = h;
- }
- };
- int* t;
- int* add;
- struct {
- bool operator()(X a, X b) const {
- if (a.coord == b.coord) {
- return a.type > b.type;
- }
- return a.coord < b.coord;
- }
- } comparator;
- void push(int v, int vl, int vr) {
- if (add[v] != 0) {
- t[v] += add[v];
- if (vl != vr) {
- add[2 * v + 1] += add[v];
- add[2 * v + 2] += add[v];
- }
- add[v] = 0;
- }
- }
- void modify(int v, int vl, int vr, int l, int r, int addValue) {
- push(v, vl, vr);
- if (r < vl || vr < l)
- return;
- if (l <= vl && vr <= r) {
- if (addValue != 0)
- add[v] = addValue;
- push(v, vl, vr);
- return;
- }
- int vm = vl + (vr - vl) / 2;
- modify(2 * v + 1, vl, vm, l, r, addValue);
- modify(2 * v + 2, vm + 1, vr, l, r, addValue);
- t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
- }
- int goDown(int v, int vl, int vr, int target) {
- push(v, vl, vr);
- if (t[v] == target) {
- if (vl == vr) {
- return vl;
- }
- int vm = (vl + vr) / 2;
- int l = goDown(2 * v + 1, vl, vm, target);
- int r = goDown(2 * v + 2, vm + 1, vr, target);
- if (l != -1) return l;
- if (r != -1) return r;
- return -1;
- } else return -1;
- }
- int main() {
- iostream::sync_with_stdio(false);
- int n, max = INT32_MIN, min = 0;
- cin >> n;
- vector<X> coord_array;
- for (int i = 0; i != n; i++) {
- int x1, x2, y1, y2;
- cin >> x1 >> y1 >> x2 >> y2;
- coord_array.emplace_back(X(x1, 1, y1, y2));
- coord_array.emplace_back(X(x2, -1, y1, y2));
- if (y1 < min) min = y1;
- if (y2 > max) max = y2;
- }
- int length = max - min + 1;
- if (min < 0) min = -min;
- sort(coord_array.begin(), coord_array.end(), comparator);
- int ans_x = 0, ans_y = 0, ans_max = 0;
- t = new int[4 * length]{0};
- add = new int[4 * length]{0};
- for (auto x : coord_array) {
- modify(0, 0, length - 1, x.lo + min, x.hi + min, x.type);
- int mx = t[0];
- if (mx > ans_max) {
- int ans = goDown(0, 0, length - 1, mx);
- if (ans != -1) {
- ans_max = mx;
- ans_x = x.coord;
- ans_y = ans - min;
- }
- }
- }
- cout << ans_max << "\n" << ans_x << " " << ans_y;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement