lalalalalalalaalalla

Untitled

Dec 2nd, 2019
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <iomanip>
  5. #include <queue>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <unordered_map>
  9. #include <tuple>
  10. #include <iomanip>
  11. #include <stdio.h>
  12. #include <map>
  13. #include <bitset>
  14. #include <set>
  15. #include <stack>
  16. #include <queue>
  17. #include <unordered_set>
  18. #include <cassert>
  19. #include <stdlib.h>
  20. #include <time.h>
  21. #include <random>
  22.  
  23.  
  24. //#pragma GCC optimize("Ofast,no-stack-protector")
  25. //#pragma GCC target("sse,sse2,sse3,sse3,sse4")
  26. //#pragma GCC optimize("unroll-loops")
  27. //#pragma GCC optimize("fast-math")
  28. //#pragma GCC target("avx2")
  29. //#pragma GCC optimize("section-anchors")
  30. //#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
  31. //#pragma GCC optimize("vpt")
  32. //#pragma GCC optimize("rename-registers")
  33. //#pragma GCC optimize("move-loop-invariants")
  34. //#pragma GCC optimize("unswitch-loops")
  35. //#pragma GCC optimize("function-sections")
  36. //#pragma GCC optimize("data-sections")
  37.  
  38. #define int long long
  39. #define ll long long
  40. #define ull unsigned long long
  41. #define all(a) (a).begin(), (a).end()
  42. #define pii pair<int, int>
  43. #define pb push_back
  44. #define ld long double
  45.  
  46.  
  47. using namespace std;
  48.  
  49. const int INF = 1e17;
  50. //const int mod = 2600000069;
  51. //const int p = 179;
  52.  
  53. struct point {
  54. int x, y;
  55. point() {}
  56. point(int x_, int y_) {
  57. x = x_;
  58. y = y_;
  59. }
  60. };
  61.  
  62. struct event {
  63. int type;
  64. point a;
  65. event() {}
  66. event(int type_, point a_) {
  67. type = type_;
  68. a = a_;
  69. }
  70. };
  71.  
  72. int n;
  73. vector<pair<point, point>> vert, hor;
  74. vector<int> y;
  75. int y_cnt = 0;
  76. vector<event> x_events, y_events;
  77. map<int, int> y_ind;
  78.  
  79. int ans = 0, y_events_ind = 0, y_events_size;
  80.  
  81. bool comp_x(event a, event b) {
  82. if (a.a.x == b.a.x) return a.type < b.type;
  83. return a.a.x < b.a.x;
  84. }
  85.  
  86. bool comp_y(event a, event b) {
  87. if (a.a.x == b.a.x) {
  88. if (a.a.y == b.a.y) {
  89. return a.type < b.type;
  90. }
  91. return a.a.y < b.a.y;
  92. }
  93. return a.a.x < b.a.x;
  94. }
  95.  
  96. struct node {
  97. int min = 0, cnt = 1;
  98. node() {}
  99. node (int min_, int cnt_) {
  100. min = min_;
  101. cnt = cnt_;
  102. }
  103. };
  104.  
  105. vector<node> t;
  106. vector<int> mod;
  107.  
  108. void in() {
  109. cin >> n;
  110. point a, b;
  111. for (int i = 0; i < n; i++) {
  112. cin >> a.x >> a.y >> b.x >> b.y;
  113. if (a.x == b.x) {
  114. if (a.y > b.y) swap(a, b);
  115. vert.pb({a, b});
  116. y.pb(a.y);
  117. y.pb(b.y);
  118. x_events.pb(event(2, point(a.x, 0)));
  119. y_events.pb(event(0, a));
  120. y_events.pb(event(1, b));
  121. } else {
  122. if (a.x > b.x) swap(a, b);
  123. hor.pb({a, b});
  124. y.pb(a.y);
  125. x_events.pb(event(0, a));
  126. x_events.pb(event(1, b));
  127. }
  128. }
  129. sort(all(x_events), comp_x);
  130. sort(all(y_events), comp_y);
  131. sort(all(y));
  132. y.resize(unique(all(y)) - y.begin());
  133. y_cnt = y.size();
  134. t.resize(8 * y_cnt);
  135. mod.resize(8 * y_cnt);
  136. for (int i = 0; i < y_cnt; i++) {
  137. y_ind[y[i]] = i;
  138. }
  139. y_events_size = y_events.size();
  140. }
  141.  
  142.  
  143. node merge(node a, node b) {
  144. node c;
  145. if (a.min == b.min) {
  146. c = a;
  147. c.cnt += b.cnt;
  148. } else if (a.min < b.min) c = a;
  149. else c = b;
  150. return c;
  151. }
  152.  
  153.  
  154. void push(int v) {
  155. mod[2 * v + 1] += mod[v];
  156. mod[2 * v + 2] += mod[v];
  157. t[v].min += mod[v];
  158. mod[v] = 0;
  159. }
  160.  
  161. void build(int v, int l, int r) {
  162. if (r - l == 1) {
  163. t[v].cnt = 1;
  164. t[v].min = 0;
  165. return;
  166. }
  167. int m = (l + r) / 2;
  168. build(2 * v + 1, l, m);
  169. build(2 * v + 2, m, r);
  170. t[v] = merge(t[2 * v + 1], t[2 * v + 2]);
  171. }
  172.  
  173. void update(int v, int l, int r, int askl, int askr, int val) {
  174. if (l >= askr || r <= askl) return;
  175. if (l >= askl && r <= askr) {
  176. mod[v] += val;
  177. push(v);
  178. return;
  179. }
  180. push(v);
  181. int m = (l + r) / 2;
  182. update(2 * v + 1, l, m, askl, askr, val);
  183. update(2 * v + 2, m, r, askl, askr, val);
  184. t[v] = merge(t[2 * v + 1], t[2 * v + 2]);
  185. }
  186.  
  187. node sum(int v, int l, int r, int askl, int askr) {
  188. if (l >= askr || r <= askl) return node(INF, 0);
  189. push(v);
  190. if (l >= askl && r <= askr) return t[v];
  191. int m = (l + r) / 2;
  192. return merge(sum(2 * v + 1, l, m, askl, askr), sum(2 * v + 2, m, r, askl, askr));
  193. }
  194.  
  195. node q;
  196.  
  197. void scanline_y(int x) {
  198. if (y_events_ind == y_events_size) return;
  199. int open = 0;
  200. int lst = y_events[y_events_ind].a.y;
  201. for (; y_events_ind < y_events_size && y_events[y_events_ind].a.x == x;) {
  202. while (y_events_ind < y_events_size && y_events[y_events_ind].a.x == x && y_events[y_events_ind].type == 0) {open++; y_events_ind++;}
  203. while (y_events_ind < y_events_size && y_events[y_events_ind].a.x == x && y_events[y_events_ind].type == 1) {open--; y_events_ind++;}
  204. if (open == 0) {
  205. q = sum(0, 0, y_cnt, y_ind[lst], y_ind[y_events[y_events_ind - 1].a.y] + 1);
  206. if (q.min == 0) {
  207. ans += y_events[y_events_ind - 1].a.y - lst + 1 - (y_ind[y_events[y_events_ind - 1].a.y] - y_ind[lst] + 1);
  208. if (q.min == 0) ans += q.cnt;
  209. }
  210. if (y_events_ind < y_events_size) lst = y_events[y_events_ind].a.y;
  211. }
  212. }
  213. }
  214.  
  215.  
  216. void scanline_x() {
  217. build(0, 0, y_cnt);
  218. int sz = x_events.size(), x, lst = x_events[0].a.x;
  219. for (int i = 0; i < sz;) {
  220. x = x_events[i].a.x;
  221. if (x_events[i].type == 2) {
  222. scanline_y(x);
  223. i++;
  224. continue;
  225. }
  226. q = sum(0, 0, y_cnt, 0, y_cnt);
  227. ans += y_cnt * (x - lst);
  228. if (t[0].min == 0) ans -= t[0].cnt * (x - lst);
  229. while (i < sz && x_events[i].a.x == x && x_events[i].type == 0) {
  230. update(0, 0, y_cnt, y_ind[x_events[i].a.y], y_ind[x_events[i].a.y] + 1, 1);
  231. i++;
  232. }
  233. q = sum(0, 0, y_cnt, 0, y_cnt);
  234. ans += y_cnt;
  235. if (t[0].min == 0) ans -= t[0].cnt;
  236. scanline_y(x);
  237. while (i < sz && x_events[i].a.x == x && x_events[i].type == 1) {
  238. update(0, 0, y_cnt, y_ind[x_events[i].a.y], y_ind[x_events[i].a.y] + 1, -1);
  239. i++;
  240. }
  241. while (i < sz && x_events[i].a.x == x) i++;
  242. lst = x + 1;
  243. }
  244. }
  245.  
  246. signed main() {
  247. ios_base::sync_with_stdio(0);
  248. cin.tie(0);
  249. cout.tie(0);
  250. in();
  251. // for (auto k : y) {
  252. // cout << k << " ";
  253. // }
  254. // cout << "\n";
  255. scanline_x();
  256. cout << ans;
  257. }
  258. /*
  259. 2
  260. 0 1 2 1
  261. 0 3 2 3
  262.  
  263. 2
  264. 0 0 0 1
  265. 0 1 0 2
  266.  
  267. 3
  268. 0 1 2 1
  269. 0 3 2 3
  270. 1 4 1 2
  271.  
  272.  
  273. */
Advertisement
Add Comment
Please, Sign In to add comment