Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 30100
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- #define int long long
- using namespace std;
- typedef long double ld;
- const int inf = 1e10;
- const int minf = -1e10;
- int n;
- struct node{
- int x, u, d, t;
- };
- struct tree{
- int len, cnt;
- };
- node a[N];
- tree tr[N*5];
- bool cmp(node a, node b)
- {
- return (a.x < b.x || (a.x==b.x && a.t < b.t));
- }
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- cin >> n;
- for(int i=1; i<=n; i++)
- {
- int x1, y1, x2, y2;
- cin >> x1 >> y1 >> x2 >> y2;
- a[i].x = x1;
- a[i+n].x = x2;
- a[i].d = a[i+n].d = y1;
- a[i].u = a[i+n].u = y2;
- a[i].t = 1;
- a[i+n].t = -1;
- }
- n*=2;
- sort(a+1,a+1+n,cmp);
- //for(int i=1; i<=n; i++) cout << a[i].x << ' ' << a[i].u << ' ' << a[i].d << endl;
- }
- void up(int id, int l, int r, int u, int v, int ty)
- {
- if (r < u || v < l) return;
- if (u <= l && r <= v)
- {
- tr[id].cnt += ty;
- //canh mo
- if (ty==1)
- {
- cout << l << ' ' << r << endl;
- tr[id].len = (r-l+1);
- //do dai
- }
- else{
- if (tr[id].cnt==0)
- tr[id].len = tr[id*2].len + tr[id*2+1].len;
- }
- return;
- }
- int mid = (l+r)/2;
- up(id*2,l,mid,u,v,ty);
- up(id*2+1,mid+1,r,u,v,ty);
- if (tr[id].cnt==0) tr[id].len = tr[id*2].len + tr[id*2+1].len;
- }
- void proc()
- {
- int ans = 0;
- for(int i=1; i<=n; i++)
- {
- ans += (a[i].x-a[i-1].x)*(tr[1].len);
- //cout << a[i].d << ' ' << a[i].u-1 << ": \n";
- up(1,0,N, a[i].d, a[i].u-1, a[i].t);
- }
- cout << ans;
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement