Advertisement
Guest User

Untitled

a guest
Jun 9th, 2024
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <numeric>
  4. #include <string>
  5. #include <queue>
  6. #include <deque>
  7. #include <iomanip>
  8. #include <map>
  9. #include <set>
  10. #include <random>
  11. #include <cmath>
  12. #include <unordered_map>
  13. #include <unordered_set>
  14. #include <stack>
  15. #include <algorithm>
  16. #define fast() ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  17. #define all(array) array.begin(), array.end()
  18. #define pb push_back
  19. #define eb emplace_back
  20. #pragma GCC target ("avx2")
  21. #pragma GCC optimize ("Ofast")
  22. using ll = long long;
  23. //using ll = int;
  24. using ull = unsigned long long;
  25. using ld = long double;
  26. using namespace std;
  27. const ll INF = 1e18;
  28. const int inf = 1e9;
  29. const int mod = 1e9 + 7;
  30. const int P = 72;
  31.  
  32.  
  33. template<typename Type>
  34. istream& operator>>(istream &in, vector<Type> &x) {
  35. for (auto &i : x) in >> i;
  36. return in;
  37. }
  38.  
  39.  
  40. template<typename Type>
  41. ostream& operator<<(ostream &out, vector<Type> &x) {
  42. for (auto i: x) out << i << " ";
  43. return out;
  44. }
  45.  
  46.  
  47. struct node {
  48. ll min;
  49. ll lazy;
  50. ll cnty;
  51. };
  52.  
  53.  
  54. const ll maxn = 2e5;
  55. vector<node> tree;
  56.  
  57.  
  58. vector<ll> x;
  59. ll mx;
  60.  
  61.  
  62. node make_data(ll tl, ll val) {
  63. node res{};
  64. res.min = val;
  65. res.cnty = x[tl + 1] - x[tl];
  66. return res;
  67. }
  68.  
  69.  
  70. node combine(node& l, node& r) {
  71. node res{};
  72. if (l.min < r.min) {
  73. return l;
  74. } else if (r.min < l.min) {
  75. return r;
  76. } else {
  77. res.min = l.min;
  78. res.cnty = l.cnty + r.cnty;
  79. return res;
  80. }
  81. }
  82.  
  83.  
  84. void push(ll tl, ll tr, ll v) {
  85. if (tree[v].lazy != 0) {
  86. tree[v].min += tree[v].lazy;
  87. if (tr - tl > 1) {
  88. tree[v * 2 + 1].lazy += tree[v].lazy;
  89. tree[v * 2 + 2].lazy += tree[v].lazy;
  90. }
  91. tree[v].lazy = 0;
  92. }
  93. }
  94.  
  95.  
  96. void build(ll tl, ll tr, ll v) {
  97. if (tr - tl == 1) {
  98. tree[v] = make_data(tl, 0);
  99. return;
  100. }
  101. ll tm = (tr + tl) / 2;
  102. build(tl, tm, v * 2 + 1);
  103. build(tm, tr, v * 2 + 2);
  104. tree[v] = combine(tree[v * 2 + 1], tree[v * 2 + 2]);
  105. }
  106.  
  107.  
  108. void update(ll l, ll r, ll val, ll tl, ll tr, ll v) {
  109. push(tl, tr, v);
  110. if (l >= tr || r <= tl) {
  111. return;
  112. }
  113. if (tl >= l && tr <= r) {
  114. tree[v].lazy += val;
  115. push(tl, tr, v);
  116. return;
  117. }
  118. ll tm = (tr + tl) / 2;
  119. update(l, r, val, tl, tm, v * 2 + 1);
  120. update(l, r, val, tm, tr, v * 2 + 2);
  121. tree[v] = combine(tree[v * 2 + 1], tree[v * 2 + 2]);
  122. }
  123.  
  124.  
  125. ll sum(ll l, ll r, ll tl, ll tr, ll v) {
  126. push(tl, tr, v);
  127. if (l >= tr || r <= tl) {
  128. return 0;
  129. }
  130. if (tl >= l && tr <= r) {
  131. return tree[v].cnty;
  132. }
  133. ll tm = (tr + tl) / 2;
  134. ll s1 = sum(l, r, tl, tm, v * 2 + 1);
  135. ll s2 = sum(l, r, tm, tr, v * 2 + 2);
  136. //tree[v] = combine(tree[v * 2 + 1], tree[v * 2 + 2]);
  137. return s1 + s2;
  138. }
  139.  
  140.  
  141. ll min(ll l, ll r, ll tl, ll tr, ll v) {
  142. push(tl, tr, v);
  143. if (l >= tr || r <= tl) {
  144. return INF;
  145. }
  146. if (tl >= l && tr <= r) {
  147. return tree[v].min;
  148. }
  149. ll tm = (tr + tl) / 2;
  150. return min(min(l, r, tl, tm, v * 2 + 1), min(l, r, tm, tr, v * 2 + 2));
  151. }
  152.  
  153.  
  154. void solve() {
  155. ll n;
  156. cin >> n;
  157. if (n == 0) {
  158. cout << 0;
  159. return;
  160. }
  161. vector<ll> y;
  162. ll x1, x2, y1, y2;
  163. vector<pair<pair<ll, ll>, pair<ll, ll>>> Q;
  164. unordered_set<ll> sx, sy;
  165. for (ll i = 0; i < n; ++i) {
  166. cin >> x1 >> y1 >> x2 >> y2;
  167. //x1[i] += 1e9; y1[i] += 1e9; x2[i] += 1e9; y2[i] += 1e9;
  168. Q.pb({{x1, y1}, {x2, y2}});
  169. if (sx.find(x1) == sx.end()) {
  170. x.pb(x1);
  171. sx.insert(x1);
  172. }
  173. if (sx.find(x2) == sx.end()) {
  174. x.pb(x2);
  175. sx.insert(x2);
  176. }
  177. if (sy.find(y1) == sy.end()) {
  178. y.pb(y1);
  179. sy.insert(y1);
  180. }
  181. if (sy.find(y2) == sy.end()) {
  182. y.pb(y2);
  183. sy.insert(y2);
  184. }
  185. }
  186. unordered_map<ll, ll> mpx, mpy;
  187. sort(all(x));
  188. sort(all(y));
  189. mx = (ll)x.size();
  190. ll my = (ll)y.size();
  191. for (ll i = 0; i < mx; ++i) {
  192. mpx[x[i]] = i;
  193. }
  194. for (ll i = 0; i < my; ++i) {
  195. mpy[y[i]] = i;
  196. }
  197. vector<vector<pair<pair<ll, ll>, ll>>> q(my);
  198. for (auto p : Q) {
  199. x1 = p.first.first, y1 = p.first.second, x2 = p.second.first, y2 = p.second.second;
  200. q[mpy[y1]].pb({{mpx[x1], mpx[x2]}, 1});
  201. q[mpy[y2]].pb({{mpx[x1], mpx[x2]}, -1});
  202. }
  203. tree.resize(mx * 4);
  204. build(0, mx - 1, 0);
  205. ll ans = 0;
  206. for (ll i = 0; i < my - 1; ++i) {
  207. for (pair<pair<ll, ll>, ll> p : q[i]) {
  208. ll l = p.first.first, r = p.first.second, v = p.second;
  209. if (r < l) swap(l, r);
  210. update(l, r, v, 0, mx - 1, 0);
  211. }
  212. ans += (x[mx - 1] - x[0] - ((min(0, mx - 1, 0, mx - 1, 0) > 0) ? 0 : sum(0, mx - 1, 0, mx - 1, 0))) * ((i == my - 1) ? 0 : y[i + 1] - y[i]);
  213. }
  214. cout << ans;
  215. }
  216.  
  217.  
  218. int main() {
  219. #ifdef LOCAL
  220. freopen("input.txt", "r", stdin);
  221. freopen("output.txt", "w", stdout);
  222. clock_t timer = clock();
  223. #endif
  224. fast();
  225. ll tc = 1;
  226. ll cfmode = 0;
  227. if (cfmode) cin >> tc;
  228. while (tc--) {
  229. solve();
  230. if (tc) cout << "\n";
  231. }
  232. #ifdef LOCAL
  233. cout << fixed << setprecision(10);
  234. cout << "\n\nExecution time: " << (long double) (clock() - timer) / CLOCKS_PER_SEC;
  235. #endif
  236. return 0;
  237. }
  238.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement