fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define int long long 
  5. using namespace std;
  6. const long long oo=1e18;
  7. const int mod=1e9+7;
  8. const int base=31;
  9. int Test=1;
  10. void home()
  11. {
  12.     if(fopen("main.inp","r")) 
  13.     freopen("main.inp","r",stdin),
  14.     freopen("main.out","w",stdout);
  15. }
  16. bool bit(int mask,int i){return (mask>>i)&1;}
  17. struct Fenwick
  18. {
  19.     int n;vector<int>f;
  20.     Fenwick(int _n):n(_n){f.resize(n+5);}
  21.     void Update(int id,int val)
  22.     {
  23.         for(;id<=n;id+=id&-id)
  24.             f[id]+=val;
  25.     }
  26.     int Get(int id)
  27.     {
  28.         int d=0;
  29.         for(;id;id-=id&-id)
  30.             d+=f[id];
  31.         return d;
  32.     }
  33. }*BIT;
  34. int Dist(int x,int y,int u,int v)
  35. {
  36.     return (x-u)*(x-u)+(v-y)*(v-y);
  37. }
  38. pair<int,int>Kien[1000006];
  39. pair<int,int>Thanh[1000006];
  40. int n,q;
  41. int x[1000006],y[1000006],z[1000006];
  42. int xKien,yKien,xThanh,yThanh;
  43. int ThanhId[1000006],ThanhVal[1000006];
  44.  
  45. struct Query
  46. {
  47.     int r1,r2,id;
  48.     bool operator<(const Query &ot)const{return r1<ot.r1;}
  49. }Q[1000006];
  50. int kq[1000006];
  51. vector<int>mau[1000006];int miid[1000006];
  52. bool pass[1000006];
  53. void Tcmduc_VOI26()
  54. {
  55.     cin>>n;
  56.     for(int i=1;i<=n;i++)
  57.     {
  58.         cin>>x[i]>>y[i]>>z[i];
  59.         mau[z[i]].push_back(i);
  60.     }
  61.     cin>>xKien>>yKien>>xThanh>>yThanh;
  62.     for(int i=1;i<=n;i++)
  63.     {
  64.         Kien[i]={Dist(x[i],y[i],xKien,yKien),i};
  65.         Thanh[i]={Dist(x[i],y[i],xThanh,yThanh),i};
  66.         ThanhVal[i]=Dist(x[i],y[i],xThanh,yThanh);
  67.     }
  68.     sort(Kien+1,Kien+n+1);
  69.     sort(Thanh+1,Thanh+n+1);
  70.     sort(ThanhVal+1,ThanhVal+n+1);
  71.     for(int i=1;i<=n;i++)ThanhId[Thanh[i].se]=i;
  72.     cin>>q;
  73.     for(int i=1;i<=q;i++)
  74.     {
  75.         cin>>Q[i].r1>>Q[i].r2;Q[i].id=i;
  76.         Q[i].r1*=Q[i].r1;Q[i].r2*=Q[i].r2;
  77.     }
  78.     sort(Q+1,Q+q+1);
  79.     int cur=1;
  80.     BIT=new Fenwick(n);
  81.     for(int i=1;i<=1000000;i++)
  82.     {
  83.         int mi=oo,id=0;
  84.         for(int idd:mau[i])
  85.         {
  86.             if(mi>Dist(x[idd],y[idd],xThanh,yThanh))
  87.             {
  88.                 mi=Dist(x[idd],y[idd],xThanh,yThanh);
  89.                 id=idd;
  90.             }
  91.         }
  92.         if(mi!=oo)
  93.         {
  94.             BIT->Update(ThanhId[id],1);
  95.             miid[i]=id;
  96.         }
  97.     }
  98.     int dem=0;
  99.     for(int i=1;i<=q;i++)
  100.     {
  101.         while(cur<=n&&Kien[cur].fi<=Q[i].r1)
  102.         {
  103.             int id=ThanhId[Kien[cur].se];
  104.             if(!pass[z[Kien[cur].se]])
  105.             {
  106.                 dem++;
  107.                 BIT->Update(ThanhId[miid[z[Kien[cur].se]]],-1);
  108.                 pass[z[Kien[cur].se]]=true;
  109.             }
  110.             cur++;
  111.         }
  112.         int id=upper_bound(ThanhVal+1,ThanhVal+n+1,Q[i].r2)-ThanhVal-1;
  113.         kq[Q[i].id]=dem+BIT->Get(id);
  114.     }
  115.     for(int i=1;i<=q;i++)cout<<kq[i]<<'\n';
  116. }
  117. signed main()
  118. {
  119.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);home();
  120.     while(Test--)Tcmduc_VOI26();
  121.     return 0;
  122. }
Success #stdin #stdout 0.01s 28208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eBQ465
language:
C++14 (gcc 8.3)
created:
9 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!