Advertisement
Guest User

meow

a guest
Feb 17th, 2020
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.52 KB | None | 0 0
  1. // (c) 2020, redotter
  2. #pragma GCC optimize("Ofast")
  3. #include <bits/stdc++.h>
  4. #include <unordered_set>
  5. #include <unordered_map>
  6. #include <random>
  7. #define pb push_back
  8. #define pf push_front
  9. #define popb pop_back
  10. #define popf pop_front
  11. #define all(a) (a).begin(), (a).end()
  12. #define sz(a) (ll)((a).size())
  13. #define heap priority_queue
  14. #define hash_map unordered_map
  15. #define hash_set unordered_set
  16. #define ft first
  17. #define sd second
  18. #define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  19. #define endl "\n"
  20. #define y0 y0998244353
  21. #define y1 y1998244353
  22. #define die(cond) if (cond) for (;;) {}
  23. using namespace std;
  24. typedef int ll;
  25. typedef unsigned long long ull;
  26. typedef long double ld;
  27. typedef pair<ll, ll> pll;
  28. typedef pair<ld, ld> pld;
  29. typedef vector<ll> vll;
  30. typedef set<ll> sll;
  31. typedef map<ll, ll> mll;
  32. const ll inf = numeric_limits<ll>::max() / 2;
  33. const ld eps = 1e-9;
  34. const ld pi = acosl(-1);
  35. template<typename T> inline bool mineq(T& a, T b) { return (a > b) ? (a = b, 1) : 0; }
  36. template<typename T> inline bool maxeq(T& a, T b) { return (a < b) ? (a = b, 1) : 0; }
  37.  
  38. void solve(), read();
  39.  
  40. signed main() {
  41.     fast;
  42.     read();
  43.     solve();
  44.     return 0;
  45. }
  46.  
  47. struct Vertex {
  48.     ll ind = 0;
  49.     ll max = 0;
  50.     ll push = 0;
  51. };
  52.  
  53. struct SegmentTree {
  54.     ll n;
  55.     vector<Vertex> t;
  56.     SegmentTree() {}
  57.     SegmentTree(ll n_) {
  58.         ll k = log2(n_) + 1;
  59.         n = 1ll << k;
  60.         t.resize(4 * n);
  61.         build();
  62.     }
  63.     void build() {
  64.         for (ll i = 0; i < n; i++) {
  65.             t[n + i].ind = i;
  66.         }
  67.         for (ll i = n - 1; i > 0; i--) {
  68.             t[i].ind = t[2 * i].ind;
  69.         }
  70.     }
  71.     void push(ll v) {
  72.         if (!t[v].push) {
  73.             return;
  74.         }
  75.         t[v].max += t[v].push;
  76.         t[2 * v].push += t[v].push;
  77.         t[2 * v + 1].push += t[v].push;
  78.         t[v].push = 0;
  79.     }
  80.     Vertex merge(Vertex v1, Vertex v2) {
  81.         if (v1.max >= v2.max) {
  82.             return v1;
  83.         } else {
  84.             return v2;
  85.         }
  86.     }
  87.     void upd(ll v, ll tl, ll tr, ll l, ll r, ll x) {
  88.         push(v);
  89.         if (tl > r || tr < l) {
  90.             return;
  91.         }
  92.         if (l <= tl && tr <= r) {
  93.             t[v].push += x;
  94.             push(v);
  95.             return;
  96.         }
  97.         ll tm = (tl + tr) / 2;
  98.         upd(2 * v, tl, tm, l, r, x);
  99.         upd(2 * v + 1, tm + 1, tr, l, r, x);
  100.         t[v] = merge(t[2 * v], t[2 * v + 1]);
  101.     }
  102.     Vertex get() {
  103.         return t[1];
  104.     }
  105. };
  106.  
  107. struct Query {
  108.     ll x1, x2, y1, y2;
  109. };
  110.  
  111. int n;
  112. vector<Query> qs;
  113. vll coord;
  114. vll xs;
  115. map<ll, vector<Query>> m_add, m_del;
  116. SegmentTree st;
  117.  
  118. void reduce() {
  119.     for (Query q : qs) {
  120.         coord.pb(q.y1);
  121.         coord.pb(q.y2);
  122.     }
  123.     sort(all(coord));
  124.     coord.resize(unique(all(coord)) - coord.begin());
  125.     for (ll i = 0; i < n; i++) {
  126.         qs[i].y1 = lower_bound(coord.begin(), coord.end(), qs[i].y1) - coord.begin();
  127.         qs[i].y2 = lower_bound(coord.begin(), coord.end(), qs[i].y2) - coord.begin();
  128.     }
  129. }
  130.  
  131. void sweep() {
  132.     for (Query q : qs) {
  133.         m_add[q.x1].pb(q);
  134.         m_del[q.x2].pb(q);
  135.         st.upd(1, 0, st.n - 1, q.y1, q.y2, +1);
  136.         xs.pb(q.x1);
  137.         xs.pb(q.x2);
  138.     }
  139.     sort(all(xs));
  140.     xs.resize(unique(all(xs)) - xs.begin());
  141. }
  142.  
  143. void solve() {
  144.     reduce();
  145.     st = SegmentTree(sz(coord));
  146.     sweep();
  147.     ll cur = 0;
  148.     ll ans = -1;
  149.     pll ind = { 0, 0 };
  150.     for (ll x : xs) {
  151.         for (Query q : m_add[x]) {
  152.             ++cur;
  153.             st.upd(1, 0, st.n - 1, q.y1, q.y2, -1);
  154.         }
  155.         Vertex v = st.get();
  156.         if (v.max + cur > ans) {
  157.             ans = v.max + cur;
  158.             ind = { x, v.ind };
  159.         }
  160.         for (Query q : m_del[x]) {
  161.             --cur;
  162.             st.upd(1, 0, st.n - 1, q.y1, q.y2, +1);
  163.         }
  164.     }
  165.     cout << ind.ft << " " << coord[ind.sd] << endl;
  166. }
  167.  
  168. void read() {
  169.     cin >> n;
  170.     qs.resize(n);
  171.     for (ll i = 0; i < n; i++) {
  172.         cin >> qs[i].x1 >> qs[i].x2 >> qs[i].y1 >> qs[i].y2;
  173.     }
  174. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement