Ganesh1648

Count Pairs

Aug 8th, 2020 (edited)
155
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.62 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3. import java.math.*;
  4.  
  5. /* Name of the class has to be "Main" only if the class is public. */
  6. class Codechef {
  7.   static int n;
  8.   static long k;
  9.   static Long a[];
  10.   static StringBuilder str = new StringBuilder("");
  11.    
  12.    
  13.     static void solve()
  14.     {
  15.         Arrays.sort(a);
  16.         int ans=0;
  17.         for(int i=0;i<n;i++)
  18.         {
  19.             int l,r;
  20.             long high=a[i]+k;
  21.             long low=a[i]-k;
  22.             int hi=-1,li=-1;
  23.            
  24.             l=i+1;r=n-1;
  25.             while(l<=r)
  26.             {
  27.                 int mid=l+(r-l)/2;
  28.                 if(a[mid]<=high)
  29.                 {
  30.                     hi=mid;
  31.                     l=mid+1;
  32.                 }
  33.                 else
  34.                     r=mid-1;
  35.             }
  36.            
  37.             l=0;r=i-1;
  38.             while(l<=r)
  39.             {
  40.                 int mid=l+(r-l)/2;
  41.                 if(a[mid]>=low)
  42.                 {
  43.                     li=mid;
  44.                     r=mid-1;
  45.                 }
  46.                 else
  47.                     l=mid+1;
  48.             }
  49.            
  50.             if(li!=-1 || hi!=-1)
  51.                ans++;
  52.         }
  53.         System.out.println(ans);
  54.     }
  55.  
  56.   public static void main(String[] args) throws java.lang.Exception {
  57.     BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  58.     String s[]=bf.readLine().trim().split("\\s+");
  59.     n=Integer.parseInt(s[0]);
  60.     k=Long.parseLong(s[1]);
  61.     s=bf.readLine().trim().split("\\s+");
  62.     a=new Long[n];
  63.     for(int i=0;i<n;i++)
  64.         a[i]=Long.parseLong(s[i]);
  65.     solve();
  66.   }
  67. }
Advertisement
Add Comment
Please, Sign In to add comment