Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
- #pragma GCC optimize 03
- #pragma GCC optimize("unroll-loops")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef std::pair<int, int> pii;
- typedef std::pair<char, char> pcc;
- typedef std::pair<ll, ll> pll;
- typedef tree<int,
- null_type,
- less<int>,
- rb_tree_tag,
- tree_order_statistics_node_update> ordered_set;
- #define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
- #define file_in freopen("input.txt", "r", stdin);
- #define file_in_out freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
- #define all(x) (x).begin(), (x).end()
- #define sz(x) (int)x.size()
- #define fi first
- #define se second
- template<typename T>
- istream& operator>>(istream &in, vector<T> &v) {
- for (auto &it : v) {
- in >> it;
- }
- return in;
- }
- template<typename T>
- ostream& operator<<(ostream &out, const vector<T> &v) {
- for (auto &it : v) {
- out << it << " ";
- }
- return out;
- }
- template<typename T1, typename T2>
- istream& operator>>(istream &in, pair<T1, T2> &v) {
- in >> v.fi >> v.se;
- return in;
- }
- template<typename T1, typename T2>
- ostream& operator<<(ostream &out, const pair<T1, T2> &v) {
- out << v.fi << " " << v.se;
- return out;
- }
- struct query {
- int x, t, l, r;
- query() {}
- query(int x, int t, int l, int r, int i) : x(x), t(t), l(l), r(r) {}
- };
- bool cmp(query &q1, query &q2) {
- if (q1.x == q2.x) {
- if (q1.t == q2.t) {
- if (q1.l == q2.l) {
- return q1.r < q2.r;
- }
- return q1.l < q2.l;
- }
- return q1.t < q2.t;
- }
- return q1.x < q2.x;
- }
- struct Node {
- int ext = 2e9, sum = 0, add = 0;
- Node() {}
- Node(int x) { ext = 0; sum = x; }
- };
- struct segtree {
- vector<Node> t;
- segtree(vector<int> &a) { t.resize(4 * sz(a)); build(0, 0, sz(a), a); }
- void build(int id, int l, int r, vector<int> &a) {
- if (l + 1 == r) { t[id] = Node(a[l]); return; }
- build(id * 2 + 1, l, l + r >> 1, a);
- build(id * 2 + 2, l + r >> 1, r, a);
- t[id].ext = min(get(id * 2 + 1), get(id * 2 + 2));
- if (t[id].ext == get(id * 2 + 1)) {
- t[id].sum += t[id * 2 + 1].sum;
- }
- if (t[id].ext == get(id * 2 + 2)) {
- t[id].sum += t[id * 2 + 2].sum;
- }
- }
- void push(int id) {
- t[id].ext += t[id].add;
- t[id * 2 + 1].add += t[id].add;
- t[id * 2 + 2].add += t[id].add;
- t[id].add = 0;
- }
- int get(int id) {
- return t[id].ext + t[id].add;
- }
- int get_sum() {
- return (get(0) == 0 ? t[0].sum : 0);
- }
- void upd(int id, int l, int r, int lq, int rq, int x) {
- if (l >= rq || lq >= r) return;
- if (lq <= l && r <= rq) { t[id].add += x; return; }
- push(id);
- upd(id * 2 + 1, l, l + r >> 1, lq, rq, x);
- upd(id * 2 + 2, l + r >> 1, r, lq, rq, x);
- t[id].ext = min(get(id * 2 + 1), get(id * 2 + 2));
- t[id].sum = 0;
- if (t[id].ext == get(id * 2 + 1)) {
- t[id].sum += t[id * 2 + 1].sum;
- }
- if (t[id].ext == get(id * 2 + 2)) {
- t[id].sum += t[id * 2 + 2].sum;
- }
- }
- };
- int main() {
- fast
- // file_in
- // file_in_out
- int n;
- cin >> n;
- if (n == 0) {
- cout << 0 << '\n';
- return 0;
- }
- vector<query> qq(2 * n);
- vector<int> px, py;
- for (int i = 0; i < n; ++i) {
- int x1, x2, l, r;
- cin >> x1 >> l >> x2 >> r;
- px.push_back(x1); px.push_back(x2);
- py.push_back(l); py.push_back(r);
- qq[2 * i + 0].x = x1; qq[2 * i + 0].t = 0; qq[2 * i + 0].l = l; qq[2 * i + 0].r = r;
- qq[2 * i + 1].x = x2; qq[2 * i + 1].t = 1; qq[2 * i + 1].l = l; qq[2 * i + 1].r = r;
- }
- sort(all(px)); sort(all(py));
- for (auto &q : qq) {
- q.x = lower_bound(all(px), q.x) - px.begin();
- q.l = lower_bound(all(py), q.l) - py.begin();
- q.r = lower_bound(all(py), q.r) - py.begin();
- }
- sort(all(qq), cmp);
- n *= 2;
- vector<int> s(n);
- for (int i = 0; i < n - 1; ++i) {
- s[i] = py[i + 1] - py[i];
- }
- segtree sg(s);
- ll ans = 0;
- int i = 0, j = 0;
- for (int x = 0; x < sz(px); ++x) {
- if (x) {
- ans += 1ll * (px[x] - px[x - 1]) * (py.back() - py.front() - sg.get_sum());
- }
- while (i < n && qq[i].x == x && qq[i].t == 0) {
- sg.upd(0, 0, n, qq[i].l, qq[i].r, 1);
- ++i;
- }
- while (i < n && qq[i].x == x && qq[i].t == 1) {
- sg.upd(0, 0, n, qq[i].l, qq[i].r, -1);
- ++i;
- }
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement