# CF gym101982F: Rectangles

Jan 26th, 2021
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
2.
4. using namespace abb;
5. using namespace output;
6. using namespace rit;
7. using namespace wit;
8.
9. inline void init() {
10.
11. }
12.
13. struct node {
14.     int v, d;
15.     node *l, *r;
16.     void pull() {
17.         v = (l ? l->v : 0) + (r ? r->v : 0);
18.     }
19.     void push(int L, int R) {
20.         if (!d) return;
21.         d = 0, v = (R - L) - v;
22.         if (R - L == 1) return;
23.         if (!l) l = new node;
24.         if (!r) r = new node;
25.         l->d = true, r->d = true;
26.     }
27.     node(): v(0), d(0) {
28.         l = r = nullptr;
29.     }
30. }*root = nullptr;
31.
32. #define m ((l + r) >> 1)
33. constexpr int L = 0, R = 1e9 + 5;
34.
35. void reverse(int ql, int qr, node*& cur = root, int l = L, int r = R) {
36.     if (!cur) cur = new node;
37.     else cur->push(l, r);
38.     if (qr <= l || r <= ql) return;
39.     if (ql <= l && r <= qr) {
40.         cur->d = true, cur->push(l, r);
41. //      debug(l, r, cur->v);
42.         return;
43.     }
44.     reverse(ql, qr, cur->l, l, m);
45.     reverse(ql, qr, cur->r, m, r);
46.     cur->pull();
47. }
48. inline int query() {return root ? (root->push(L, R), root->v) : 0;}
49. #undef m
50.
51. inline void solve() {
52.     int n; cin >> n;
53.     using line = tuple<int, int, int>;
54.     V<line> v(n << 1);
55.     for (int i = 0; i != n; i++) {
56.         static int x1, y1, x2, y2;
57.         cin >> x1 >> y1 >> x2 >> y2;
58.         if (y1 > y2) swap(y1, y2);
59.         v[i << 1    ] = {x1, y1, y2};
60.         v[i << 1 | 1] = {x2, y1, y2};
61.     }
62.     sort(v.begin(), v.end());
63.     ll sum = 0, cur = 0;
64.     for (const auto& i : v) {
65.         static int x, l, r;
66.         tie(x, l, r) = i;
67.         sum += 1LL * (x - cur) * query();
68.         reverse(l, r), cur = x;
69. //      debug(x, l, r, query());
70.     }
71.     cout << sum << endl;
72. }
73.
74. main() {
75.     ios::sync_with_stdio(false);
76.     init();
77.     int t = 1;