Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<set>
- #include<vector>
- #include<set>
- #include<map>
- #include<algorithm>
- #include<queue>
- using namespace std;
- #define ll long long
- #define ull unsigned long long
- #define pb push_back
- #define F first
- #define S second
- #define leftSon v + v, tl, tm
- #define rightSon v + v + 1, tm + 1, tr
- const int MAXN = (int) 2e5 + 10;
- int n;
- struct SegmentTree
- {
- struct Node
- {
- int mx;
- int toAdd;
- int x;
- Node()
- {
- x = 0;
- mx = 0;
- toAdd = 0;
- }
- };
- vector<Node> t;
- SegmentTree()
- {
- t.resize(MAXN * 8);
- for (int i = 0; i < (int) t.size(); i++)
- {
- t[i].x = i;
- }
- }
- void push(int v, int tl, int tr)
- {
- if (t[v].toAdd == 0)
- {
- return;
- }
- t[v + v].toAdd += t[v].toAdd;
- t[v + v + 1].toAdd += t[v].toAdd;
- int tm = (tl + tr) / 2;
- t[v + v].mx += (tm - tl + 1) * t[v + v].toAdd;
- t[v + v + 1].mx += (tr - tm) * t[v + v + 1].toAdd;
- }
- void add(int v, int tl, int tr, int l, int r, int x)
- {
- if (tl > r || tr < l)
- {
- return;
- }
- push(v, tl, tr);
- if (l <= tl && tr <= r)
- {
- t[v].mx += (tr - tl + 1) * x;
- t[v].toAdd = x;
- push(v, tl, tr);
- }
- int tm = (tl + tr) / 2;
- add(leftSon, l, r, x);
- add(rightSon, l, r, x);
- if (t[v + v].mx > t[v + v + 1].mx)
- {
- t[v].x = t[v + v].x;
- t[v].mx = t[v + v].mx;
- }
- else
- {
- t[v].x = t[v + v + 1].x;
- t[v].mx = t[v + v + 1].mx;
- }
- }
- };
- struct coor
- {
- coor(int x1, int x2, int y, int val) : x1(x1), x2(x2), y(y), val(val)
- {
- }
- int x1;
- int x2;
- int y;
- int val;
- };
- bool cmp(coor a, coor b)
- {
- return (a.y < b.y);
- }
- struct cor
- {
- int val;
- int x;
- int y;
- };
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cin >> n;
- vector<coor> windows;
- int k, l, m, j;
- for (int i = 0; i < n; i++)
- {
- cin >> k >> l >> m >> j;
- windows.emplace_back(coor(k, m, l, 1));
- windows.emplace_back(coor(k, m, j, -1));
- }
- SegmentTree T;
- sort(windows.begin(), windows.end(), cmp);
- cor ans{-1, 0, 0};
- for (auto window: windows)
- {
- int x1 = window.x1;
- int x2 = window.x2;
- int val = window.val;
- T.add(1, -500000, 500000, x1, x2, val);
- int mx = T.t[1].mx;
- int corMx = T.t[1].x;
- if (mx > ans.val)
- {
- ans.val = mx;
- ans.x = corMx;
- ans.y = window.y;
- }
- }
- cout << ans.val << endl << ans.x << " " << ans.y;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement