Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:367077216")
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <set>
- #include <map>
- #include <queue>
- #include <algorithm>
- #include <iomanip>
- using namespace std;
- typedef long long ll;
- struct edge {
- int low_y; int high_y; int x; int type;
- edge(int _l, int _h, int _x, int _t) {
- this->low_y = _l;
- this->high_y = _h;
- this->x = _x;
- this->type = _t;
- }
- };
- struct point {
- int x; int y; int cnt;
- point(int _x, int _y, int _c) {
- this->x = _x;
- this->y = _y;
- this->cnt = _c;
- }
- };
- bool comp(edge f, edge s) {
- if (f.x == s.x) {
- if (f.type == s.type) {
- if (f.low_y == s.low_y) {
- return f.high_y < s.high_y;
- }
- return f.low_y < s.low_y;
- }
- return f.type > s.type;
- }
- return f.x < s.x;
- }
- struct node {
- int max; int ex;
- node(int _m, int _e) {
- this->max = _m;
- this->ex = _e;
- }
- };
- int n; int N = -3e6 - 3;
- vector<edge> a;
- int ans = -1; pair<int, int> ans_cs = { -1, -1 };
- vector<node> tree;
- void push(int v, int tl, int tr) {
- if (tl == tr) return;
- tree[v].max += tree[v].ex;
- tree[2 * v].ex += tree[v].ex;
- tree[2 * v + 1].ex += tree[v].ex;
- tree[v].ex = 0;
- }
- void change(int v, int tl, int tr, int l, int r, int type) {
- push(v, tl, tr);
- if (l > r) {
- return;
- }
- else if (tl == l && tr == r) {
- tree[v].ex += type;
- }
- else {
- int tm = (tl + tr) / 2;
- change(2 * v, tl, tm, l, min(tm, r), type);
- change(2 * v + 1, tm + 1, tr, max(tm + 1, l), r, type);
- tree[v].max = max(tree[2 * v].max + tree[2 * v].ex,
- tree[2 * v + 1].max + tree[2 * v + 1].ex);
- }
- }
- pair<int, int> find(int v, int tl, int tr) {
- push(v, tl, tr);
- if (tl == tr) return { tree[v].max + tree[v].ex, tl };
- else {
- int tm = (tl + tr) / 2;
- if (tree[2 * v].max + tree[2 * v].ex >= tree[2 * v + 1].max + tree[2 * v + 1].ex) {
- return find(2 * v, tl, tm);
- }
- else {
- return find(2 * v + 1, tm + 1, tr);
- }
- }
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- int d = 2000001;
- cin >> n;
- for (int i = 0; i < n; ++i) {
- int x1, y1, x2, y2;
- cin >> x1 >> y1 >> x2 >> y2;
- x1 += d; y1 += d;
- x2 += d; y2 += d;
- N = max(N, y2);
- a.push_back({ y1, y2, x1, 1 });
- a.push_back({ y1, y2, x2, -1 });
- }
- sort(a.begin(), a.end(), comp);
- tree.resize(4 * N, { 0, 0 });
- for (edge cur : a) {
- change(1, 0, N, cur.low_y, cur.high_y, cur.type);
- if (cur.type == 1) {
- pair<int, int> cur_best = find(1, 0, N);
- if (cur_best.first > ans) {
- ans = cur_best.first;
- ans_cs = { cur.x, cur_best.second };
- }
- }
- }
- cout << ans << "\n" << ans_cs.first - d << " " << ans_cs.second - d;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement