Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // (c) 2020, redotter
- #pragma GCC optimize("Ofast")
- #include <bits/stdc++.h>
- #include <unordered_set>
- #include <unordered_map>
- #include <random>
- #define pb push_back
- #define pf push_front
- #define popb pop_back
- #define popf pop_front
- #define all(a) (a).begin(), (a).end()
- #define sz(a) (ll)((a).size())
- #define heap priority_queue
- #define hash_map unordered_map
- #define hash_set unordered_set
- #define ft first
- #define sd second
- #define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
- #define endl "\n"
- #define y0 y0998244353
- #define y1 y1998244353
- #define die(cond) if (cond) for (;;) {}
- using namespace std;
- typedef int ll;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef pair<ll, ll> pll;
- typedef pair<ld, ld> pld;
- typedef vector<ll> vll;
- typedef set<ll> sll;
- typedef map<ll, ll> mll;
- const ll inf = numeric_limits<ll>::max() / 2;
- const ld eps = 1e-9;
- const ld pi = acosl(-1);
- template<typename T> inline bool mineq(T& a, T b) { return (a > b) ? (a = b, 1) : 0; }
- template<typename T> inline bool maxeq(T& a, T b) { return (a < b) ? (a = b, 1) : 0; }
- void solve(), read();
- signed main() {
- fast;
- read();
- solve();
- return 0;
- }
- struct Vertex {
- ll ind = 0;
- ll max = 0;
- ll push = 0;
- };
- struct SegmentTree {
- ll n;
- vector<Vertex> t;
- SegmentTree() {}
- SegmentTree(ll n_) {
- ll k = log2(n_) + 1;
- n = 1ll << k;
- t.resize(4 * n);
- build();
- }
- void build() {
- for (ll i = 0; i < n; i++) {
- t[n + i].ind = i;
- }
- for (ll i = n - 1; i > 0; i--) {
- t[i].ind = t[2 * i].ind;
- }
- }
- void push(ll v) {
- if (!t[v].push) {
- return;
- }
- t[v].max += t[v].push;
- t[2 * v].push += t[v].push;
- t[2 * v + 1].push += t[v].push;
- t[v].push = 0;
- }
- Vertex merge(Vertex v1, Vertex v2) {
- if (v1.max >= v2.max) {
- return v1;
- } else {
- return v2;
- }
- }
- void upd(ll v, ll tl, ll tr, ll l, ll r, ll x) {
- push(v);
- if (tl > r || tr < l) {
- return;
- }
- if (l <= tl && tr <= r) {
- t[v].push += x;
- push(v);
- return;
- }
- ll tm = (tl + tr) / 2;
- upd(2 * v, tl, tm, l, r, x);
- upd(2 * v + 1, tm + 1, tr, l, r, x);
- t[v] = merge(t[2 * v], t[2 * v + 1]);
- }
- Vertex get() {
- return t[1];
- }
- };
- struct Query {
- ll x1, x2, y1, y2;
- };
- int n;
- vector<Query> qs;
- vll coord;
- vll xs;
- map<ll, vector<Query>> m_add, m_del;
- SegmentTree st;
- void reduce() {
- for (Query q : qs) {
- coord.pb(q.y1);
- coord.pb(q.y2);
- }
- sort(all(coord));
- coord.resize(unique(all(coord)) - coord.begin());
- for (ll i = 0; i < n; i++) {
- qs[i].y1 = lower_bound(coord.begin(), coord.end(), qs[i].y1) - coord.begin();
- qs[i].y2 = lower_bound(coord.begin(), coord.end(), qs[i].y2) - coord.begin();
- }
- }
- void sweep() {
- for (Query q : qs) {
- m_add[q.x1].pb(q);
- m_del[q.x2].pb(q);
- st.upd(1, 0, st.n - 1, q.y1, q.y2, +1);
- xs.pb(q.x1);
- xs.pb(q.x2);
- }
- sort(all(xs));
- xs.resize(unique(all(xs)) - xs.begin());
- }
- void solve() {
- reduce();
- st = SegmentTree(sz(coord));
- sweep();
- ll cur = 0;
- ll ans = -1;
- pll ind = { 0, 0 };
- for (ll x : xs) {
- for (Query q : m_add[x]) {
- ++cur;
- st.upd(1, 0, st.n - 1, q.y1, q.y2, -1);
- }
- Vertex v = st.get();
- if (v.max + cur > ans) {
- ans = v.max + cur;
- ind = { x, v.ind };
- }
- for (Query q : m_del[x]) {
- --cur;
- st.upd(1, 0, st.n - 1, q.y1, q.y2, +1);
- }
- }
- cout << ind.ft << " " << coord[ind.sd] << endl;
- }
- void read() {
- cin >> n;
- qs.resize(n);
- for (ll i = 0; i < n; i++) {
- cin >> qs[i].x1 >> qs[i].x2 >> qs[i].y1 >> qs[i].y2;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement