fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define file "o"
  5. #define ff(i,a,b) for(auto i=(a); i<=(b); ++i)
  6. #define ffr(i,b,a) for(auto i=(b); i>=(a); --i)
  7. #define ss " "
  8. #define pb emplace_back
  9. #define sz(s) (int)(s).size()
  10. #define all(s) (s).begin(), (s).end()
  11. #define cn continue
  12. #define re exit(0)
  13.  
  14. using ll = long long;
  15. using vi = vector<int>;
  16.  
  17. const int maxn1 = 200000 + 5;
  18.  
  19. struct HS{int x,r,ts;} a[maxn1];
  20. struct B{ll l,x,r;} b[maxn1];
  21.  
  22. inline void rf(){
  23.     ios::sync_with_stdio(false);
  24.     cin.tie(nullptr); cout.tie(nullptr);
  25.     if(fopen(file".inp","r")){
  26.         freopen(file".inp","r",stdin);
  27.         freopen(file".out","w",stdout);
  28.     }
  29. }
  30.  
  31. struct BIT{
  32.     int n=0;
  33.     vector<int> t,used;
  34.     inline void reset(int _n){
  35.         n=_n;
  36.         if(sz(t)<n+1) t.assign(n+1,0);
  37.         used.clear();
  38.     }
  39.     inline void add(int x,int v){
  40.         for(; x<=n; x+=x&-x){
  41.             if(t[x]==0) used.pb(x);
  42.             t[x]+=v;
  43.         }
  44.     }
  45.     inline int sum(int x) const{
  46.         int s=0; for(; x>0; x-=x&-x) s+=t[x]; return s;
  47.     }
  48.     inline int range(int l,int r) const{
  49.         if(r<=0||l>r) return 0;
  50.         if(l<=1) return sum(r);
  51.         return sum(r)-sum(l-1);
  52.     }
  53.     inline void clear_used(){
  54.         for(int i:used) t[i]=0;
  55.         used.clear();
  56.     }
  57. };
  58.  
  59. int n,q;
  60. vector<vi> g;
  61. vector<vector<ll>> coords;
  62. vector<int> posL,posX,posR;
  63. vector<int> tmp2;
  64. vector<array<ll,51>> cntPref;
  65.  
  66. inline int getPos(const vector<ll>& v, ll val){
  67.     return (int)(upper_bound(all(v), val)-v.begin());
  68. }
  69. inline bool cmpIdxByRadius(int i,int j){ return a[i].r>a[j].r; }
  70.  
  71. ll calGroup(int tRank){
  72.     static BIT bit;
  73.     const auto &vec = g[tRank];
  74.     bit.reset(sz(coords[tRank]));
  75.     ll ans=0;
  76.     for(int idx:vec){
  77.         ans += bit.range(posL[idx], posR[idx]);
  78.         bit.add(posX[idx],1);
  79.     }
  80.     bit.clear_used();
  81.     return ans;
  82. }
  83.  
  84. ll cal2(int i,int j){
  85.     static BIT bi,bj;
  86.     const auto &gi=g[i], &gj=g[j];
  87.     bi.reset(sz(coords[i]));
  88.     bj.reset(sz(coords[j]));
  89.     ll ans=0;
  90.     int p1=0,p2=0;
  91.     while(p1<sz(gi) && p2<sz(gj)){
  92.         int u=gi[p1], v=gj[p2];
  93.         if(a[u].r>a[v].r){
  94.             int li_i=posL[u], ri_i=posR[u];
  95.             int li_j=getPos(coords[j], b[u].l);
  96.             int ri_j=getPos(coords[j], b[u].r);
  97.             ans += bi.range(li_i,ri_i) + bj.range(li_j,ri_j);
  98.             bi.add(posX[u],1);
  99.             ++p1;
  100.         }else{
  101.             int lj_j=posL[v], rj_j=posR[v];
  102.             int lj_i=getPos(coords[i], b[v].l);
  103.             int rj_i=getPos(coords[i], b[v].r);
  104.             ans += bj.range(lj_j,rj_j) + bi.range(lj_i,rj_i);
  105.             bj.add(posX[v],1);
  106.             ++p2;
  107.         }
  108.     }
  109.     while(p1<sz(gi)){
  110.         int u=gi[p1++];
  111.         int li_i=posL[u], ri_i=posR[u];
  112.         int li_j=getPos(coords[j], b[u].l);
  113.         int ri_j=getPos(coords[j], b[u].r);
  114.         ans += bi.range(li_i,ri_i) + bj.range(li_j,ri_j);
  115.         bi.add(posX[u],1);
  116.     }
  117.     while(p2<sz(gj)){
  118.         int v=gj[p2++];
  119.         int lj_j=posL[v], rj_j=posR[v];
  120.         int lj_i=getPos(coords[i], b[v].l);
  121.         int rj_i=getPos(coords[i], b[v].r);
  122.         ans += bj.range(lj_j,rj_j) + bi.range(lj_i,rj_i);
  123.         bj.add(posX[v],1);
  124.     }
  125.     bi.clear_used();
  126.     bj.clear_used();
  127.     return ans;
  128. }
  129.  
  130. int main(){
  131.     rf();
  132.     int sub; if(!(cin>>sub)) return 0;
  133.     cin>>n>>q;
  134.     ff(i,1,n){
  135.         int x,r,ts; cin>>x>>r>>ts;
  136.         a[i]={x,r,ts};
  137.         b[i]={ (ll)x-r, (ll)x, (ll)x+r };
  138.     }
  139.     {
  140.         vector<int> vts; vts.reserve(n);
  141.         ff(i,1,n) vts.pb(a[i].ts);
  142.         sort(all(vts)); vts.erase(unique(all(vts)), vts.end());
  143.         tmp2=vts;
  144.         ff(i,1,n) a[i].ts=(int)(upper_bound(all(vts), a[i].ts)-vts.begin());
  145.     }
  146.     int T=sz(tmp2);
  147.     g.assign(T+2,{});
  148.     coords.assign(T+2,{});
  149.     posL.assign(n+5,0);
  150.     posX.assign(n+5,0);
  151.     posR.assign(n+5,0);
  152.     ff(i,1,n) g[a[i].ts].pb(i);
  153.     ff(t,1,T){
  154.         auto &vec=g[t];
  155.         if(vec.empty()) cn;
  156.         static vector<ll> pool;
  157.         pool.clear(); pool.reserve(3*sz(vec));
  158.         for(int idx:vec){ pool.pb(b[idx].l); pool.pb(b[idx].x); pool.pb(b[idx].r); }
  159.         sort(all(pool)); pool.erase(unique(all(pool)), pool.end());
  160.         coords[t]=pool;
  161.         for(int idx:vec){
  162.             posL[idx]=getPos(coords[t], b[idx].l);
  163.             posX[idx]=getPos(coords[t], b[idx].x);
  164.             posR[idx]=getPos(coords[t], b[idx].r);
  165.         }
  166.     }
  167.     ff(t,1,T) sort(all(g[t]), cmpIdxByRadius);
  168.     const int K=50;
  169.     cntPref.assign(T+2,{});
  170.     ff(i,1,T) cntPref[i][0]=calGroup(i);
  171.     ff(i,1,T){
  172.         for(int j=i+1; j<=min(T,i+K); ++j){
  173.             ll cross=cal2(i,j)-cntPref[i][0]-cntPref[j][0];
  174.             int d=j-i;
  175.             cntPref[i][d]=cntPref[i][d-1]+cross;
  176.         }
  177.     }
  178.     while(q--){
  179.         int mn,mx; cin>>mn>>mx;
  180.         int L=(int)(lower_bound(all(tmp2), mn)-tmp2.begin())+1;
  181.         int R=(int)(upper_bound(all(tmp2), mx)-tmp2.begin());
  182.         if(L>R||L<1||R<1||L>T||R>T){ cout<<0<<ss; cn; }
  183.         ll ans=0;
  184.         for(int i=L;i<=R;++i){
  185.             int d=R-i; if(d>K) d=K;
  186.             ans+=cntPref[i][d];
  187.         }
  188.         cout<<ans<<ss;
  189.     }
  190.     re;
  191. }
  192.  
Success #stdin #stdout 0.01s 5676KB
comments (?)
stdin
copy 
1
5 3
2 22071997 1
2 22071997 2
7 22071997 3
9 22071997 4
7 22071997 5
1 3
2 5
1 5
stdout
copy 
3 6 10
https://ideone.com/qi63D5
language:
C++14 (gcc 8.3)
created:
5 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!