Advertisement
MinhNGUYEN2k4

AREA

May 22nd, 2021
200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.32 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 30100
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int n;
  28. struct node{
  29.     int x, u, d, t;
  30. };
  31. struct tree{
  32.     int len, cnt;
  33. };
  34. node a[N];
  35. tree tr[N*5];
  36.  
  37. bool cmp(node a, node b)
  38. {
  39.     return (a.x < b.x || (a.x==b.x && a.t < b.t));
  40. }
  41.  
  42. void readfile()
  43. {
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(0);cout.tie(0);
  46.     if (fopen(Task".inp","r"))
  47.     {
  48.         freopen(Task".inp","r",stdin);
  49.         //freopen(Task".out","w",stdout);
  50.     }
  51.     cin >> n;
  52.     for(int i=1; i<=n; i++)
  53.     {
  54.         int x1, y1, x2, y2;
  55.         cin >> x1 >> y1 >> x2 >> y2;
  56.         a[i].x = x1;
  57.         a[i+n].x = x2;
  58.         a[i].d = a[i+n].d = y1;
  59.         a[i].u = a[i+n].u = y2;
  60.         a[i].t = 1;
  61.         a[i+n].t = -1;
  62.     }
  63.     n*=2;
  64.     sort(a+1,a+1+n,cmp);
  65.     //for(int i=1; i<=n; i++) cout << a[i].x << ' ' << a[i].u << ' ' << a[i].d << endl;
  66. }
  67.  
  68. void up(int id, int l, int r, int u, int v, int ty)
  69. {
  70.     if (r < u || v < l) return;
  71.     if (u <= l && r <= v)
  72.     {
  73.         tr[id].cnt += ty;
  74.         //canh mo
  75.         if (ty==1)
  76.         {
  77.             cout << l << ' ' << r << endl;
  78.             tr[id].len = (r-l+1);
  79.             //do dai
  80.         }
  81.         else{
  82.             if (tr[id].cnt==0)
  83.                 tr[id].len = tr[id*2].len + tr[id*2+1].len;
  84.         }
  85.         return;
  86.     }
  87.     int mid = (l+r)/2;
  88.     up(id*2,l,mid,u,v,ty);
  89.     up(id*2+1,mid+1,r,u,v,ty);
  90.  
  91.     if (tr[id].cnt==0) tr[id].len = tr[id*2].len + tr[id*2+1].len;
  92. }
  93.  
  94. void proc()
  95. {
  96.     int ans = 0;
  97.     for(int i=1; i<=n; i++)
  98.     {
  99.         ans += (a[i].x-a[i-1].x)*(tr[1].len);
  100.         //cout << a[i].d << ' ' << a[i].u-1 << ": \n";
  101.         up(1,0,N, a[i].d, a[i].u-1, a[i].t);
  102.     }
  103.     cout << ans;
  104. }
  105.  
  106. signed main()
  107. {
  108.     readfile();
  109.     proc();
  110.     return 0;
  111. }
  112.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement