SHOW:
|
|
- or go back to the newest paste.
| 1 | #include <bits/stdc++.h> | |
| 2 | using namespace std; | |
| 3 | #define int long long | |
| 4 | #define SZ(x) (int)(x.size()) | |
| 5 | ||
| 6 | struct seg{
| |
| 7 | int x, y1, y2; | |
| 8 | int del;//1 -> add, -1 -> minus | |
| 9 | }arr[200005]; | |
| 10 | bool cmp(seg a, seg b){
| |
| 11 | return a.x < b.x; | |
| 12 | } | |
| 13 | ||
| 14 | struct node{
| |
| 15 | node *lch, *rch; | |
| 16 | int l, r, mid, tag, minval, cnt;//we have cnt minval | |
| 17 | node(int L, int R){
| |
| 18 | l = L; r = R; | |
| 19 | mid = (l+r) / 2; | |
| 20 | tag = minval = 0; | |
| 21 | cnt = r-l+1; | |
| 22 | if(l != r)lch = new node(l, mid); | |
| 23 | else lch = nullptr; | |
| 24 | if(l != r)rch = new node(mid+1, r); | |
| 25 | else rch = nullptr; | |
| 26 | } | |
| 27 | void pushtag(){
| |
| 28 | lch->tag += tag; | |
| 29 | rch->tag += tag; | |
| 30 | lch->minval += tag; | |
| 31 | rch->minval += tag; | |
| 32 | tag = 0; | |
| 33 | } | |
| 34 | void add(int L, int R, int V){
| |
| 35 | //cout << l << ' ' << L << ' ' << r << ' ' << R << '\n'; | |
| 36 | if(L == l && R == r){
| |
| 37 | minval += V; | |
| 38 | tag += V; | |
| 39 | return; | |
| 40 | } | |
| 41 | if(lch == nullptr || rch == nullptr)return;// test | |
| 42 | pushtag(); | |
| 43 | if(L <= mid)lch->add(L, min(R, mid), V); | |
| 44 | if(R > mid)rch->add(max(L, mid+1), R, V); | |
| 45 | minval = min(lch->minval, rch->minval); | |
| 46 | if(lch->minval == rch->minval)cnt = lch->cnt + rch->cnt; | |
| 47 | else if(minval == lch->minval)cnt = lch->cnt; | |
| 48 | else if(minval == rch->minval)cnt = rch->cnt; | |
| 49 | //cout << l << ' ' << r << ' ' << cnt << ' ' << minval << endl;; | |
| 50 | } | |
| 51 | }; | |
| 52 | ||
| 53 | node *root; | |
| 54 | ||
| 55 | int32_t main(){
| |
| 56 | int n; | |
| 57 | cin >> n; | |
| 58 | root = new node(1, 1000000); | |
| 59 | for(int i = 0; i < n; ++i){
| |
| 60 | int l,r,d,u; | |
| 61 | cin >> l >> r >> d >> u; | |
| 62 | arr[i<<1] = {.x = l, .y1 = d, .y2 = u, .del = 1};
| |
| 63 | arr[i<<1|1] = {.x = r, .y1 = d, .y2 = u, .del = -1};
| |
| 64 | } | |
| 65 | n *= 2; | |
| 66 | sort(arr, arr+n, cmp); | |
| 67 | int ans = 0; | |
| 68 | for(int i = 0; i < n; ++i){
| |
| 69 | if(i != 0){
| |
| 70 | if(root->minval != 0)ans += (arr[i].x-arr[i-1].x) * (root->r-root->l+1); | |
| 71 | else ans += (arr[i].x-arr[i-1].x) * (root->r-root->l+1 - root->cnt); | |
| 72 | //cout << arr[i].x-arr[i-1].x << ' ' << root->r-root->l+1 - root->cnt << ' ' << ans << '\n'; | |
| 73 | } | |
| 74 | root->add(arr[i].y1+1, arr[i].y2, arr[i].del); | |
| 75 | //cout << arr[i].x << ' ' << arr[i].y1 << ' ' << arr[i].y2 << ' ' << arr[i].del << '\n';; | |
| 76 | } | |
| 77 | cout << ans << '\n'; | |
| 78 | return 0; | |
| 79 | } |
