Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <iomanip>
- #include <queue>
- #include <cmath>
- #include <algorithm>
- #include <unordered_map>
- #include <tuple>
- #include <iomanip>
- #include <stdio.h>
- #include <map>
- #include <bitset>
- #include <set>
- #include <stack>
- #include <queue>
- #include <unordered_set>
- #include <cassert>
- #include <stdlib.h>
- #include <time.h>
- #include <random>
- //#pragma GCC optimize("Ofast,no-stack-protector")
- //#pragma GCC target("sse,sse2,sse3,sse3,sse4")
- //#pragma GCC optimize("unroll-loops")
- //#pragma GCC optimize("fast-math")
- //#pragma GCC target("avx2")
- //#pragma GCC optimize("section-anchors")
- //#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
- //#pragma GCC optimize("vpt")
- //#pragma GCC optimize("rename-registers")
- //#pragma GCC optimize("move-loop-invariants")
- //#pragma GCC optimize("unswitch-loops")
- //#pragma GCC optimize("function-sections")
- //#pragma GCC optimize("data-sections")
- #define int long long
- #define ll long long
- #define ull unsigned long long
- #define all(a) (a).begin(), (a).end()
- #define pii pair<int, int>
- #define pb push_back
- #define ld long double
- using namespace std;
- const int INF = 1e17;
- //const int mod = 2600000069;
- //const int p = 179;
- struct point {
- int x, y;
- point() {}
- point(int x_, int y_) {
- x = x_;
- y = y_;
- }
- };
- struct event {
- int type;
- point a;
- event() {}
- event(int type_, point a_) {
- type = type_;
- a = a_;
- }
- };
- int n;
- vector<pair<point, point>> vert, hor;
- vector<int> y;
- int y_cnt = 0;
- vector<event> x_events, y_events;
- map<int, int> y_ind;
- int ans = 0, y_events_ind = 0, y_events_size;
- bool comp_x(event a, event b) {
- if (a.a.x == b.a.x) return a.type < b.type;
- return a.a.x < b.a.x;
- }
- bool comp_y(event a, event b) {
- if (a.a.x == b.a.x) {
- if (a.a.y == b.a.y) {
- return a.type < b.type;
- }
- return a.a.y < b.a.y;
- }
- return a.a.x < b.a.x;
- }
- struct node {
- int min = 0, cnt = 1;
- node() {}
- node (int min_, int cnt_) {
- min = min_;
- cnt = cnt_;
- }
- };
- vector<node> t;
- vector<int> mod;
- void in() {
- cin >> n;
- point a, b;
- for (int i = 0; i < n; i++) {
- cin >> a.x >> a.y >> b.x >> b.y;
- if (a.x == b.x) {
- if (a.y > b.y) swap(a, b);
- vert.pb({a, b});
- y.pb(a.y);
- y.pb(b.y);
- x_events.pb(event(2, point(a.x, 0)));
- y_events.pb(event(0, a));
- y_events.pb(event(1, b));
- } else {
- if (a.x > b.x) swap(a, b);
- hor.pb({a, b});
- y.pb(a.y);
- x_events.pb(event(0, a));
- x_events.pb(event(1, b));
- }
- }
- sort(all(x_events), comp_x);
- sort(all(y_events), comp_y);
- sort(all(y));
- y.resize(unique(all(y)) - y.begin());
- y_cnt = y.size();
- t.resize(8 * y_cnt);
- mod.resize(8 * y_cnt);
- for (int i = 0; i < y_cnt; i++) {
- y_ind[y[i]] = i;
- }
- y_events_size = y_events.size();
- }
- node merge(node a, node b) {
- node c;
- if (a.min == b.min) {
- c = a;
- c.cnt += b.cnt;
- } else if (a.min < b.min) c = a;
- else c = b;
- return c;
- }
- void push(int v) {
- mod[2 * v + 1] += mod[v];
- mod[2 * v + 2] += mod[v];
- t[v].min += mod[v];
- mod[v] = 0;
- }
- void build(int v, int l, int r) {
- if (r - l == 1) {
- t[v].cnt = 1;
- t[v].min = 0;
- return;
- }
- int m = (l + r) / 2;
- build(2 * v + 1, l, m);
- build(2 * v + 2, m, r);
- t[v] = merge(t[2 * v + 1], t[2 * v + 2]);
- }
- void update(int v, int l, int r, int askl, int askr, int val) {
- if (l >= askr || r <= askl) return;
- if (l >= askl && r <= askr) {
- mod[v] += val;
- push(v);
- return;
- }
- push(v);
- int m = (l + r) / 2;
- update(2 * v + 1, l, m, askl, askr, val);
- update(2 * v + 2, m, r, askl, askr, val);
- t[v] = merge(t[2 * v + 1], t[2 * v + 2]);
- }
- node sum(int v, int l, int r, int askl, int askr) {
- if (l >= askr || r <= askl) return node(INF, 0);
- push(v);
- if (l >= askl && r <= askr) return t[v];
- int m = (l + r) / 2;
- return merge(sum(2 * v + 1, l, m, askl, askr), sum(2 * v + 2, m, r, askl, askr));
- }
- node q;
- void scanline_y(int x) {
- if (y_events_ind == y_events_size) return;
- int open = 0;
- int lst = y_events[y_events_ind].a.y;
- for (; y_events_ind < y_events_size && y_events[y_events_ind].a.x == x;) {
- while (y_events_ind < y_events_size && y_events[y_events_ind].a.x == x && y_events[y_events_ind].type == 0) {open++; y_events_ind++;}
- while (y_events_ind < y_events_size && y_events[y_events_ind].a.x == x && y_events[y_events_ind].type == 1) {open--; y_events_ind++;}
- if (open == 0) {
- q = sum(0, 0, y_cnt, y_ind[lst], y_ind[y_events[y_events_ind - 1].a.y] + 1);
- if (q.min == 0) {
- ans += y_events[y_events_ind - 1].a.y - lst + 1 - (y_ind[y_events[y_events_ind - 1].a.y] - y_ind[lst] + 1);
- if (q.min == 0) ans += q.cnt;
- }
- if (y_events_ind < y_events_size) lst = y_events[y_events_ind].a.y;
- }
- }
- }
- void scanline_x() {
- build(0, 0, y_cnt);
- int sz = x_events.size(), x, lst = x_events[0].a.x;
- for (int i = 0; i < sz;) {
- x = x_events[i].a.x;
- if (x_events[i].type == 2) {
- scanline_y(x);
- i++;
- continue;
- }
- q = sum(0, 0, y_cnt, 0, y_cnt);
- ans += y_cnt * (x - lst);
- if (t[0].min == 0) ans -= t[0].cnt * (x - lst);
- while (i < sz && x_events[i].a.x == x && x_events[i].type == 0) {
- update(0, 0, y_cnt, y_ind[x_events[i].a.y], y_ind[x_events[i].a.y] + 1, 1);
- i++;
- }
- q = sum(0, 0, y_cnt, 0, y_cnt);
- ans += y_cnt;
- if (t[0].min == 0) ans -= t[0].cnt;
- scanline_y(x);
- while (i < sz && x_events[i].a.x == x && x_events[i].type == 1) {
- update(0, 0, y_cnt, y_ind[x_events[i].a.y], y_ind[x_events[i].a.y] + 1, -1);
- i++;
- }
- while (i < sz && x_events[i].a.x == x) i++;
- lst = x + 1;
- }
- }
- signed main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- in();
- // for (auto k : y) {
- // cout << k << " ";
- // }
- // cout << "\n";
- scanline_x();
- cout << ans;
- }
- /*
- 2
- 0 1 2 1
- 0 3 2 3
- 2
- 0 0 0 1
- 0 1 0 2
- 3
- 0 1 2 1
- 0 3 2 3
- 1 4 1 2
- */
Advertisement
Add Comment
Please, Sign In to add comment