Advertisement
MathQ_

Untitled

May 20th, 2022
790
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
  2. #pragma GCC optimize 03
  3. #pragma GCC optimize("unroll-loops")
  4.  
  5. #include <bits/stdc++.h>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8.  
  9. using namespace std;
  10. using namespace __gnu_pbds;
  11.  
  12. typedef unsigned long long ull;
  13. typedef long long ll;
  14. typedef long double ld;
  15. typedef std::pair<int, int> pii;
  16. typedef std::pair<char, char> pcc;
  17. typedef std::pair<ll, ll> pll;
  18. typedef tree<int,
  19.              null_type,
  20.              less<int>,
  21.              rb_tree_tag,
  22.              tree_order_statistics_node_update> ordered_set;
  23.  
  24. #define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  25. #define file_in freopen("input.txt", "r", stdin);
  26. #define file_in_out freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  27. #define all(x) (x).begin(), (x).end()
  28. #define sz(x) (int)x.size()
  29. #define fi first
  30. #define se second
  31.  
  32. template<typename T>
  33. istream& operator>>(istream &in, vector<T> &v) {
  34.     for (auto &it : v) {
  35.         in >> it;
  36.     }
  37.     return in;
  38. }
  39.  
  40. template<typename T>
  41. ostream& operator<<(ostream &out, const vector<T> &v) {
  42.     for (auto &it : v) {
  43.         out << it << " ";
  44.     }
  45.     return out;
  46. }
  47.  
  48. template<typename T1, typename T2>
  49. istream& operator>>(istream &in, pair<T1, T2> &v) {
  50.     in >> v.fi >> v.se;
  51.     return in;
  52. }
  53.  
  54. template<typename T1, typename T2>
  55. ostream& operator<<(ostream &out, const pair<T1, T2> &v) {
  56.     out << v.fi << " " << v.se;
  57.     return out;
  58. }
  59. struct query {
  60.     int x, t, l, r;
  61.     query() {}
  62.     query(int x, int t, int l, int r, int i) : x(x), t(t), l(l), r(r) {}
  63. };
  64.  
  65. bool cmp(query &q1, query &q2) {
  66.     if (q1.x == q2.x) {
  67.         if (q1.t == q2.t) {
  68.             if (q1.l == q2.l) {
  69.                 return q1.r < q2.r;
  70.             }
  71.             return q1.l < q2.l;
  72.         }
  73.         return q1.t < q2.t;
  74.     }
  75.     return q1.x < q2.x;
  76. }
  77.  
  78. struct Node {
  79.     int ext = 2e9, sum = 0, add = 0;
  80.     Node() {}
  81.     Node(int x) { ext = 0; sum = x; }
  82. };
  83.  
  84. struct segtree {
  85.     vector<Node> t;
  86.     segtree(vector<int> &a) { t.resize(4 * sz(a)); build(0, 0, sz(a), a); }
  87.     void build(int id, int l, int r, vector<int> &a) {
  88.         if (l + 1 == r) { t[id] = Node(a[l]); return; }
  89.         build(id * 2 + 1, l, l + r >> 1, a);
  90.         build(id * 2 + 2, l + r >> 1, r, a);
  91.         t[id].ext = min(get(id * 2 + 1), get(id * 2 + 2));
  92.         if (t[id].ext == get(id * 2 + 1)) {
  93.             t[id].sum += t[id * 2 + 1].sum;
  94.         }
  95.         if (t[id].ext == get(id * 2 + 2)) {
  96.             t[id].sum += t[id * 2 + 2].sum;
  97.         }
  98.     }
  99.     void push(int id) {
  100.         t[id].ext += t[id].add;
  101.         t[id * 2 + 1].add += t[id].add;
  102.         t[id * 2 + 2].add += t[id].add;
  103.         t[id].add = 0;
  104.     }
  105.     int get(int id) {
  106.         return t[id].ext + t[id].add;
  107.     }
  108.     int get_sum() {
  109.         return (get(0) == 0 ? t[0].sum : 0);
  110.     }
  111.     void upd(int id, int l, int r, int lq, int rq, int x) {
  112.         if (l >= rq || lq >= r) return;
  113.         if (lq <= l && r <= rq) { t[id].add += x; return; }
  114.         push(id);
  115.         upd(id * 2 + 1, l, l + r >> 1, lq, rq, x);
  116.         upd(id * 2 + 2, l + r >> 1, r, lq, rq, x);
  117.         t[id].ext = min(get(id * 2 + 1), get(id * 2 + 2));
  118.         t[id].sum = 0;
  119.         if (t[id].ext == get(id * 2 + 1)) {
  120.             t[id].sum += t[id * 2 + 1].sum;
  121.         }
  122.         if (t[id].ext == get(id * 2 + 2)) {
  123.             t[id].sum += t[id * 2 + 2].sum;
  124.         }
  125.     }
  126. };
  127.  
  128. int main() {
  129.     fast
  130.     // file_in
  131.     // file_in_out
  132.  
  133.     int n;
  134.     cin >> n;
  135.     if (n == 0) {
  136.         cout << 0 << '\n';
  137.         return 0;
  138.     }
  139.     vector<query> qq(2 * n);
  140.     vector<int> px, py;
  141.     for (int i = 0; i < n; ++i) {
  142.         int x1, x2, l, r;
  143.         cin >> x1 >> l >> x2 >> r;
  144.         px.push_back(x1); px.push_back(x2);
  145.         py.push_back(l); py.push_back(r);
  146.         qq[2 * i + 0].x = x1; qq[2 * i + 0].t = 0; qq[2 * i + 0].l = l; qq[2 * i + 0].r = r;
  147.         qq[2 * i + 1].x = x2; qq[2 * i + 1].t = 1; qq[2 * i + 1].l = l; qq[2 * i + 1].r = r;
  148.     }
  149.     sort(all(px)); sort(all(py));
  150.     for (auto &q : qq) {
  151.         q.x = lower_bound(all(px), q.x) - px.begin();
  152.         q.l = lower_bound(all(py), q.l) - py.begin();
  153.         q.r = lower_bound(all(py), q.r) - py.begin();
  154.     }
  155.     sort(all(qq), cmp);
  156.     n *= 2;
  157.     vector<int> s(n);
  158.     for (int i = 0; i < n - 1; ++i) {
  159.         s[i] = py[i + 1] - py[i];
  160.     }
  161.     segtree sg(s);
  162.     ll ans = 0;
  163.     int i = 0, j = 0;
  164.     for (int x = 0; x < sz(px); ++x) {
  165.         if (x) {
  166.             ans += 1ll * (px[x] - px[x - 1]) * (py.back() - py.front() - sg.get_sum());
  167.         }
  168.         while (i < n && qq[i].x == x && qq[i].t == 0) {
  169.             sg.upd(0, 0, n, qq[i].l, qq[i].r, 1);          
  170.             ++i;
  171.         }
  172.         while (i < n && qq[i].x == x && qq[i].t == 1) {
  173.             sg.upd(0, 0, n, qq[i].l, qq[i].r, -1);          
  174.             ++i;
  175.         }
  176.     }
  177.     cout << ans << '\n';
  178.     return 0;
  179. }
Advertisement
RAW Paste Data Copied
Advertisement