Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /// author: Mr.Hakimov
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- #define pb push_back
- #define pf push_front
- #define Pb pop_back
- #define Pf pop_front
- #define all(x) (x).begin(), (x).end()
- #define fin(s) freopen(s, "r", stdin);
- #define fout(s) freopen(s, "w", stdout);
- /* Just some advices:
- 1. If I use set/multiset, I will check it - is it correct to use set/multiset in a problem?
- 2. If I can't solve problem, I must write a program, which could help me to understand it much more better)
- ...
- */
- using namespace std;
- typedef long long LL;
- typedef long double LD;
- int TN = 1;
- int n;
- const int N = 400001;
- const int delta = 200001;
- struct query {
- int l;
- int r;
- int x;
- int y;
- query(int L, int R, int X, int Y) {
- l = L;
- r = R;
- x = X;
- y = Y;
- }
- };
- vector < query > q;
- vector < pair < int, int > > t(4 * N, {0, 0});
- vector < int > d(4 * N, 0);
- bool comp(query a, query b) {
- return a.x < b.x || a.x == b.x && a.y > b.y;
- }
- void build(int v, int l, int r) {
- if (l == r) {
- t[v].se = l;
- return;
- }
- int m = (l + r) / 2;
- build(2 * v, l, m);
- build(2 * v + 1, m + 1, r);
- if (t[2 * v].fi > t[2 * v + 1].fi) {
- t[v] = t[2 * v];
- } else {
- t[v] = t[2 * v + 1];
- }
- }
- void push(int v, int len) {
- if (d[v] != 0) {
- if (len >= 2) {
- d[2 * v] += d[v];
- d[2 * v + 1] += d[v];
- }
- t[v].fi += d[v];
- d[v] = 0;
- }
- }
- void set_(int v, int l, int r, int L, int R, int x) {
- push(v, r - l + 1);
- if (L > r || R < l) {
- return;
- }
- if (L <= l && r <= R) {
- d[v] += x;
- push(v, r - l + 1);
- return;
- }
- int m = (l + r) / 2;
- set_(2 * v, l, m, L, R, x);
- set_(2 * v + 1, m + 1, r, L, R, x);
- if (t[2 * v] > t[2 * v + 1]) {
- t[v] = t[2 * v];
- } else {
- t[v] = t[2 * v + 1];
- }
- }
- int get(int v, int l, int r, int L, int R) {
- push(v, r - l + 1);
- if (L > r || R < l) {
- return -1;
- }
- if (L <= l && r <= R) {
- return v;
- }
- int m = (l + r) / 2;
- int sl = get(2 * v, l, m, L, R);
- int sr = get(2 * v + 1, m + 1, r, L, R);
- if (sl < 0) {
- return sr;
- }
- if (sr < 0) {
- return sl;
- }
- if (t[sl].fi > t[sr].fi) {
- return sl;
- } else {
- return sr;
- }
- }
- void solve() {
- cin >> n;
- for (int i = 0; i < n; i++) {
- int x1, y1, x2, y2;
- cin >> x1 >> y1 >> x2 >> y2;
- q.pb(query(y1, y2, x1, 1));
- q.pb(query(y1, y2, x2, -1));
- }
- build(1, 0, N);
- sort(q.begin(), q.end(), comp);
- int res = 0;
- pair < int, int > mx;
- for (int i = 0; i < (int)q.size(); i++) {
- set_(1, 0, N, q[i].l + delta, q[i].r + delta, q[i].y);
- int v = get(1, 0, N, 0, N);
- if (t[v].fi > res) {
- mx = {q[i].x, t[v].se - delta};
- res = t[v].fi;
- }
- }
- cout << res << endl;
- cout << mx.fi << " " << mx.se << endl;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(nullptr); cout.tie(nullptr);
- /// =========================================
- /// fin("input.txt"); fout("output.txt");
- /// fin("stars.in"); fout("stars.out");
- /// cin >> TN;
- /// =========================================
- while (TN--) solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement