HackerRank Almost Equal – Advanced problem solution

In this HackerRank Almost Equal – Advanced problem solution, we have given an array H[], where H[i] represents the height of the ith fighter, for a given l, r where 0 <= l <= r < N, can you count the number of pairs of fighters between l and r (both inclusive) who qualify to play a game?.

Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {

  static int nn;
  static int block;
  static int[] fenwick;
  static long cnt = 0;

  static class B implements Comparable<B> {
    int l;
    int r;
    int id;
    
    @Override
    public int compareTo(B o) {
      int i = l/block;
      int j = o.l/block;
      if (i != j) {
        return i - j;
      }
      if (r != o.r) {
        return r - o.r;
      }
      return l - o.l;
    }
  }
  
  static int getSum(int x) {
    int s = 0;
    for (; x != 0; x &= x-1)
      s += fenwick[x-1];
    return s;
  }

  static class Node {
    int l;
    int r;
    int h;

    public Node(int l, int r, int h) {
      this.l = l;
      this.r = r;
      this.h = h;
    }

    void remove() {
      add(h, -1);
      cnt -= getSum(r) - getSum(l);
    }

    void add() {
      cnt += getSum(r) - getSum(l);
      add(h, 1);
    }

    void add(int x, int v) {
      for (; x < nn; x |= x+1)
        fenwick[x] += v;
    }
  }

    
  static public int lowerBound(int[] arr, int len, int key) {
    if (key <= arr[0]) {
      return 0;
    }
    if (key > arr[len - 1]) {
      return 0;
    }
    
    int index = Arrays.binarySearch(arr, 0, len, key);
    if (index < 0) {
      index = - index - 1;
      if (index < 0) {
        return 0;
      }
    } 
    return index;
  }
  
  static public int upperBound(int[] arr, int len, int key) {
    int index = Arrays.binarySearch(arr, 0, len, key+1);
    if (index < 0) {
      index = - index - 1;
      if (index < 0 || index > len) {
        return 0;
      }
    }
    return index;
  }
  
  public static int unique(int[] arr) {
    if (arr.length == 1) return 1;
    int len = 1;
    while (len < arr.length && arr[len] != arr[len-1]) { 
      len++;
    }
    for (int i = len + 1; i < arr.length; i++) {
      if (arr[i] != arr[len - 1]) {
        len++;
        arr[len - 1] = arr[i];
      }
    }
    return len;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());

    st = new StringTokenizer(br.readLine());
    int[] a = new int[n];
    int[] c = new int[n];
    for (int i = 0; i < n; i++) {
      int item = Integer.parseInt(st.nextToken());
      c[i] = a[i] = item;
    }
    Arrays.sort(c);
    nn = unique(c);
    
    Node[] nodes = new Node[n];
    for (int i = 0; i < n; i++) {
      int l = lowerBound(c, nn, a[i]-k);
      int r = upperBound(c, nn, a[i]+k);
      int h = lowerBound(c, nn, a[i]);
      nodes[i] = new Node(l, r, h);
    }
    
    st = new StringTokenizer(br.readLine());
    int q = Integer.parseInt(st.nextToken());
    
    B[] b = new B[q];
    block = (int) Math.max(1.0, Math.sqrt((double)(n)*n/Math.max(1, q)));
    for (int i = 0; i < q; i++) {
      st = new StringTokenizer(br.readLine());
      b[i] = new B();
      b[i].id = i;
      b[i].l = Integer.parseInt(st.nextToken());
      b[i].r = Integer.parseInt(st.nextToken()) + 1;
    }
    Arrays.sort(b);
    int l = 0;
    int r = 0;
    fenwick = new int[n];
    long[] result = new long[q];
    for (int i = 0; i < q; i++) {
      while (l < b[i].l) {
        nodes[l++].remove();
      }
      while (b[i].l < l) {
        nodes[--l].add();
      }
      while (b[i].r < r) {
        nodes[--r].remove();
      }
      while (r < b[i].r) {
        nodes[r++].add();
      }
      result[b[i].id] = cnt;
    }

    for (int i = 0; i < result.length; i++) {
      bw.write(String.valueOf(result[i]));

      if (i != result.length - 1) {
        bw.write("n");
      }
    }

    bw.newLine();

    bw.close();
    br.close();
  }
}

Problem solution in C++ programming.

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <utility>
#define rep(i, s, n) for(int i=int(s); i<=int(n); ++i)
#define rf freopen("in.in", "r", stdin)
#define wf freopen("out.out", "w", stdout)
using namespace std;
#define mp make_pair
#define ll long long
const int mx=1e5+10;

#define gc getchar_unlocked
void scan(int &x)
{
    register int c = gc();
    x = 0;
    for(;(c<48 || c>57);c = gc());
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}

static ll b2d[410][410], b1d[mx][410];
static int h[mx], szb[410], lb[410], rb[410];
pair<int, int> bb[410], *buck[410];
int n, k, q, sqr;

inline void cum2d()
{
    rep(i, 1, 409) rep(j, 1, 409)
        b2d[i][j] += b2d[i-1][j]+b2d[i][j-1]-b2d[i-1][j-1];
}
inline void cum1d()
{
    rep(i, 0, n) rep(j, 1, 409)
        b1d[i][j] += b1d[i][j-1];
}

inline ll inonev(int* v, int sz)
{
    if(sz<=0) return 0;

    ll ret = 0; int up=0;
    rep(i, 0, sz-1)
    {
        while(v[up] <= v[i]+k and up<sz) up++;
        ret += up-(i+1);
    }
    return ret;
}
inline ll intwov(int* v1, int sz1, int* v2, int sz2)
{
    if(sz1<=0 or sz2<=0) return 0;

    ll ret=0; int low=0, up=0;
    rep(i, 0, sz1-1)
    {
        while(v2[low] < v1[i]-k and low<sz2) low++;
        while(v2[up] <= v1[i]+k and up<sz2) up++;
        ret += up-low;
    }
    return ret;
}

void process()
{
    for(int i=0; i*sqr<n; ++i)
    {
        int s=i*sqr, e=min(n-1, s+sqr-1);
        buck[i+1]=new pair<int, int>[e-s+1]; szb[i+1]=e-s+1;
        
        rep(j, s, e)
            buck[i+1][j-s] = mp(h[j], j),
            lb[j-s] = h[j];
        sort(lb, lb+szb[i+1]);
        sort(buck[i+1], buck[i+1]+szb[i+1]);

        ll val=inonev(lb, szb[i+1]);
        b2d[i+1][i+1] += val;

        rep(j, 1, i)
        {
            val=0; int up=0, low=0;
            rep(l, 0, szb[i+1]-1)
            {
                while(buck[j][low].first < buck[i+1][l].first-k and low<szb[j]) low++;
                while(buck[j][up].first <= buck[i+1][l].first+k and up<szb[j]) up++;
                b1d[buck[i+1][l].second][j] += up-low; val += up-low;
            }
            b2d[j][i+1]+=val;
        }
    }

    for(int i=0; i*sqr<=n; ++i)
    {
        for(int j=i+2; szb[j]; ++j)
        {
            int up=0, low=0;
            rep(l, 0, szb[i+1]-1)
            {
                while(buck[j][low].first < buck[i+1][l].first-k and low<szb[j]) low++;
                while(buck[j][up].first <= buck[i+1][l].first+k and up<szb[j]) up++;
                b1d[buck[i+1][l].second][j] += up-low;
            }
        }
    }
}

int main()
{
    //rf; wf;
    scan(n); scan(k); sqr=sqrt(n);
    rep(i, 0, n-1)
        scan(h[i]);
    
    process();
    cum1d();
    cum2d();

    scanf("%d", &q);
    while(q--)
    {
        int l, r;
        scan(l); scan(r);
        ll ans=0;

        int sqrl=l/sqr, sqrr=r/sqr, szl=0, szr=0; sqrl++;

        rep(i, 0, szb[sqrl]-1)
            if(buck[sqrl][i].second>=l and buck[sqrl][i].second<=r)
                lb[szl++]=buck[sqrl][i].first;
        rep(i, 0, szb[sqrr+1]-1)
            if(buck[sqrr+1][i].second>=l and buck[sqrr+1][i].second<=r)
                rb[szr++]=buck[sqrr+1][i].first;

        ans+=inonev(lb, szl); 
        if(sqrr+1==sqrl) {printf("%lldn", ans); continue;}
        ans+=inonev(rb, szr);

        ans += intwov(lb, szl, rb, szr);
        ans += b2d[sqrr][sqrr]-b2d[sqrr][sqrl]-b2d[sqrl][sqrr]+b2d[sqrl][sqrl];

        rep(i, l, sqr*sqrl-1)
            ans += b1d[i][sqrr]-b1d[i][sqrl];
        rep(i, sqr*sqrr, r)
            ans += b1d[i][sqrr]-b1d[i][sqrl];

        printf("%lldn", ans);
    }
    return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void QQ(int x,int y);
void add(int X);
void removee(int X);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size);
void sort_a3(int*a,int*b,int*c,int size);
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size);
int read(int idx);
void update(int idx,int val,int MaxVal);
int H[300000],rH[300000],q[2][100000],qq[2][100000],idx[300000],tree[300001],NN,cl,cr;
long long ans[100000],x;

int main(){
  int K,Q,i,j;
  scanf("%d%d",&NN,&K);
  for(i=0;i<NN;i++){
    scanf("%d",&H[3*i]);
    H[3*i+1]=H[3*i]-K;
    H[3*i+2]=H[3*i]+K;
    idx[3*i]=3*i;
    idx[3*i+1]=3*i+1;
    idx[3*i+2]=3*i+2;
  }
  sort_a2(H,idx,3*NN);
  for(i=j=0;i<3*NN;i++){
    if(i && H[i]!=H[i-1])
      j++;
    rH[idx[i]]=j;
  }
  scanf("%d",&Q);
  for(i=0;i<Q;i++){
    scanf("%d%d",&q[0][i],&q[1][i]);
    q[1][i]++;
  }
  for(i=0,j=(int)sqrt(NN);i<Q;i++){
    qq[0][i]=q[0][i]/j;
    qq[1][i]=q[1][i];
    idx[i]=i;
  }
  sort_a3(&qq[0][0],&qq[1][0],idx,Q);
  for(i=cl=cr=0,x=0;i<Q;i++){
    QQ(q[0][idx[i]],q[1][idx[i]]);
    ans[idx[i]]=x;
  }
  for(i=0;i<Q;i++)
    printf("%lldn",ans[i]);
  return 0;
}
void QQ(int x,int y){
  while(cl<x)
    removee(cl++);
  while(cl>x)
    add(--cl);
  while(cr<y)
    add(cr++);
  while(cr>y)
    removee(--cr);
  return;
}
void add(int X){
  int y=read(rH[3*X+2]+1);
  if(rH[3*X+1])
    y-=read(rH[3*X+1]);
  x+=y;
  update(rH[3*X]+1,1,3*NN);
  return;
}
void removee(int X){
  int y=read(rH[3*X+2]+1);
  if(rH[3*X+1])
    y-=read(rH[3*X+1]);
  x-=y-1;
  update(rH[3*X]+1,-1,3*NN);
  return;
}
void sort_a2(int*a,int*b,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int*left_a,*left_b,*right_a,*right_b;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_b[i]=b[i+m];
  }
  sort_a2(left_a,left_b,m);
  sort_a2(right_a,right_b,size-m);
  merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    }
  }
  return;
}
void sort_a3(int*a,int*b,int*c,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  left_c=(int*)malloc(m*sizeof(int));
  right_c=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
    left_c[i]=c[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_b[i]=b[i+m];
    right_c[i]=c[i+m];
  }
  sort_a3(left_a,left_b,left_c,m);
  sort_a3(right_a,right_b,right_c,size-m);
  merge3(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  free(left_c);
  free(right_c);
  return;
}
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      c[i+j] = right_c[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      c[i+j] = left_c[i];
      i++;
    } else if (left_a[i] == right_a[j]) {
      if(left_b[i]<=right_b[j]){
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      c[i+j] = left_c[i];
      i++;
      }
      else{
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      c[i+j] = right_c[j];
      j++;
      }
    } else if (left_a[i] < right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      c[i+j] = left_c[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      c[i+j] = right_c[j];
      j++;
    }
  }
  return;
}
int read(int idx){
  int sum = 0;
  while(idx>0){
    sum+=tree[idx];
    idx-=(idx&-idx);
  }
  return sum;
}
void update(int idx,int val,int MaxVal){
  while(idx<=MaxVal){
    tree[idx]+=val;
    idx+=(idx&-idx);
  }
  return;
}