Advertisement
kuroni

ICPC Vietnam National 2019 - K

Nov 12th, 2019
468
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.86 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. using namespace std;
  5.  
  6. const int N = 2E5 + 5;
  7.  
  8. int n;
  9. long long x, y, u, v, ans = 0;
  10. vector<long long> ve;
  11.  
  12. struct event {
  13.     long long u, l, r, val;
  14.  
  15.     event(long long _u, long long _l, long long _r, long long _val) : u(_u), l(_l), r(_r), val(_val) {}
  16. };
  17. vector<event> sw;
  18.  
  19. struct segment_tree {
  20. #define m (l + r) / 2
  21. #define lc i * 2
  22. #define rc i * 2 + 1
  23.  
  24.     long long eve[4 * N], odd[4 * N];
  25.     pair<int, long long> mi[4 * N];
  26.     int lz[4 * N];
  27.  
  28.     void apply(int i, int v) {
  29.         lz[i] += v;
  30.         mi[i].fi += v;
  31.         if (abs(v) % 2 == 1) {
  32.             swap(eve[i], odd[i]);
  33.         }
  34.     }
  35.  
  36.     void down(int i) {
  37.         apply(lc, lz[i]);
  38.         apply(rc, lz[i]);
  39.         lz[i] = 0;
  40.     }
  41.  
  42.     void build(int l, int r, int i) {
  43.         if (l == r) {
  44.             eve[i] = mi[i].se = ve[l + 1] - ve[l];
  45.             odd[i] = 0;
  46.         } else {
  47.             build(l, m, lc);
  48.             build(m + 1, r, rc);
  49.             eve[i] = eve[lc] + eve[rc];
  50.             odd[i] = 0;
  51.             mi[i].se = eve[i];
  52.         }
  53.     }
  54.  
  55.     void update(int l, int r, int i, int L, int R, int v) {
  56.         if (l > R || r < L || L > R) {
  57.             return;
  58.         } else if (L <= l && r <= R) {
  59.             apply(i, v);
  60.         } else {
  61.             down(i);
  62.             update(l, m, lc, L, R, v);
  63.             update(m + 1, r, rc, L, R, v);
  64.             eve[i] = eve[lc] + eve[rc];
  65.             odd[i] = odd[lc] + odd[rc];
  66.             mi[i] = min(mi[lc], mi[rc]);
  67.             if (mi[lc].fi == mi[rc].fi) {
  68.                 mi[i].se = mi[lc].se + mi[rc].se;
  69.             }
  70.         }
  71.     }
  72.  
  73. #undef m
  74. #undef lc
  75. #undef rc
  76. } seg;
  77.  
  78. int main() {
  79.     ios_base::sync_with_stdio(false);
  80.     cin.tie(nullptr);
  81.     cin >> n;
  82.     for (int i = 1; i <= n; i++) {
  83.         cin >> x >> y >> u >> v;
  84.         if (x > u) {
  85.             swap(x, u);
  86.         }
  87.         if (y > v) {
  88.             swap(y, v);
  89.         }
  90.         if (x == u || y == v) {
  91.             continue;
  92.         }
  93.         sw.push_back(event(x, y, v, 1)); sw.push_back(event(u, y, v, -1));
  94.         ve.push_back(y); ve.push_back(v);
  95.     }
  96.     if (sw.empty()) {
  97.         return cout << 0, 0;
  98.     }
  99.     sort(ve.begin(), ve.end());
  100.     sort(sw.begin(), sw.end(), [](const event &u, const event &v) {
  101.         return u.u < v.u;
  102.     });
  103.     ve.erase(unique(ve.begin(), ve.end()), ve.end());
  104.     int n = ve.size() - 1;
  105.     seg.build(0, n - 1, 1);
  106.     for (int i = 0; i < sw.size() - 1; i++) {
  107.         int l = distance(ve.begin(), lower_bound(ve.begin(), ve.end(), sw[i].l));
  108.         int r = distance(ve.begin(), lower_bound(ve.begin(), ve.end(), sw[i].r)) - 1;
  109.         seg.update(0, n - 1, 1, l, r, sw[i].val);
  110.         ans += 1LL * (sw[i + 1].u - sw[i].u) * (seg.eve[1] - (seg.mi[1].fi == 0) * seg.mi[1].se);
  111.     }
  112.     cout << ans;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement