Advertisement
Guest User

Untitled

a guest
Apr 5th, 2020
180
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.35 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define int long long
  4. using namespace std;
  5.  
  6. typedef pair<int, int> pii;
  7. vector<pii> tree;
  8.  
  9. void add(int l, int r, int x, int lx, int rx, int add_m, int c= 1) {
  10.     if (l > rx || lx > r) {
  11.         return;
  12.     }
  13.     if (lx >= l && rx <= r) {
  14.         tree[x].second += add_m;
  15.         tree[x].first += add_m;
  16.         return;
  17.     }
  18.     int m = (rx + lx) / 2;
  19.     //cout << c << " ";
  20.     add(l, r, 2 * x, lx, m, add_m, c+1);
  21.     add(l, r, 2 * x + 1, m + 1, rx, add_m, c+1);
  22.     tree[x].first = max(tree[2*x].first, tree[2*x+1].first) + tree[x].second;
  23. }
  24.  
  25.  
  26.  
  27. int maxmy(int x, int lx, int rx) {
  28.     if(rx == lx ){
  29.         return lx;
  30.     }
  31.     int m = (rx + lx) / 2;
  32.     tree[2*x].first += tree[x].second;
  33.     tree[2*x].second += tree[x].second;
  34.     tree[2*x+1].first += tree[x].second;
  35.     tree[2*x+1].second += tree[x].second;
  36.     tree[x].second = 0;
  37.  
  38.     if(tree[2*x].first > tree[2*x + 1].first){
  39.         return maxmy(2*x, lx, m);
  40.     } else {
  41.         return maxmy(2*x+1, m+1, rx);
  42.     }
  43. }
  44.  
  45.  
  46. int32_t main() {
  47.     int n, k=2e5 + 1, maxx = 0, maxy = 0, minx = 1e6, miny = 1e6;
  48.     int maxr = 0;
  49.     int x1,y1,x2,y2;
  50.     cin >> n;
  51.     list <pair<pii, int>> start, end;
  52.     for (int i = 0; i < n; i++){
  53.         cin >> x1 >> y1 >> x2 >> y2;
  54.         start.push_back({{x1, y1}, y2 - y1});
  55.         end.push_back({{x2, y2}, y2-y1});
  56.  
  57.         maxx = max(maxx, x2);
  58.         minx = min(minx, x1);
  59.  
  60.     }
  61.     start.sort();
  62.     end.sort();
  63.  
  64.     pii ans;
  65.     tree.assign(4*k, {0, 0});
  66.     bool is_ir = false;
  67.     for (int i = minx; i <= maxx+1; i++){
  68.         while(start.front().first.first == i){
  69.             add(start.front().first.second + 2e5 + 1, start.front().first.second + start.front().second + 2e5 + 1, 1 ,1, 2*k, 1);
  70.             start.pop_front();
  71.             is_ir = true;
  72.         }
  73.         if(is_ir) {
  74.             if (maxr < tree[1].first){
  75.                 int tmp = maxmy(1, 1, 2*k) - 2e5 - 1;
  76.                 maxr = max (maxr, tree[1].first);
  77.                 ans = {i, tmp};
  78.             }
  79.         }
  80.         while(end.front().first.first == i){
  81.             add(end.front().first.second - start.front().second + 2e5 + 1 , end.front().first.second + 2e5 + 1 , 1 ,1, 2*k, -1);
  82.             end.pop_front();
  83.         }
  84.         is_ir = false;
  85.     }
  86.     cout << maxr << endl << ans.first << " " << ans.second;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement