Advertisement
Guest User

Untitled

a guest
Mar 24th, 2018
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.79 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. class X {
  8. public:
  9.  
  10.     friend bool operator==(X &x1, X &x2) {
  11.         return (x1.type == x2.type && x1.coord == x2.coord && x1.lo == x2.lo && x1.hi == x2.hi);
  12.     }
  13.  
  14.     int coord;
  15.     int type;
  16.     int lo;
  17.     int hi;
  18.  
  19.     X(int c, int t, int l, int h) {
  20.         coord = c;
  21.         type = t;
  22.         lo = l;
  23.         hi = h;
  24.     }
  25.  
  26. };
  27.  
  28. int* t;
  29. int* add;
  30.  
  31. struct {
  32.     bool operator()(X a, X b) const {
  33.         if (a.coord == b.coord) {
  34.             return a.type > b.type;
  35.         }
  36.         return a.coord < b.coord;
  37.     }
  38. } comparator;
  39.  
  40. void push(int v, int vl, int vr) {
  41.     if (add[v] != 0) {
  42.         t[v] += add[v];
  43.         if (vl != vr) {
  44.             add[2 * v + 1] += add[v];
  45.             add[2 * v + 2] += add[v];
  46.         }
  47.         add[v] = 0;
  48.     }
  49. }
  50.  
  51. void modify(int v, int vl, int vr, int l, int r, int addValue) {
  52.     push(v, vl, vr);
  53.     if (r < vl || vr < l)
  54.         return;
  55.     if (l <= vl && vr <= r) {
  56.         if (addValue != 0)
  57.             add[v] = addValue;
  58.         push(v, vl, vr);
  59.         return;
  60.     }
  61.     int vm = vl + (vr - vl) / 2;
  62.     modify(2 * v + 1, vl, vm, l, r, addValue);
  63.     modify(2 * v + 2, vm + 1, vr, l, r, addValue);
  64.     t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
  65. }
  66.  
  67. int goDown(int v, int vl, int vr, int target) {
  68.     push(v, vl, vr);
  69.     if (t[v] == target) {
  70.         if (vl == vr) {
  71.             return vl;
  72.         }
  73.         int vm = (vl + vr) / 2;
  74.         int l = goDown(2 * v + 1, vl, vm, target);
  75.         int r = goDown(2 * v + 2, vm + 1, vr, target);
  76.         if (l != -1) return l;
  77.         if (r != -1) return r;
  78.         return -1;
  79.     } else return -1;
  80. }
  81.  
  82. int main() {
  83.     iostream::sync_with_stdio(false);
  84.     int n, max = INT32_MIN, min = 0;
  85.     cin >> n;
  86.     vector<X> coord_array;
  87.     for (int i = 0; i != n; i++) {
  88.         int x1, x2, y1, y2;
  89.         cin >> x1 >> y1 >> x2 >> y2;
  90.         coord_array.emplace_back(X(x1, 1, y1, y2));
  91.         coord_array.emplace_back(X(x2, -1, y1, y2));
  92.         if (y1 < min) min = y1;
  93.         if (y2 > max) max = y2;
  94.     }
  95.     int length = max - min + 1;
  96.     if (min < 0) min = -min;
  97.     sort(coord_array.begin(), coord_array.end(), comparator);
  98.     int ans_x = 0, ans_y = 0, ans_max = 0;
  99.     t = new int[4 * length]{0};
  100.     add = new int[4 * length]{0};
  101.     for (auto x : coord_array) {
  102.         modify(0, 0, length - 1, x.lo + min, x.hi + min, x.type);
  103.         int mx = t[0];
  104.         if (mx > ans_max) {
  105.             int ans = goDown(0, 0, length - 1, mx);
  106.             if (ans != -1) {
  107.                 ans_max = mx;
  108.                 ans_x = x.coord;
  109.                 ans_y = ans - min;
  110.             }
  111.         }
  112.     }
  113.     cout << ans_max << "\n" << ans_x << " " << ans_y;
  114.     return 0;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement