Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- using namespace std;
- const int N = 2E5 + 5;
- int n;
- long long x, y, u, v, ans = 0;
- vector<long long> ve;
- struct event {
- long long u, l, r, val;
- event(long long _u, long long _l, long long _r, long long _val) : u(_u), l(_l), r(_r), val(_val) {}
- };
- vector<event> sw;
- struct segment_tree {
- #define m (l + r) / 2
- #define lc i * 2
- #define rc i * 2 + 1
- long long eve[4 * N], odd[4 * N];
- pair<int, long long> mi[4 * N];
- int lz[4 * N];
- void apply(int i, int v) {
- lz[i] += v;
- mi[i].fi += v;
- if (abs(v) % 2 == 1) {
- swap(eve[i], odd[i]);
- }
- }
- void down(int i) {
- apply(lc, lz[i]);
- apply(rc, lz[i]);
- lz[i] = 0;
- }
- void build(int l, int r, int i) {
- if (l == r) {
- eve[i] = mi[i].se = ve[l + 1] - ve[l];
- odd[i] = 0;
- } else {
- build(l, m, lc);
- build(m + 1, r, rc);
- eve[i] = eve[lc] + eve[rc];
- odd[i] = 0;
- mi[i].se = eve[i];
- }
- }
- void update(int l, int r, int i, int L, int R, int v) {
- if (l > R || r < L || L > R) {
- return;
- } else if (L <= l && r <= R) {
- apply(i, v);
- } else {
- down(i);
- update(l, m, lc, L, R, v);
- update(m + 1, r, rc, L, R, v);
- eve[i] = eve[lc] + eve[rc];
- odd[i] = odd[lc] + odd[rc];
- mi[i] = min(mi[lc], mi[rc]);
- if (mi[lc].fi == mi[rc].fi) {
- mi[i].se = mi[lc].se + mi[rc].se;
- }
- }
- }
- #undef m
- #undef lc
- #undef rc
- } seg;
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cin >> n;
- for (int i = 1; i <= n; i++) {
- cin >> x >> y >> u >> v;
- if (x > u) {
- swap(x, u);
- }
- if (y > v) {
- swap(y, v);
- }
- if (x == u || y == v) {
- continue;
- }
- sw.push_back(event(x, y, v, 1)); sw.push_back(event(u, y, v, -1));
- ve.push_back(y); ve.push_back(v);
- }
- if (sw.empty()) {
- return cout << 0, 0;
- }
- sort(ve.begin(), ve.end());
- sort(sw.begin(), sw.end(), [](const event &u, const event &v) {
- return u.u < v.u;
- });
- ve.erase(unique(ve.begin(), ve.end()), ve.end());
- int n = ve.size() - 1;
- seg.build(0, n - 1, 1);
- for (int i = 0; i < sw.size() - 1; i++) {
- int l = distance(ve.begin(), lower_bound(ve.begin(), ve.end(), sw[i].l));
- int r = distance(ve.begin(), lower_bound(ve.begin(), ve.end(), sw[i].r)) - 1;
- seg.update(0, n - 1, 1, l, r, sw[i].val);
- ans += 1LL * (sw[i + 1].u - sw[i].u) * (seg.eve[1] - (seg.mi[1].fi == 0) * seg.mi[1].se);
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement