Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2016
2,663
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.17 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define P(x,y) make_pair(x,y)
  3. using namespace std;
  4. class Rectangle{
  5.     public:
  6.     int x1 , y1 , x2 , y2;
  7.     static Rectangle empt;
  8.     Rectangle(){
  9.         x1=y1=x2=y2=0;
  10.     }
  11.     Rectangle(int X1 , int Y1 , int X2 , int Y2){
  12.         x1 = X1; y1=Y1;
  13.         x2 = X2; y2=Y2;
  14.     }
  15.     Rectangle intersect(Rectangle R){
  16.         if(R.x1 >= x2 || R.x2 <= x1) return empt;
  17.         if(R.y1 >= y2 || R.y2 <= y1) return empt;
  18.         return Rectangle(max(x1 , R.x1) , max(y1 , R.y1) , min(x2 , R.x2) , min(y2 , R.y2));
  19.     }
  20. };
  21. struct Event{
  22.     int x , y1 , y2 , type;
  23.     Event(){}
  24.     Event(int x , int y1 , int y2 , int type):x(x) , y1(y1) , y2(y2) , type(type){}
  25. };
  26. bool operator < (const Event&A , const Event&B){
  27.     //if(A.x != B.x)
  28.     return A.x < B.x;
  29.     //if(A.y1 != B.y1) return A.y1 < B.y1;
  30.     //if(A.y2 != B.y2()) A.y2 < B.y2;
  31. }
  32. const int MX=(1<<17);
  33. struct Node{
  34.     int prob , sum , ans;
  35.     Node(){}
  36.     Node(int prob , int sum , int ans):prob(prob) , sum(sum) , ans(ans){}
  37. };
  38. Node tree[MX*4];
  39. int interval[MX];
  40. void build(int x , int a , int b){
  41.     tree[x] = Node(0 , 0 , 0);
  42.     if(a==b){
  43.         tree[x].sum+=interval[a];
  44.         return;
  45.     }
  46.     build(x*2 , a , (a+b)/2);
  47.     build(x*2+1 , (a+b)/2+1 , b);
  48.     tree[x].sum = tree[x*2].sum + tree[x*2+1].sum;
  49. }
  50. int ask(int x){
  51.     if(tree[x].prob) return tree[x].sum;
  52.     return tree[x].ans;
  53. }
  54. int st , en , V;
  55. void update(int x , int a , int b){
  56.     if(st>b || en<a) return;
  57.     if(a>=st && b<=en){
  58.         tree[x].prob+=V;
  59.         return;
  60.     }
  61.     update(x*2 , a , (a+b)/2);
  62.     update(x*2+1 , (a+b)/2+1 , b);
  63.     tree[x].ans = ask(x*2) + ask(x*2+1);
  64. }
  65. Rectangle Rectangle::empt = Rectangle();
  66. vector < Rectangle > Rect;
  67. vector < int > sorted;
  68. vector < Event > sweep;
  69. void compressncalc(){
  70.     sweep.clear();
  71.     sorted.clear();
  72.     for(auto R : Rect){
  73.         sorted.push_back(R.y1);
  74.         sorted.push_back(R.y2);
  75.     }
  76.     sort(sorted.begin() , sorted.end());
  77.     sorted.erase(unique(sorted.begin() , sorted.end()) , sorted.end());
  78.     int sz = sorted.size();
  79.     for(int j=0;j<sorted.size() - 1;j++)
  80.         interval[j+1] = sorted[j+1] - sorted[j];
  81.     for(auto R : Rect){
  82.         sweep.push_back(Event(R.x1 , R.y1 , R.y2 , 1));
  83.         sweep.push_back(Event(R.x2 , R.y1 , R.y2 , -1));
  84.     }
  85.     sort(sweep.begin() , sweep.end());
  86.     build(1,1,sz-1);
  87. }
  88. long long ans;
  89. void Sweep(){
  90.     ans=0;
  91.     if(sorted.empty() || sweep.empty()) return;
  92.     int last = 0 , sz_ = sorted.size();
  93.     for(int j=0;j<sweep.size();j++){
  94.         ans+= 1ll * (sweep[j].x - last) * ask(1);
  95.         last = sweep[j].x;
  96.         V = sweep[j].type;
  97.         st = lower_bound(sorted.begin() , sorted.end() , sweep[j].y1) - sorted.begin() + 1;
  98.         en = lower_bound(sorted.begin() , sorted.end() , sweep[j].y2) - sorted.begin();
  99.         update(1 , 1 , sz_-1);
  100.     }
  101. }
  102. int main(){
  103. //    freopen("in.in","r",stdin);
  104.     int n;
  105.     scanf("%d",&n);
  106.     for(int j=1;j<=n;j++){
  107.         int a , b ,c  , d;
  108.         scanf("%d %d %d %d",&a,&b,&c,&d);
  109.         Rect.push_back(Rectangle(a , b , c , d));
  110.     }
  111.     compressncalc();
  112.     Sweep();
  113.     cout<<ans<<endl;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement