Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- #define SZ(x) (int)(x.size())
- struct seg{
- int x, y1, y2;
- int del;//1 -> add, -1 -> minus
- }arr[200005];
- bool cmp(seg a, seg b){
- return a.x < b.x;
- }
- struct node{
- node *lch, *rch;
- int l, r, mid, tag, minval, cnt;//we have cnt minval
- node(int L, int R){
- l = L; r = R;
- mid = (l+r) / 2;
- tag = minval = 0;
- cnt = r-l+1;
- if(l != r)lch = new node(l, mid);
- else lch = nullptr;
- if(l != r)rch = new node(mid+1, r);
- else rch = nullptr;
- }
- void pushtag(){
- lch->tag += tag;
- rch->tag += tag;
- lch->minval += tag;
- rch->minval += tag;
- tag = 0;
- }
- void add(int L, int R, int V){
- //cout << l << ' ' << L << ' ' << r << ' ' << R << '\n';
- if(L == l && R == r){
- minval += V;
- tag += V;
- return;
- }
- if(lch == nullptr || rch == nullptr)return;// test
- pushtag();
- if(L <= mid)lch->add(L, min(R, mid), V);
- if(R > mid)rch->add(max(L, mid+1), R, V);
- minval = min(lch->minval, rch->minval);
- if(lch->minval == rch->minval)cnt = lch->cnt + rch->cnt;
- else if(minval == lch->minval)cnt = lch->cnt;
- else if(minval == rch->minval)cnt = rch->cnt;
- //cout << l << ' ' << r << ' ' << cnt << ' ' << minval << endl;;
- }
- };
- node *root;
- int32_t main(){
- int n;
- cin >> n;
- root = new node(1, 1000000);
- for(int i = 0; i < n; ++i){
- int l,r,d,u;
- cin >> l >> r >> d >> u;
- arr[i<<1] = {.x = l, .y1 = d, .y2 = u, .del = 1};
- arr[i<<1|1] = {.x = r, .y1 = d, .y2 = u, .del = -1};
- }
- n *= 2;
- sort(arr, arr+n, cmp);
- int ans = 0;
- for(int i = 0; i < n; ++i){
- if(i != 0){
- if(root->minval != 0)ans += (arr[i].x-arr[i-1].x) * (root->r-root->l+1);
- else ans += (arr[i].x-arr[i-1].x) * (root->r-root->l+1 - root->cnt);
- //cout << arr[i].x-arr[i-1].x << ' ' << root->r-root->l+1 - root->cnt << ' ' << ans << '\n';
- }
- root->add(arr[i].y1+1, arr[i].y2, arr[i].del);
- //cout << arr[i].x << ' ' << arr[i].y1 << ' ' << arr[i].y2 << ' ' << arr[i].del << '\n';;
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement