Advertisement
Guest User

Untitled

a guest
Mar 19th, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.94 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<set>
  5. #include<vector>
  6. #include<set>
  7. #include<map>
  8. #include<algorithm>
  9. #include<queue>
  10.  
  11. using namespace std;
  12. #define ll long long
  13. #define ull unsigned long long
  14. #define pb push_back
  15. #define F first
  16. #define S second
  17. #define leftSon v + v, tl, tm
  18. #define rightSon v + v + 1, tm + 1, tr
  19.  
  20. const int MAXN = (int) 2e5 + 10;
  21. int n;
  22.  
  23. struct SegmentTree
  24. {
  25.     struct Node
  26.     {
  27.         int mx;
  28.         int toAdd;
  29.         int x;
  30.  
  31.         Node()
  32.         {
  33.             x = 0;
  34.             mx = 0;
  35.             toAdd = 0;
  36.         }
  37.     };
  38.  
  39.     vector<Node> t;
  40.  
  41.     SegmentTree()
  42.     {
  43.         t.resize(MAXN * 8);
  44.         for (int i = 0; i < (int) t.size(); i++)
  45.         {
  46.             t[i].x = i;
  47.         }
  48.     }
  49.  
  50.     void push(int v, int tl, int tr)
  51.     {
  52.         if (t[v].toAdd == 0)
  53.         {
  54.             return;
  55.         }
  56.  
  57.         t[v + v].toAdd += t[v].toAdd;
  58.         t[v + v + 1].toAdd += t[v].toAdd;
  59.         int tm = (tl + tr) / 2;
  60.         t[v + v].mx += (tm - tl + 1) * t[v + v].toAdd;
  61.         t[v + v + 1].mx += (tr - tm) * t[v + v + 1].toAdd;
  62.     }
  63.  
  64.     void add(int v, int tl, int tr, int l, int r, int x)
  65.     {
  66.         if (tl > r || tr < l)
  67.         {
  68.             return;
  69.         }
  70.         push(v, tl, tr);
  71.         if (l <= tl && tr <= r)
  72.         {
  73.             t[v].mx += (tr - tl + 1) * x;
  74.             t[v].toAdd = x;
  75.             push(v, tl, tr);
  76.         }
  77.         int tm = (tl + tr) / 2;
  78.         add(leftSon, l, r, x);
  79.         add(rightSon, l, r, x);
  80.  
  81.         if (t[v + v].mx > t[v + v + 1].mx)
  82.         {
  83.             t[v].x = t[v + v].x;
  84.             t[v].mx = t[v + v].mx;
  85.         }
  86.         else
  87.         {
  88.             t[v].x = t[v + v + 1].x;
  89.             t[v].mx = t[v + v + 1].mx;
  90.         }
  91.     }
  92.  
  93. };
  94.  
  95.  
  96. struct coor
  97. {
  98.     coor(int x1, int x2, int y, int val) : x1(x1), x2(x2), y(y), val(val)
  99.     {
  100.     }
  101.  
  102.     int x1;
  103.     int x2;
  104.     int y;
  105.     int val;
  106. };
  107.  
  108. bool cmp(coor a, coor b)
  109. {
  110.     return (a.y < b.y);
  111. }
  112.  
  113.  
  114. struct cor
  115. {
  116.     int val;
  117.     int x;
  118.     int y;
  119. };
  120.  
  121. int main()
  122. {
  123.     ios_base::sync_with_stdio(false);
  124.     cin.tie(nullptr);
  125.  
  126.     cin >> n;
  127.  
  128.     vector<coor> windows;
  129.  
  130.     int k, l, m, j;
  131.     for (int i = 0; i < n; i++)
  132.     {
  133.         cin >> k >> l >> m >> j;
  134.         windows.emplace_back(coor(k, m, l, 1));
  135.         windows.emplace_back(coor(k, m, j, -1));
  136.     }
  137.     SegmentTree T;
  138.     sort(windows.begin(), windows.end(), cmp);
  139.     cor ans{-1, 0, 0};
  140.     for (auto window: windows)
  141.     {
  142.         int x1 = window.x1;
  143.         int x2 = window.x2;
  144.         int val = window.val;
  145.  
  146.         T.add(1, -500000, 500000, x1, x2, val);
  147.         int mx = T.t[1].mx;
  148.         int corMx = T.t[1].x;
  149.  
  150.  
  151.         if (mx > ans.val)
  152.         {
  153.             ans.val = mx;
  154.             ans.x = corMx;
  155.             ans.y = window.y;
  156.         }
  157.     }
  158.     cout << ans.val << endl << ans.x << " " << ans.y;
  159.     return 0;
  160. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement