Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <numeric>
- #include <string>
- #include <queue>
- #include <deque>
- #include <iomanip>
- #include <map>
- #include <set>
- #include <random>
- #include <cmath>
- #include <unordered_map>
- #include <unordered_set>
- #include <stack>
- #include <algorithm>
- #define fast() ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
- #define all(array) array.begin(), array.end()
- #define pb push_back
- #define eb emplace_back
- #pragma GCC target ("avx2")
- #pragma GCC optimize ("Ofast")
- using ll = long long;
- //using ll = int;
- using ull = unsigned long long;
- using ld = long double;
- using namespace std;
- const ll INF = 1e18;
- const int inf = 1e9;
- const int mod = 1e9 + 7;
- const int P = 72;
- template<typename Type>
- istream& operator>>(istream &in, vector<Type> &x) {
- for (auto &i : x) in >> i;
- return in;
- }
- template<typename Type>
- ostream& operator<<(ostream &out, vector<Type> &x) {
- for (auto i: x) out << i << " ";
- return out;
- }
- struct node {
- ll min;
- ll lazy;
- ll cnty;
- };
- const ll maxn = 2e5;
- vector<node> tree;
- vector<ll> x;
- ll mx;
- node make_data(ll tl, ll val) {
- node res{};
- res.min = val;
- res.cnty = x[tl + 1] - x[tl];
- return res;
- }
- node combine(node& l, node& r) {
- node res{};
- if (l.min < r.min) {
- return l;
- } else if (r.min < l.min) {
- return r;
- } else {
- res.min = l.min;
- res.cnty = l.cnty + r.cnty;
- return res;
- }
- }
- void push(ll tl, ll tr, ll v) {
- if (tree[v].lazy != 0) {
- tree[v].min += tree[v].lazy;
- if (tr - tl > 1) {
- tree[v * 2 + 1].lazy += tree[v].lazy;
- tree[v * 2 + 2].lazy += tree[v].lazy;
- }
- tree[v].lazy = 0;
- }
- }
- void build(ll tl, ll tr, ll v) {
- if (tr - tl == 1) {
- tree[v] = make_data(tl, 0);
- return;
- }
- ll tm = (tr + tl) / 2;
- build(tl, tm, v * 2 + 1);
- build(tm, tr, v * 2 + 2);
- tree[v] = combine(tree[v * 2 + 1], tree[v * 2 + 2]);
- }
- void update(ll l, ll r, ll val, ll tl, ll tr, ll v) {
- push(tl, tr, v);
- if (l >= tr || r <= tl) {
- return;
- }
- if (tl >= l && tr <= r) {
- tree[v].lazy += val;
- push(tl, tr, v);
- return;
- }
- ll tm = (tr + tl) / 2;
- update(l, r, val, tl, tm, v * 2 + 1);
- update(l, r, val, tm, tr, v * 2 + 2);
- tree[v] = combine(tree[v * 2 + 1], tree[v * 2 + 2]);
- }
- ll sum(ll l, ll r, ll tl, ll tr, ll v) {
- push(tl, tr, v);
- if (l >= tr || r <= tl) {
- return 0;
- }
- if (tl >= l && tr <= r) {
- return tree[v].cnty;
- }
- ll tm = (tr + tl) / 2;
- ll s1 = sum(l, r, tl, tm, v * 2 + 1);
- ll s2 = sum(l, r, tm, tr, v * 2 + 2);
- //tree[v] = combine(tree[v * 2 + 1], tree[v * 2 + 2]);
- return s1 + s2;
- }
- ll min(ll l, ll r, ll tl, ll tr, ll v) {
- push(tl, tr, v);
- if (l >= tr || r <= tl) {
- return INF;
- }
- if (tl >= l && tr <= r) {
- return tree[v].min;
- }
- ll tm = (tr + tl) / 2;
- return min(min(l, r, tl, tm, v * 2 + 1), min(l, r, tm, tr, v * 2 + 2));
- }
- void solve() {
- ll n;
- cin >> n;
- if (n == 0) {
- cout << 0;
- return;
- }
- vector<ll> y;
- ll x1, x2, y1, y2;
- vector<pair<pair<ll, ll>, pair<ll, ll>>> Q;
- unordered_set<ll> sx, sy;
- for (ll i = 0; i < n; ++i) {
- cin >> x1 >> y1 >> x2 >> y2;
- //x1[i] += 1e9; y1[i] += 1e9; x2[i] += 1e9; y2[i] += 1e9;
- Q.pb({{x1, y1}, {x2, y2}});
- if (sx.find(x1) == sx.end()) {
- x.pb(x1);
- sx.insert(x1);
- }
- if (sx.find(x2) == sx.end()) {
- x.pb(x2);
- sx.insert(x2);
- }
- if (sy.find(y1) == sy.end()) {
- y.pb(y1);
- sy.insert(y1);
- }
- if (sy.find(y2) == sy.end()) {
- y.pb(y2);
- sy.insert(y2);
- }
- }
- unordered_map<ll, ll> mpx, mpy;
- sort(all(x));
- sort(all(y));
- mx = (ll)x.size();
- ll my = (ll)y.size();
- for (ll i = 0; i < mx; ++i) {
- mpx[x[i]] = i;
- }
- for (ll i = 0; i < my; ++i) {
- mpy[y[i]] = i;
- }
- vector<vector<pair<pair<ll, ll>, ll>>> q(my);
- for (auto p : Q) {
- x1 = p.first.first, y1 = p.first.second, x2 = p.second.first, y2 = p.second.second;
- q[mpy[y1]].pb({{mpx[x1], mpx[x2]}, 1});
- q[mpy[y2]].pb({{mpx[x1], mpx[x2]}, -1});
- }
- tree.resize(mx * 4);
- build(0, mx - 1, 0);
- ll ans = 0;
- for (ll i = 0; i < my - 1; ++i) {
- for (pair<pair<ll, ll>, ll> p : q[i]) {
- ll l = p.first.first, r = p.first.second, v = p.second;
- if (r < l) swap(l, r);
- update(l, r, v, 0, mx - 1, 0);
- }
- ans += (x[mx - 1] - x[0] - ((min(0, mx - 1, 0, mx - 1, 0) > 0) ? 0 : sum(0, mx - 1, 0, mx - 1, 0))) * ((i == my - 1) ? 0 : y[i + 1] - y[i]);
- }
- cout << ans;
- }
- int main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- clock_t timer = clock();
- #endif
- fast();
- ll tc = 1;
- ll cfmode = 0;
- if (cfmode) cin >> tc;
- while (tc--) {
- solve();
- if (tc) cout << "\n";
- }
- #ifdef LOCAL
- cout << fixed << setprecision(10);
- cout << "\n\nExecution time: " << (long double) (clock() - timer) / CLOCKS_PER_SEC;
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement