Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2019
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.66 KB | None | 0 0
  1. #define _USE_MATH_DEFINES
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <vector>
  5. #include <set>
  6. #include <queue>
  7. #include <map>
  8. #include <string>
  9. #include <cmath>
  10. #include <functional>
  11. #include <algorithm>
  12. #include <utility>
  13. #include <stack>
  14. #include <unordered_map>
  15. #include <unordered_set>
  16. #include <iterator>
  17. #include <fstream>
  18. #include <iomanip>
  19. #include <time.h>
  20. #include <complex>
  21. //#pragma comment(linker, "/STACK:16777216")
  22.  
  23. using namespace std;
  24.  
  25. typedef long double C;
  26. typedef complex<C> P;
  27.  
  28. #define X real()
  29. #define Y imag()
  30. #define Size(X) (int)X.size()
  31. //#define int long long
  32. #define ui unsigned int
  33. #define mp make_pair
  34. #define timer fghge
  35. #define y1 yjyjyju
  36. #define all(X) (X).begin(), (X).end()
  37. #define endl '\n'
  38.  
  39. struct node {
  40. int lb, rb;
  41. int lazy = 0, a = 0;
  42. node *l = 0, *r = 0;
  43. pair<int, int> maxim;
  44.  
  45. node(int _lb, int _rb) {
  46. lb = _lb; rb = _rb;
  47. if (lb + 1 < rb) {
  48. int t = (lb + rb) / 2;
  49. l = new node(lb, t);
  50. r = new node(t, rb);
  51. }
  52. maxim = { lb, 0 };
  53. }
  54.  
  55. void add(int x, int _l, int _r) {
  56. if (_r < lb || _l >= rb)
  57. return;
  58.  
  59. if (_l <= lb && rb - 1 <=_r)
  60. lazy += x;
  61. else {
  62. l->add(x, _l, _r); r->add(x, _l, _r);
  63. auto a = l->maxim, b = r->maxim;
  64. a.second += l->lazy;
  65. b.second += r->lazy;
  66. if (a.second < b.second)
  67. swap(a, b);
  68. maxim = a;
  69. }
  70. }
  71.  
  72. void push() {
  73. maxim.second += lazy;
  74. if (lb + 1 == rb) {
  75. lazy = 0;
  76. return;
  77. }
  78. l->lazy += lazy; r->lazy += lazy;
  79. lazy = 0;
  80. }
  81.  
  82. pair<int, int> max(int _l, int _r) {
  83. push();
  84.  
  85. if (_r < lb || _l >= rb)
  86. return{ -1, -1 };
  87.  
  88. if (_l <= lb && _r >= rb - 1)
  89. return maxim;
  90. else {
  91. auto a = l->max(_l, _r), b = r->max(_l, _r);
  92. if (a.second < b.second)
  93. swap(a, b);
  94. return a;
  95. }
  96. }
  97. };
  98.  
  99. struct event {
  100. int x, l, r, d;
  101. };
  102.  
  103. bool cmp(const event &a, const event &b) {
  104. if (a.x != b.x)
  105. return a.x < b.x;
  106. else
  107. return a.d > b.d;
  108. }
  109.  
  110. signed main()
  111. {
  112. ios_base::sync_with_stdio(0);
  113. cin.tie(0), cout.tie(0);
  114. //freopen("input.txt", "r", stdin);
  115. //freopen("output.txt", "w", stdout);
  116. int HMAX = 2 * 1e6 + 10, b = 1e6 + 1;
  117. node *t = new node(0, HMAX);
  118.  
  119. int n; cin >> n;
  120. vector<event> a;
  121. for (int i = 0; i < n; i++) {
  122. int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
  123. y1 += b; y2 += b;
  124. a.push_back({ x1, y1, y2, 1 });
  125. a.push_back({ x2, y1, y2, -1 });
  126. }
  127. sort(all(a), cmp);
  128.  
  129. int ans = 0, x, y;
  130. for (int i = 0; i < 2 * n; i++) {
  131. t->add(a[i].d, a[i].l, a[i].r);
  132. auto res = t->max(0, HMAX);
  133. if (res.second > ans) {
  134. ans = res.second;
  135. x = a[i].x;
  136. y = res.first;
  137. }
  138. }
  139. cout << ans << endl << x << " " << y - b;
  140. return 0;
  141. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement