fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  3. #define ll long long
  4. #define pb push_back
  5. #define pii pair<int,int>
  6. #define pll pair<ll,ll>
  7. #define fi first
  8. #define se second
  9. #define all(t) t.begin(),t.end()
  10. using namespace std;
  11.  
  12. const ll inf=1e10;
  13. const int maxn=200003;
  14.  
  15. int n;
  16. struct ox
  17. {
  18.     int x,y,sts;
  19.     ox(){}
  20.     ox(int x, int y, int sts):
  21.         x(x),y(y),sts(sts) {}
  22. };
  23. struct oy
  24. {
  25.     int x,y,Y;
  26.     oy(){}
  27.     oy(int x, int y, int Y):
  28.         x(x),y(y),Y(Y) {}
  29. };
  30. vector<ox>A;
  31. vector<oy>B;
  32. vector<int>N;
  33. void ADD(int x, int y, int u, int v)
  34. {
  35.     if(x==u)
  36.         B.pb(oy(x,min(y,v),max(y,v)));
  37.     else
  38.     {
  39.  
  40.         if(x>u) swap(x,u);
  41.         A.pb(ox(x,y,1));
  42.         A.pb(ox(u+1,y,-1));
  43.     }
  44. }
  45. int POS(int X)
  46. {
  47.     return lower_bound(N.begin(),N.end(),X)+1-N.begin();
  48. }
  49. ll node[maxn*15];
  50. void update(int l, int r, int lab, int a, ll x)
  51. {
  52.     if(l==r)
  53.     {
  54.         node[lab]+=x;
  55.         return;
  56.     }
  57.     int mid=(l+r)/2;
  58.     if(a<=mid) update(l,mid,lab*2,a,x);
  59.     else update(mid+1,r,lab*2+1,a,x);
  60.     node[lab]=node[lab*2]+node[lab*2+1];
  61. }
  62. ll get(int l, int r, int lab, int a, int b)
  63. {
  64.     if(l>b || r<a) return 0;
  65.     if(l>=a && r<=b) return node[lab];
  66.     int mid=(l+r)/2;
  67.     return get(l,mid,lab*2,a,b)+get(mid+1,r,lab*2+1,a,b);
  68. }
  69. bool cmp1(ox a, ox b)
  70. {
  71.     return a.x<b.x;
  72. }
  73. bool cmp2(oy a, oy b)
  74. {
  75.     return a.x<b.x;
  76. }
  77. int main()
  78. {
  79.     ios_base::sync_with_stdio(0);
  80.     cin.tie(0);cout.tie(0);
  81.     int n;
  82.     cin>>n;
  83.     for(int i=1;i<=n;i++)
  84.     {
  85.         int x,y,u,v;
  86.         cin>>x>>y>>u>>v;
  87.         N.pb(x);N.pb(y);N.pb(u);N.pb(v);
  88.         ADD(x,y,u,v);
  89.     }
  90.     sort(N.begin(),N.end());
  91.     N.erase(unique(N.begin(),N.end()),N.end());
  92.     for(int i=0;i<A.size();i++)
  93.         A[i]=ox(POS(A[i].x),POS(A[i].y),A[i].sts);
  94.     for(int i=0;i<B.size();i++)
  95.         B[i]=oy(POS(B[i].x),POS(B[i].y),POS(B[i].Y));
  96.     int MX=N.size();
  97.     int i=0,j=0;
  98.     ll ans=0;
  99.     sort(A.begin(),A.end(),cmp1);
  100.     sort(B.begin(),B.end(),cmp2);
  101.     for(int x0=1;x0<=MX;x0++)
  102.     {
  103.         while(true)
  104.         {
  105.             if(i>=A.size()) break;
  106.             if(A[i].x<x0) i++;
  107.             else if(A[i].x==x0)
  108.             {
  109.                  update(1,MX,1,A[i].y,A[i].sts);
  110.                  ++i;
  111.                  ///cout<<"x";
  112.             }
  113.             else break;
  114.         }
  115.         while(true)
  116.         {
  117.             if(j>=B.size()) break;
  118.             if(B[j].x<x0) ++j;
  119.             else if(B[j].x==x0)
  120.             {
  121.                 ans+=get(1,MX,1,B[j].y,B[j].Y);
  122.                 ++j;
  123.                 ///cout<<"x";
  124.             }
  125.             else break;
  126.         }
  127.     }
  128.     cout<<ans;
  129. }
  130. /*
  131. 12
  132. -4 1 -1 1
  133. -2 2 3 2
  134. -5 -4 -3 -4
  135. 4 2 8 2
  136. 1 -1 5 -1
  137. 1 -3 5 -3
  138. -4 -4 -4 2
  139. -3 0 -3 3
  140. -1 0 -1 3
  141. 2 -2 2 4
  142. 3 0 3 -4
  143. 7 1 7 4
  144.  
  145. out : 10
  146. */
  147.  
Success #stdin #stdout 0.02s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ozpVwU
Trò chơi - OLP 30/4 năm 2021
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!