Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2019
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.43 KB | None | 0 0
  1. /// author: Mr.Hakimov
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define pf push_front
  9. #define Pb pop_back
  10. #define Pf pop_front
  11. #define all(x) (x).begin(), (x).end()
  12. #define fin(s) freopen(s, "r", stdin);
  13. #define fout(s) freopen(s, "w", stdout);
  14.  
  15. /* Just some advices:
  16. 1. If I use set/multiset, I will check it - is it correct to use set/multiset in a problem?
  17. 2. If I can't solve problem, I must write a program, which could help me to understand it much more better)
  18. ...
  19. */
  20.  
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef long double LD;
  25.  
  26. int TN = 1;
  27. int n;
  28. const int N = 400001;
  29. const int delta = 200001;
  30.  
  31. struct query {
  32.     int l;
  33.     int r;
  34.     int x;
  35.     int y;
  36.     query(int L, int R, int X, int Y) {
  37.         l = L;
  38.         r = R;
  39.         x = X;
  40.         y = Y;
  41.     }
  42. };
  43.  
  44. vector < query > q;
  45. vector < pair < int, int > > t(4 * N, {0, 0});
  46. vector < int > d(4 * N, 0);
  47.  
  48. bool comp(query a, query b) {
  49.     return a.x < b.x || a.x == b.x && a.y > b.y;
  50. }
  51.  
  52. void build(int v, int l, int r) {
  53.     if (l == r) {
  54.         t[v].se = l;
  55.         return;
  56.     }
  57.     int m = (l + r) / 2;
  58.     build(2 * v, l, m);
  59.     build(2 * v + 1, m + 1, r);
  60.     if (t[2 * v].fi > t[2 * v + 1].fi) {
  61.         t[v] = t[2 * v];
  62.     } else {
  63.         t[v] = t[2 * v + 1];
  64.     }
  65. }
  66.  
  67. void push(int v, int len) {
  68.     if (d[v] != 0) {
  69.         if (len >= 2) {
  70.             d[2 * v] += d[v];
  71.             d[2 * v + 1] += d[v];
  72.         }
  73.         t[v].fi += d[v];
  74.         d[v] = 0;
  75.     }
  76. }
  77.  
  78. void set_(int v, int l, int r, int L, int R, int x) {
  79.     push(v, r - l + 1);
  80.     if (L > r || R < l) {
  81.         return;
  82.     }
  83.     if (L <= l && r <= R) {
  84.         d[v] += x;
  85.         push(v, r - l + 1);
  86.         return;
  87.     }
  88.     int m = (l + r) / 2;
  89.     set_(2 * v, l, m, L, R, x);
  90.     set_(2 * v + 1, m + 1, r, L, R, x);
  91.     if (t[2 * v] > t[2 * v + 1]) {
  92.         t[v] = t[2 * v];
  93.     } else {
  94.         t[v] = t[2 * v + 1];
  95.     }
  96. }
  97.  
  98. int get(int v, int l, int r, int L, int R) {
  99.     push(v, r - l + 1);
  100.     if (L > r || R < l) {
  101.         return -1;
  102.     }
  103.     if (L <= l && r <= R) {
  104.         return v;
  105.     }
  106.     int m = (l + r) / 2;
  107.     int sl = get(2 * v, l, m, L, R);
  108.     int sr = get(2 * v + 1, m + 1, r, L, R);
  109.     if (sl < 0) {
  110.         return sr;
  111.     }
  112.     if (sr < 0) {
  113.         return sl;
  114.     }
  115.     if (t[sl].fi > t[sr].fi) {
  116.         return sl;
  117.     } else {
  118.         return sr;
  119.     }
  120. }
  121.  
  122. void solve() {
  123.     cin >> n;
  124.     for (int i = 0; i < n; i++) {
  125.         int x1, y1, x2, y2;
  126.         cin >> x1 >> y1 >> x2 >> y2;
  127.         q.pb(query(y1, y2, x1, 1));
  128.         q.pb(query(y1, y2, x2, -1));
  129.     }
  130.     build(1, 0, N);
  131.     sort(q.begin(), q.end(), comp);
  132.     int res = 0;
  133.     pair < int, int > mx;
  134.     for (int i = 0; i < (int)q.size(); i++) {
  135.         set_(1, 0, N, q[i].l + delta, q[i].r + delta, q[i].y);
  136.         int v = get(1, 0, N, 0, N);
  137.         if (t[v].fi > res) {
  138.             mx = {q[i].x, t[v].se - delta};
  139.             res = t[v].fi;
  140.         }
  141.     }
  142.     cout << res << endl;
  143.     cout << mx.fi << " " << mx.se << endl;
  144. }
  145.  
  146. int main() {
  147.     ios_base::sync_with_stdio(0);
  148.     cin.tie(nullptr); cout.tie(nullptr);
  149.     /// =========================================
  150.     /// fin("input.txt"); fout("output.txt");
  151.     /// fin("stars.in"); fout("stars.out");
  152.     /// cin >> TN;
  153.     /// =========================================
  154.     while (TN--) solve();
  155.     return 0;
  156. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement