fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define ff(i,a,b) for(auto i=(a); i<=(b); ++i)
  7. #define ss " "
  8. #define pb emplace_back
  9. #define sz(v) (int)(v).size()
  10. #define all(v) (v).begin(), (v).end()
  11. typedef long long ll;
  12. const int maxn1=2e5+5;
  13.  
  14. struct HS{int x,r,ts;} a[maxn1];
  15. struct Interval{int l,x,r;} b[maxn1];
  16.  
  17. vector<int> groupIdx[maxn1];     // chỉ số theo nhóm ts
  18. ll cntGrp[maxn1][55];            // cnt[i][d] giữa nhóm i và i+d (d<=50)
  19. vector<int> xsComp, tsComp;
  20.  
  21. struct BIT{
  22.     int N; vector<int> t;
  23.     BIT() {}
  24.     BIT(int n){ init(n); }
  25.     void init(int n){ N=n; t.assign(N+2,0); }
  26.     void add(int i,int v){ for(; i<=N; i+=i&-i) t[i]+=v; }
  27.     int sum(int i){ int s=0; for(; i>0; i-=i&-i) s+=t[i]; return s; }
  28.     int range(int l,int r){ if(l>r) return 0; return sum(r)-sum(l-1); }
  29. };
  30.  
  31. void compress(int n){
  32.     vector<int> v;
  33.     for(int i=1;i<=n;i++) v.pb(b[i].l), v.pb(b[i].x), v.pb(b[i].r);
  34.     sort(all(v)); v.erase(unique(all(v)), v.end());
  35.     xsComp=v;
  36.     for(int i=1;i<=n;i++){
  37.         b[i].l = upper_bound(all(v), b[i].l)-v.begin();
  38.         b[i].x = upper_bound(all(v), b[i].x)-v.begin();
  39.         b[i].r = upper_bound(all(v), b[i].r)-v.begin();
  40.     }
  41.     v.clear();
  42.     for(int i=1;i<=n;i++) v.pb(a[i].ts);
  43.     sort(all(v)); v.erase(unique(all(v)), v.end());
  44.     tsComp=v;
  45.     for(int i=1;i<=n;i++)
  46.         a[i].ts = upper_bound(all(v), a[i].ts)-v.begin();
  47. }
  48.  
  49. int main(){
  50.     ios::sync_with_stdio(false);
  51.     cin.tie(nullptr);
  52.  
  53.     int sub; if(!(cin>>sub)) return 0;
  54.     int n,q; cin>>n>>q;
  55.     for(int i=1;i<=n;i++){
  56.         int x,r,ts; cin>>x>>r>>ts;
  57.         a[i]={x,r,ts};
  58.         b[i]={x-r,x,x+r};
  59.     }
  60.     compress(n);
  61.  
  62.     int S = sz(tsComp);
  63.     for(int i=1;i<=n;i++) groupIdx[a[i].ts].pb(i);
  64.  
  65.     // Pre-build mỗi nhóm: danh sách index sort theo l, r, x
  66.     vector<vector<int>> byL(S+1), byR(S+1), byX(S+1);
  67.     for(int g=1; g<=S; g++){
  68.         auto &vec = groupIdx[g];
  69.         byL[g]=vec; byR[g]=vec; byX[g]=vec;
  70.         sort(all(byL[g]), [&](int i,int j){ return b[i].l < b[j].l; });
  71.         sort(all(byR[g]), [&](int i,int j){ return b[i].r < b[j].r; });
  72.         sort(all(byX[g]), [&](int i,int j){ return b[i].x < b[j].x; });
  73.     }
  74.  
  75.     // Fenwick theo x đã nén
  76.     const int XN = sz(xsComp)+2;
  77.     const int D = 50;
  78.  
  79.     // Tính cnt[g][d] cho mọi d ≤ 50 bằng quét hợp hai nhóm
  80.     for(int d=0; d<=D; d++){
  81.         for(int g=1; g<=S; g++){
  82.             int h = g + d;
  83.             if(h>S) break;
  84.             if(groupIdx[g].empty() || groupIdx[h].empty()){
  85.                 cntGrp[g][d]=0; continue;
  86.             }
  87.  
  88.             // merged theo x
  89.             vector<pair<int,int>> merged; // (x, +id) id>0 thuộc h; id<0 thuộc g
  90.             merged.reserve(groupIdx[g].size()+groupIdx[h].size());
  91.             for(int i: byX[g]) merged.pb(b[i].x, -i);
  92.             for(int j: byX[h]) merged.pb(b[j].x, +j);
  93.             sort(all(merged));
  94.  
  95.             // Active set cho mỗi nhóm bằng 2 BIT theo x_i
  96.             BIT bitA(XN), bitB(XN);
  97.             int pLg=0, pRg=0, pLh=0, pRh=0;
  98.             const auto &GL=byL[g], &GR=byR[g];
  99.             const auto &HL=byL[h], &HR=byR[h];
  100.  
  101.             long long pairs=0;
  102.  
  103.             for(auto [xcur, tag] : merged){
  104.                 // cập nhật active theo xcur cho cả 2 nhóm
  105.                 while(pLg<sz(GL) && b[GL[pLg]].l<=xcur){
  106.                     bitA.add(b[GL[pLg]].x, +1); pLg++;
  107.                 }
  108.                 while(pRg<sz(GR) && b[GR[pRg]].r < xcur){
  109.                     bitA.add(b[GR[pRg]].x, -1); pRg++;
  110.                 }
  111.                 while(pLh<sz(HL) && b[HL[pLh]].l<=xcur){
  112.                     bitB.add(b[HL[pLh]].x, +1); pLh++;
  113.                 }
  114.                 while(pRh<sz(HR) && b[HR[pRh]].r < xcur){
  115.                     bitB.add(b[HR[pRh]].x, -1); pRh++;
  116.                 }
  117.  
  118.                 if(tag>0){ // phần tử thuộc nhóm h, ghép với active của g
  119.                     int j = tag;
  120.                     int lj = b[j].l;
  121.                     pairs += bitA.range(lj, b[j].x);
  122.                 }else{     // thuộc nhóm g, ghép với active của h
  123.                     int i = -tag;
  124.                     int li = b[i].l;
  125.                     if(g==h){
  126.                         // cùng nhóm: đang active của chính nhóm -> trừ bản thân
  127.                         pairs += bitB.range(li, b[i].x) - 1;
  128.                     }else{
  129.                         pairs += bitB.range(li, b[i].x);
  130.                     }
  131.                 }
  132.             }
  133.             cntGrp[g][d]=pairs;
  134.         }
  135.     }
  136.  
  137.     // Trả lời truy vấn
  138.     while(q--){
  139.         int Lval, Rval; cin>>Lval>>Rval;
  140.         // map sang chỉ số nén của ts
  141.         int L=-1, R=-1;
  142.         // lower_bound ≥ Lval
  143.         int l=1,r=sz(tsComp);
  144.         while(l<=r){ int m=(l+r)>>1; if(tsComp[m-1]>=Lval){ L=m; r=m-1;} else l=m+1; }
  145.         if(L==-1){ cout<<0<<ss; continue; }
  146.         // upper_bound ≤ Rval
  147.         l=1; r=sz(tsComp);
  148.         while(l<=r){ int m=(l+r)>>1; if(tsComp[m-1]<=Rval){ R=m; l=m+1;} else r=m-1; }
  149.         if(R==-1){ cout<<0<<ss; continue; }
  150.  
  151.         long long ans=0;
  152.         for(int i=L;i<=R;i++){
  153.             int rem = min(50, R - i);
  154.             for(int dlt=0; dlt<=rem; ++dlt) ans += cntGrp[i][dlt];
  155.         }
  156.         cout<<ans<<ss;
  157.     }
  158.     return 0;
  159. }
  160.  
Success #stdin #stdout 0.01s 11796KB
comments (?)
stdin
copy 
1
5 2
1 1 2
2 1 2
3 1 7
4 1 9
5 1 7
2 2
7 9
stdout
copy 
4 5
https://ideone.com/g5FrsX
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!