Advertisement
konchin_shih

CF gym101982F: Rectangles

Jan 26th, 2021
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include"./template/headers.hpp"
  2.  
  3. //#define MULTI_TASKCASE
  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;
  78. #ifdef MULTI_TASKCASE
  79.     cin >> t; cin.ignore();
  80. #endif
  81.     while (t--) solve();
  82.     return 0;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement