Advertisement
Guest User

Untitled

a guest
Jan 16th, 2017
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.12 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <fstream>
  4. #include <cstdio>
  5. #include <cmath>
  6. #include <ctime>
  7. #include <cstring>
  8. #include <algorithm>
  9. #include <vector>
  10. #include <string>
  11. #include <map>
  12. #include <set>
  13. #include <queue>
  14. #include <deque>
  15. #include <bitset>
  16. #include <cassert>
  17. #include <tuple>
  18. #include <unordered_map>
  19. #include <unordered_set>
  20.  
  21. using namespace std;
  22.  
  23. const int maxc = (int)32;
  24. const int dd = (int)7e4 + 7;
  25. const int MOD = (int)1e9 + 9;
  26. const int INF = (int)1e9 + 7;
  27. const long long LINF = (1ll) * 1e18 + 7;
  28. const int P = (int)239017;
  29. #define ll long long
  30. #define TIME clock() * 1.0 / CLOCKS_PER_SEC
  31. #define err(x) cerr << __FUNCTION__ << " (" << __LINE__ << \
  32. "): [" << #x << "] = " << x;
  33. #define tm WHAT_THE_FUCK_DOES_THIS_VARIABLE_DOES
  34. void ujugajuga(bool tl228) {
  35. #ifdef starcall
  36. freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  37. #else
  38. //freopen("roads.in", "r", stdin); freopen("roads.out", "w", stdout);
  39. //freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  40. #endif
  41. //srand(time(0));
  42. srand(atoi("Dlya porazeniya"));
  43. if (tl228) {
  44. ios_base::sync_with_stdio(0);
  45. cin.tie();
  46. cout.tie();
  47. }
  48. }
  49.  
  50. struct event {
  51. int from, to, type, day;
  52. event() {}
  53. event(int _from, int _to, int _type, int _day) {
  54. from = _from, to = _to, type = _type, day = _day;
  55. }
  56. bool operator < (event b) {
  57. if (from != b.from)
  58. return from < b.from;
  59. if (type != b.type)
  60. return type < b.type;
  61. return day < b.day;
  62. }
  63. };
  64.  
  65. pair<int, int> t[4 * dd + 7];
  66. int add[4 * dd + 7];
  67.  
  68. void push(int v, int tl, int tr) {
  69. if (tr - tl > 1) {
  70. add[v * 2] += add[v];
  71. add[v * 2 + 1] += add[v];
  72. }
  73. t[v].first += add[v];
  74. add[v] = 0;
  75. }
  76.  
  77. void upd(int v, int tl, int tr, int l, int r, int val) {
  78. push(v, tl, tr);
  79. if (r <= tl || l >= tr) {
  80. return;
  81. }
  82. if (r >= tr && tl >= l) {
  83. add[v] += val;
  84. if (tr - 1 == tl)
  85. t[v].second = tl;
  86. push(v, tl, tr);
  87. return;
  88. }
  89. int tm = (tl + tr) / 2;
  90. upd(v * 2, tl, tm, l, r, val);
  91. upd(v * 2 + 1, tm, tr, l, r, val);
  92. t[v] = max(t[v * 2], t[v * 2 + 1]);
  93. }
  94.  
  95. pair<int, int> get(int v, int tl, int tr, int l, int r) {
  96. push(v, tl, tr);
  97. if (r <= tl || l >= tr) {
  98. return make_pair(-INF, -INF);
  99. }
  100. if (r >= tr && tl >= l) {
  101. return t[v];
  102. }
  103. int tm = (tl + tr) / 2;
  104. push(v, tl, tr);
  105. return max(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm, tr, l, r));
  106. }
  107.  
  108. int n;
  109. vector<pair<int, int> > a, b;
  110.  
  111. pair<int, int> rr[dd];
  112. map<long long, int> w;
  113. vector<int> was;
  114. int main() {
  115. ujugajuga(0);
  116. cin >> n;
  117. vector<event> g;
  118. for (int i = 0; i < n; i++) {
  119. int q, w, e, r;
  120. scanf("%d %d %d %d", &q, &w, &e, &r);
  121. a.push_back({ q, w }), b.push_back({ e, r });
  122. was.push_back(q);
  123. was.push_back(w);
  124. was.push_back(e);
  125. was.push_back(r);
  126. //upd(1, 0, dd, e, r + 1, 1);
  127. }
  128. sort(was.begin(), was.end());
  129. was.resize(unique(was.begin(), was.end()) - was.begin());
  130. for (int i = 0; i < was.size(); i++) {
  131. w[was[i]] = i;
  132. }
  133. for (int i = 0; i < n; i++) {
  134. a[i].first = lower_bound(was.begin(), was.end(), a[i].first) - was.begin();
  135. a[i].second = lower_bound(was.begin(), was.end(), a[i].second) - was.begin();
  136. b[i].first = lower_bound(was.begin(), was.end(), b[i].first) - was.begin();
  137. b[i].second = lower_bound(was.begin(), was.end(), b[i].second) - was.begin();
  138. upd(1, 0, dd, b[i].first, b[i].second + 1, 1);
  139. }
  140. for (int i = 0; i < n; i++) {
  141. g.push_back({ a[i].first, a[i].second, -1, i });
  142. g.push_back({ a[i].second, a[i].first, 1, i });
  143. }
  144. sort(g.begin(), g.end());
  145. int bal = 0;
  146. int ans1 = 0, ans2 = 0;
  147. int ans = 0;
  148. for (auto ev : g) {
  149. if (ev.type == -1) {
  150. upd(1, 0, dd, b[ev.day].first, b[ev.day].second + 1, -1);
  151. bal++;
  152.  
  153. }
  154. else {
  155. pair<int, int> r = get(1, 0, dd, 0, dd);
  156. int cc = bal + r.first;
  157. if (cc > ans) {
  158. ans = cc;
  159. ans1 = ev.from;
  160. ans2 = r.second;
  161. }
  162. bal--;
  163. upd(1, 0, dd, b[ev.day].first, b[ev.day].second + 1, 1);
  164. }
  165. }
  166. assert(ans1 >= 0 && ans1 < was.size());
  167. assert(ans2 >= 0 && ans2 < was.size());
  168. cout << was[ans1] << " " << was[ans2];
  169. return 0;
  170. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement