Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _USE_MATH_DEFINES
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <set>
- #include <queue>
- #include <map>
- #include <string>
- #include <cmath>
- #include <functional>
- #include <algorithm>
- #include <utility>
- #include <stack>
- #include <unordered_map>
- #include <unordered_set>
- #include <iterator>
- #include <fstream>
- #include <iomanip>
- #include <time.h>
- #include <complex>
- //#pragma comment(linker, "/STACK:16777216")
- using namespace std;
- typedef long double C;
- typedef complex<C> P;
- #define X real()
- #define Y imag()
- #define Size(X) (int)X.size()
- //#define int long long
- #define ui unsigned int
- #define mp make_pair
- #define timer fghge
- #define y1 yjyjyju
- #define all(X) (X).begin(), (X).end()
- #define endl '\n'
- struct node {
- int lb, rb;
- int lazy = 0, a = 0;
- node *l = 0, *r = 0;
- pair<int, int> maxim;
- node(int _lb, int _rb) {
- lb = _lb; rb = _rb;
- if (lb + 1 < rb) {
- int t = (lb + rb) / 2;
- l = new node(lb, t);
- r = new node(t, rb);
- }
- maxim = { lb, 0 };
- }
- void add(int x, int _l, int _r) {
- if (_r < lb || _l >= rb)
- return;
- if (_l <= lb && rb - 1 <=_r)
- lazy += x;
- else {
- l->add(x, _l, _r); r->add(x, _l, _r);
- auto a = l->maxim, b = r->maxim;
- a.second += l->lazy;
- b.second += r->lazy;
- if (a.second < b.second)
- swap(a, b);
- maxim = a;
- }
- }
- void push() {
- maxim.second += lazy;
- if (lb + 1 == rb) {
- lazy = 0;
- return;
- }
- l->lazy += lazy; r->lazy += lazy;
- lazy = 0;
- }
- pair<int, int> max(int _l, int _r) {
- push();
- if (_r < lb || _l >= rb)
- return{ -1, -1 };
- if (_l <= lb && _r >= rb - 1)
- return maxim;
- else {
- auto a = l->max(_l, _r), b = r->max(_l, _r);
- if (a.second < b.second)
- swap(a, b);
- return a;
- }
- }
- };
- struct event {
- int x, l, r, d;
- };
- bool cmp(const event &a, const event &b) {
- if (a.x != b.x)
- return a.x < b.x;
- else
- return a.d > b.d;
- }
- signed main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0), cout.tie(0);
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- int HMAX = 2 * 1e6 + 10, b = 1e6 + 1;
- node *t = new node(0, HMAX);
- int n; cin >> n;
- vector<event> a;
- for (int i = 0; i < n; i++) {
- int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
- y1 += b; y2 += b;
- a.push_back({ x1, y1, y2, 1 });
- a.push_back({ x2, y1, y2, -1 });
- }
- sort(all(a), cmp);
- int ans = 0, x, y;
- for (int i = 0; i < 2 * n; i++) {
- t->add(a[i].d, a[i].l, a[i].r);
- auto res = t->max(0, HMAX);
- if (res.second > ans) {
- ans = res.second;
- x = a[i].x;
- y = res.first;
- }
- }
- cout << ans << endl << x << " " << y - b;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement