Advertisement
Guest User

Untitled

a guest
Mar 24th, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.94 KB | None | 0 0
  1. #define _FORTIFY_SOURCE 0
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC optimize("no-stack-protector")
  4. #pragma GCC optimize("unroll-loops")
  5. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  6. #include <iostream>
  7. #include <stdio.h>
  8. #include <vector>
  9. #include <set>
  10. #include <unordered_set>
  11. #include <map>
  12. #include <unordered_map>
  13. #include <deque>
  14. #include <algorithm>
  15. #include <math.h>
  16. #include <random>
  17. #define ff first
  18. #define ss second
  19. #define pb push_back
  20. #define mp make_pair
  21. #define int long long
  22. #define double long double
  23. #define Matrix vector<vector<int> >
  24. #define kektor vector
  25. #define pii pair<int, int>
  26. #define pp pair
  27. #define all(x) x.begin(), x.end()
  28.  
  29. using namespace std;
  30.  
  31. typedef long long ll;
  32.  
  33. int RandInt(int min, int max) {
  34. if (max < min) {
  35. swap(min, max);
  36. }
  37. random_device rd;
  38. mt19937 mt(rd());
  39. uniform_int_distribution<int> dist(min, max);
  40. return dist(mt);
  41. }
  42.  
  43. const int maxn = 3e5, mod = 1e9 + 7, inf = 1e18; const double pi = 3.14159265359, eps = 1e-9;
  44.  
  45. struct State {
  46. int x, y, ty, y1;
  47. State(int _x, int _y, int _ty, int _y1) : x(_x), y(_y), ty(_ty), y1(_y1) {}
  48. State() : x(0), y(0), ty(0), y1(0) {}
  49. };
  50.  
  51. struct Node {
  52. int x, id, push;
  53. Node(int _x, int _id, int _push) : x(_x), id(_id), push(_push) {}
  54. Node() : x(0), id(0), push(0) {}
  55. };
  56.  
  57. Node operator+(Node p1, Node p2) {
  58. if (p1.x > p2.x) {
  59. return p1;
  60. }
  61. return p2;
  62. }
  63.  
  64. int n, len = 1;
  65. vector<Node> tree;
  66. vector<State> scan;
  67.  
  68. bool cmp(State p1, State p2) {
  69. return (p1.x < p2.x) || (p1.x == p2.x && p1.ty < p2.ty);
  70. }
  71.  
  72. void build() {
  73. while (len < 3e6) {
  74. len *= 2;
  75. }
  76. tree.resize(len + len - 1);
  77. for (int i = len - 1; i < len + 3e6 - 1; ++i) {
  78. tree[i].id = i - len + 1;
  79. }
  80. for (int i = len - 2; i >= 0; --i) {
  81. tree[i] = tree[i * 2 + 1];
  82. }
  83. }
  84.  
  85. int push_ver(int root, int l, int r) {
  86. int push = tree[root].push;
  87. tree[root].x += push;
  88. tree[root].push = 0;
  89. if (l != r) {
  90. tree[root * 2 + 1].push += push;
  91. tree[root * 2 + 2].push += push;
  92. }
  93. }
  94.  
  95. pii get(int l, int r, int l1, int r1, int root) {
  96. push_ver(root, l, r);
  97. if (l >= l1 && r <= r1) {
  98. return mp(tree[root].x, tree[root].id);
  99. } else if (max(l, l1) > min(r, r1)) {
  100. return mp(-inf, -inf);
  101. } else {
  102. int tm = (l + r) / 2;
  103. return max(get(l, tm, l1, r1, root * 2 + 1), get(tm + 1, r, l1, r1, root * 2 + 2));
  104. }
  105. }
  106.  
  107. void upd(int l, int r, int l1, int r1, int root, int val) {
  108. push_ver(root, l, r);
  109. if (l >= l1 && r <= r1) {
  110. tree[root].push += val;
  111. push_ver(root, l, r);
  112. } else if (max(l, l1) > min(r, r1)) {
  113. return;
  114. } else {
  115. int tm = (l + r) / 2;
  116. upd(l, tm, l1, r1, root * 2 + 1, val);
  117. upd(tm + 1, r, l1, r1, root * 2 + 2, val);
  118. tree[root] = tree[root * 2 + 1] + tree[root * 2 + 2];
  119. }
  120. }
  121.  
  122. void solve() {
  123. cin >> n;
  124. for (int i = 0; i < n; ++i) {
  125. int x, y, x1, y1;
  126. cin >> x >> y >> x1 >> y1;
  127. x += 1e6;
  128. y += 1e6;
  129. x1 += 1e6;
  130. y1 += 1e6;
  131. scan.pb(State(x, y, -1, y1));
  132. scan.pb(State(x1, y1, 1, y));
  133. }
  134. sort(all(scan), cmp);
  135. build();
  136. int ans = -inf, a = -inf, b = -inf;
  137. for (int i = 0; i < scan.size(); ++i) {
  138. int L = min(scan[i].y, scan[i].y1);
  139. int R = max(scan[i].y, scan[i].y1);
  140. upd(0, len - 1, L, R, 0, -scan[i].ty);
  141. pii val = get(0, len - 1, L, R, 0);
  142. if (val.ff > ans) {
  143. ans = val.ff;
  144. a = scan[i].x;
  145. b = val.ss;
  146. }
  147. }
  148. cout << ans << '\n' << a - (int)1e6 << " " << b - (int)1e6;
  149. }
  150.  
  151. signed main() {
  152. cout.precision(10);
  153. cout << fixed;
  154. ios_base::sync_with_stdio(false);
  155. cin.tie(0);
  156. cout.tie(0);
  157. #ifdef offline_judge
  158. freopen("TASK.in", "r", stdin);
  159. freopen("TASK.out", "w", stdout);
  160. #endif
  161. solve();
  162. return 0;
  163. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement