Advertisement
he_obviously

Untitled

Oct 7th, 2020
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.12 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:367077216")
  2.  
  3. #include <iostream>
  4. #include <cmath>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <queue>
  9. #include <algorithm>
  10. #include <iomanip>
  11.  
  12. using namespace std;
  13.  
  14. typedef long long ll;
  15.  
  16. struct edge {
  17.     int low_y; int high_y; int x; int type;
  18.     edge(int _l, int _h, int _x, int _t) {
  19.         this->low_y = _l;
  20.         this->high_y = _h;
  21.         this->x = _x;
  22.         this->type = _t;
  23.     }
  24. };
  25.  
  26. struct point {
  27.     int x; int y; int cnt;
  28.     point(int _x, int _y, int _c) {
  29.         this->x = _x;
  30.         this->y = _y;
  31.         this->cnt = _c;
  32.     }
  33. };
  34.  
  35. bool comp(edge f, edge s) {
  36.     if (f.x == s.x) {
  37.         if (f.type == s.type) {
  38.             if (f.low_y == s.low_y) {
  39.                 return f.high_y < s.high_y;
  40.             }
  41.             return f.low_y < s.low_y;
  42.         }
  43.         return f.type > s.type;
  44.     }
  45.     return f.x < s.x;
  46. }
  47.  
  48. struct node {
  49.     int max; int ex;
  50.     node(int _m, int _e) {
  51.         this->max = _m;
  52.         this->ex = _e;
  53.     }
  54. };
  55.  
  56. int n; int N = -3e6 - 3;
  57. vector<edge> a;
  58. int ans = -1; pair<int, int> ans_cs = { -1, -1 };
  59. vector<node> tree;
  60.  
  61. void push(int v, int tl, int tr) {
  62.     if (tl == tr) return;
  63.     tree[v].max += tree[v].ex;
  64.     tree[2 * v].ex += tree[v].ex;
  65.     tree[2 * v + 1].ex += tree[v].ex;
  66.     tree[v].ex = 0;
  67. }
  68.  
  69. void change(int v, int tl, int tr, int l, int r, int type) {
  70.     push(v, tl, tr);
  71.     if (l > r) {
  72.         return;
  73.     }
  74.     else if (tl == l && tr == r) {
  75.         tree[v].ex += type;
  76.     }
  77.     else {
  78.         int tm = (tl + tr) / 2;
  79.         change(2 * v, tl, tm, l, min(tm, r), type);
  80.         change(2 * v + 1, tm + 1, tr, max(tm + 1, l), r, type);
  81.         tree[v].max = max(tree[2 * v].max + tree[2 * v].ex,
  82.             tree[2 * v + 1].max + tree[2 * v + 1].ex);
  83.     }
  84. }
  85.  
  86. pair<int, int> find(int v, int tl, int tr) {
  87.     push(v, tl, tr);
  88.     if (tl == tr) return { tree[v].max + tree[v].ex, tl };
  89.     else {
  90.         int tm = (tl + tr) / 2;
  91.         if (tree[2 * v].max + tree[2 * v].ex >= tree[2 * v + 1].max + tree[2 * v + 1].ex) {
  92.             return find(2 * v, tl, tm);
  93.         }
  94.         else {
  95.             return find(2 * v + 1, tm + 1, tr);
  96.         }
  97.     }
  98. }
  99.  
  100. int main() {
  101.  
  102.     ios_base::sync_with_stdio(0);
  103.     cin.tie(0); cout.tie(0);
  104.  
  105.     int d = 2000001;
  106.  
  107.     cin >> n;
  108.  
  109.     for (int i = 0; i < n; ++i) {
  110.         int x1, y1, x2, y2;
  111.         cin >> x1 >> y1 >> x2 >> y2;
  112.         x1 += d; y1 += d;
  113.         x2 += d; y2 += d;
  114.         N = max(N, y2);
  115.         a.push_back({ y1, y2, x1, 1 });
  116.         a.push_back({ y1, y2, x2, -1 });
  117.     }
  118.  
  119.     sort(a.begin(), a.end(), comp);
  120.  
  121.     tree.resize(4 * N, { 0, 0 });
  122.  
  123.     for (edge cur : a) {
  124.         change(1, 0, N, cur.low_y, cur.high_y, cur.type);
  125.         if (cur.type == 1) {
  126.             pair<int, int> cur_best = find(1, 0, N);
  127.             if (cur_best.first > ans) {
  128.                 ans = cur_best.first;
  129.                 ans_cs = { cur.x, cur_best.second };
  130.             }
  131.         }
  132.     }
  133.  
  134.     cout << ans << "\n" << ans_cs.first - d << " " << ans_cs.second - d;
  135.  
  136.     return 0;
  137. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement