Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <fstream>
- #include <cstdio>
- #include <cmath>
- #include <ctime>
- #include <cstring>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <map>
- #include <set>
- #include <queue>
- #include <deque>
- #include <bitset>
- #include <cassert>
- #include <tuple>
- #include <unordered_map>
- #include <unordered_set>
- using namespace std;
- const int maxc = (int)32;
- const int dd = (int)7e4 + 7;
- const int MOD = (int)1e9 + 9;
- const int INF = (int)1e9 + 7;
- const long long LINF = (1ll) * 1e18 + 7;
- const int P = (int)239017;
- #define ll long long
- #define TIME clock() * 1.0 / CLOCKS_PER_SEC
- #define err(x) cerr << __FUNCTION__ << " (" << __LINE__ << \
- "): [" << #x << "] = " << x;
- #define tm WHAT_THE_FUCK_DOES_THIS_VARIABLE_DOES
- void ujugajuga(bool tl228) {
- #ifdef starcall
- freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
- #else
- //freopen("roads.in", "r", stdin); freopen("roads.out", "w", stdout);
- //freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
- #endif
- //srand(time(0));
- srand(atoi("Dlya porazeniya"));
- if (tl228) {
- ios_base::sync_with_stdio(0);
- cin.tie();
- cout.tie();
- }
- }
- struct event {
- int from, to, type, day;
- event() {}
- event(int _from, int _to, int _type, int _day) {
- from = _from, to = _to, type = _type, day = _day;
- }
- bool operator < (event b) {
- if (from != b.from)
- return from < b.from;
- if (type != b.type)
- return type < b.type;
- return day < b.day;
- }
- };
- pair<int, int> t[4 * dd + 7];
- int add[4 * dd + 7];
- void push(int v, int tl, int tr) {
- if (tr - tl > 1) {
- add[v * 2] += add[v];
- add[v * 2 + 1] += add[v];
- }
- t[v].first += add[v];
- add[v] = 0;
- }
- void upd(int v, int tl, int tr, int l, int r, int val) {
- push(v, tl, tr);
- if (r <= tl || l >= tr) {
- return;
- }
- if (r >= tr && tl >= l) {
- add[v] += val;
- if (tr - 1 == tl)
- t[v].second = tl;
- push(v, tl, tr);
- return;
- }
- int tm = (tl + tr) / 2;
- upd(v * 2, tl, tm, l, r, val);
- upd(v * 2 + 1, tm, tr, l, r, val);
- t[v] = max(t[v * 2], t[v * 2 + 1]);
- }
- pair<int, int> get(int v, int tl, int tr, int l, int r) {
- push(v, tl, tr);
- if (r <= tl || l >= tr) {
- return make_pair(-INF, -INF);
- }
- if (r >= tr && tl >= l) {
- return t[v];
- }
- int tm = (tl + tr) / 2;
- push(v, tl, tr);
- return max(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm, tr, l, r));
- }
- int n;
- vector<pair<int, int> > a, b;
- pair<int, int> rr[dd];
- map<long long, int> w;
- vector<int> was;
- int main() {
- ujugajuga(0);
- cin >> n;
- vector<event> g;
- for (int i = 0; i < n; i++) {
- int q, w, e, r;
- scanf("%d %d %d %d", &q, &w, &e, &r);
- a.push_back({ q, w }), b.push_back({ e, r });
- was.push_back(q);
- was.push_back(w);
- was.push_back(e);
- was.push_back(r);
- //upd(1, 0, dd, e, r + 1, 1);
- }
- sort(was.begin(), was.end());
- was.resize(unique(was.begin(), was.end()) - was.begin());
- for (int i = 0; i < was.size(); i++) {
- w[was[i]] = i;
- }
- for (int i = 0; i < n; i++) {
- a[i].first = lower_bound(was.begin(), was.end(), a[i].first) - was.begin();
- a[i].second = lower_bound(was.begin(), was.end(), a[i].second) - was.begin();
- b[i].first = lower_bound(was.begin(), was.end(), b[i].first) - was.begin();
- b[i].second = lower_bound(was.begin(), was.end(), b[i].second) - was.begin();
- upd(1, 0, dd, b[i].first, b[i].second + 1, 1);
- }
- for (int i = 0; i < n; i++) {
- g.push_back({ a[i].first, a[i].second, -1, i });
- g.push_back({ a[i].second, a[i].first, 1, i });
- }
- sort(g.begin(), g.end());
- int bal = 0;
- int ans1 = 0, ans2 = 0;
- int ans = 0;
- for (auto ev : g) {
- if (ev.type == -1) {
- upd(1, 0, dd, b[ev.day].first, b[ev.day].second + 1, -1);
- bal++;
- }
- else {
- pair<int, int> r = get(1, 0, dd, 0, dd);
- int cc = bal + r.first;
- if (cc > ans) {
- ans = cc;
- ans1 = ev.from;
- ans2 = r.second;
- }
- bal--;
- upd(1, 0, dd, b[ev.day].first, b[ev.day].second + 1, 1);
- }
- }
- assert(ans1 >= 0 && ans1 < was.size());
- assert(ans2 >= 0 && ans2 < was.size());
- cout << was[ans1] << " " << was[ans2];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement