Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- typedef pair<int, int> pii;
- vector<pii> tree;
- void add(int l, int r, int x, int lx, int rx, int add_m, int c= 1) {
- if (l > rx || lx > r) {
- return;
- }
- if (lx >= l && rx <= r) {
- tree[x].second += add_m;
- tree[x].first += add_m;
- return;
- }
- int m = (rx + lx) / 2;
- //cout << c << " ";
- add(l, r, 2 * x, lx, m, add_m, c+1);
- add(l, r, 2 * x + 1, m + 1, rx, add_m, c+1);
- tree[x].first = max(tree[2*x].first, tree[2*x+1].first) + tree[x].second;
- }
- int maxmy(int x, int lx, int rx) {
- if(rx == lx ){
- return lx;
- }
- int m = (rx + lx) / 2;
- tree[2*x].first += tree[x].second;
- tree[2*x].second += tree[x].second;
- tree[2*x+1].first += tree[x].second;
- tree[2*x+1].second += tree[x].second;
- tree[x].second = 0;
- if(tree[2*x].first > tree[2*x + 1].first){
- return maxmy(2*x, lx, m);
- } else {
- return maxmy(2*x+1, m+1, rx);
- }
- }
- int32_t main() {
- int n, k=2e5 + 1, maxx = 0, maxy = 0, minx = 1e6, miny = 1e6;
- int maxr = 0;
- int x1,y1,x2,y2;
- cin >> n;
- list <pair<pii, int>> start, end;
- for (int i = 0; i < n; i++){
- cin >> x1 >> y1 >> x2 >> y2;
- start.push_back({{x1, y1}, y2 - y1});
- end.push_back({{x2, y2}, y2-y1});
- maxx = max(maxx, x2);
- minx = min(minx, x1);
- }
- start.sort();
- end.sort();
- pii ans;
- tree.assign(4*k, {0, 0});
- bool is_ir = false;
- for (int i = minx; i <= maxx+1; i++){
- while(start.front().first.first == i){
- add(start.front().first.second + 2e5 + 1, start.front().first.second + start.front().second + 2e5 + 1, 1 ,1, 2*k, 1);
- start.pop_front();
- is_ir = true;
- }
- if(is_ir) {
- if (maxr < tree[1].first){
- int tmp = maxmy(1, 1, 2*k) - 2e5 - 1;
- maxr = max (maxr, tree[1].first);
- ans = {i, tmp};
- }
- }
- while(end.front().first.first == i){
- add(end.front().first.second - start.front().second + 2e5 + 1 , end.front().first.second + 2e5 + 1 , 1 ,1, 2*k, -1);
- end.pop_front();
- }
- is_ir = false;
- }
- cout << maxr << endl << ans.first << " " << ans.second;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement