Advertisement
Guest User

Untitled

a guest
Nov 9th, 2019
609
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.32 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct SegTree {
  6.   struct Node {
  7.     int cnt = 0;
  8.     int dp[2] = {0, 0};
  9.     bool l_flip = false;
  10.     int l_add = 0;
  11.     int min = 0;
  12.   };
  13.   int n;
  14.   vector<int> all;
  15.   vector<Node> data;
  16.  
  17.   SegTree(vector<int> all) :
  18.     n(all.size()), all(all), data(4 * n) {
  19.       init(1, 0, n - 2);
  20.     }
  21.  
  22.   void init(int node, int b, int e) {
  23.     if (b == e) {
  24.       data[node].dp[0] = all[b + 1] - all[b];  
  25.       data[node].cnt = all[b + 1] - all[b];
  26.     } else {
  27.       int m = (b + e) / 2;
  28.       init(node * 2, b, m);
  29.       init(node * 2 + 1, m + 1, e);
  30.       pull(node);
  31.     }
  32.   }
  33.  
  34.   int norm(int x) {
  35.     return lower_bound(all.begin(), all.end(), x) - all.begin();
  36.   }
  37.  
  38.   void push(int node, int b, int e) {
  39.     if (data[node].l_flip) {
  40.       swap(data[node].dp[0], data[node].dp[1]);
  41.       if (b < e) {
  42.         data[node * 2].l_flip ^= 1;
  43.         data[node * 2 + 1].l_flip ^= 1;
  44.       }
  45.       data[node].l_flip = 0;
  46.     }
  47.     if (data[node].l_add) {
  48.       data[node].min += data[node].l_add;
  49.       if (b < e) {
  50.         data[node * 2].l_add += data[node].l_add;
  51.         data[node * 2 + 1].l_add += data[node].l_add;
  52.       }
  53.       data[node].l_add = 0;
  54.     }
  55.   }
  56.  
  57.   void pull(int node) {
  58.     data[node].dp[0] = data[node * 2].dp[0] + data[node * 2 + 1].dp[0];
  59.     data[node].dp[1] = data[node * 2].dp[1] + data[node * 2 + 1].dp[1];
  60.     data[node].min = min(data[node * 2].min, data[node * 2 + 1].min);
  61.     data[node].cnt = 0;
  62.     if (data[node].min == data[node * 2].min)
  63.       data[node].cnt += data[node * 2].cnt;
  64.     if (data[node].min == data[node * 2 + 1].min)
  65.       data[node].cnt += data[node * 2 + 1].cnt;
  66.   }
  67.  
  68.   void update(int node, int b, int e, int l, int r, int val) {
  69.     push(node, b, e);
  70.     l = max(l, b); r = min(e, r);
  71.     if (l > r) return;
  72.     if (b == l && e == r) {
  73.       data[node].l_flip ^= 1;
  74.       data[node].l_add += val;
  75.       push(node, b, e);
  76.       return;
  77.     }
  78.     int m = (b + e) / 2;
  79.     update(node * 2, b, m, l, r, val);
  80.     update(node * 2 + 1, m + 1, e, l, r, val);
  81.     pull(node);
  82.   }
  83.  
  84.   void Update(int l, int r, int val) {
  85.     l = norm(l); r = norm(r) - 1;
  86.     if (l > r) return;
  87.     update(1, 0, n - 2, l, r, val);
  88.   }
  89.  
  90.   int Get() {
  91.     int ret = all.back() - all.front();
  92.     if (data[1].min == 0) {
  93.       ret -= data[1].cnt;  
  94.     }
  95.     ret -= data[1].dp[1];
  96.     return ret;
  97.   }
  98. };
  99.  
  100. int main() {
  101.   int n; cin >> n;
  102.   vector<tuple<int, int, int, int>> events;
  103.   events.reserve(2 * n);
  104.   vector<int> all;
  105.   all.reserve(2 * n);
  106.  
  107.   for (int i = 0; i < n; ++i) {
  108.     int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
  109.     if (x1 > x2) swap(x1, x2);
  110.     if (y1 > y2) swap(y1, y2);
  111.     all.push_back(y1); all.push_back(y2);
  112.     events.emplace_back(x1, y1, y2, +1);
  113.     events.emplace_back(x2, y1, y2, -1);
  114.   }
  115.  
  116.   sort(events.begin(), events.end());
  117.  
  118.   sort(all.begin(), all.end());
  119.   all.erase(unique(all.begin(), all.end()), all.end());
  120.   SegTree st(all);
  121.  
  122.   int last = -1;
  123.   long long total = 0;
  124.  
  125.   for (int i = 0; i < 2 * n; ++i) {
  126.     int x, y1, y2, val;
  127.     tie(x, y1, y2, val) = events[i];
  128.     total += 1LL * st.Get() * (x - last);
  129.     // cerr << "x=" << x << "total=" << total << endl;
  130.     st.Update(y1, y2, val);
  131.     last = x;
  132.   }
  133.  
  134.   cout << total << endl;
  135.  
  136.   return 0;
  137. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement