fork download
copy 
  1. //Pranet Verma
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. int base,n,k,m,h[100001],b[100001],lt[100001],rt[100001];
  5. long long tot=0;
  6. struct Q
  7. {
  8.     int l,r,i;
  9.     bool operator <(const Q &o)const{return l/base==o.l/base?r<o.r:l/base<o.l/base;}
  10. }q[100001];
  11. int bit[100011];
  12. int read(int u)
  13. {
  14.     int ret=0;
  15.     while(u)
  16.         ret+=bit[u],u-=(u&-u);
  17.     return ret;
  18. }
  19. void update(int i,int u)
  20. {
  21.     while(i<100010)
  22.         bit[i]+=u,i+=(i&-i);
  23. }
  24. void add(int u)
  25. {
  26.     tot+=read(rt[u])-read(lt[u]-1);
  27.     update(h[u],1);
  28. }   
  29. void remove(int u)
  30. {   
  31.     update(h[u],-1);
  32.     tot-=read(rt[u])-read(lt[u]-1);
  33. }
  34. int L=0,R=-1;
  35. long long process(int l,int r)
  36. {
  37.     while(L>l)
  38.         add(--L);
  39.     while(L<l)
  40.         remove(L++);
  41.     while(R>r)
  42.         remove(R--);
  43.     while(R<r)
  44.         add(++R);
  45.     return tot;
  46. }
  47. long long ret[100001];
  48. int main()
  49. {
  50.     scanf("%d%d",&n,&k);
  51.     base=ceil(sqrt(n));
  52.     for(int i=0;i<n;++i)
  53.         scanf("%d",&h[i]),
  54.         b[i]=h[i];
  55.     sort(b,b+n);
  56.     for(int i=0;i<n;++i)
  57.         lt[i]=1+lower_bound(b,b+n,h[i]-k)-b,
  58.         rt[i]=1+upper_bound(b,b+n,h[i]+k)-b-1,
  59.         h[i]=1+lower_bound(b,b+n,h[i])-b;
  60.     scanf("%d",&m);
  61.     for(int i=0;i<m;++i)
  62.         scanf("%d%d",&q[i].l,&q[i].r),q[i].i=i;
  63.     sort(q,q+m);
  64.     for(int i=0;i<m;++i)
  65.         ret[q[i].i]=process(q[i].l,q[i].r);
  66.     for(int i=0;i<m;++i)
  67.         printf("%lld\n",ret[i]);
  68. }
Success #stdin #stdout 0s 7368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KB2xzc
language:
C++ (gcc 8.3)
created:
9 years 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!