zfCCFf - Online Java Compiler & Debugging Tool

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static int bs(int arr[],int target){
		int low = 0;
		int high = arr.length-1;
		int idx = arr.length;
		while(low<=high){
			int mid = low+(high-low)/2;
			if(target<=arr[mid]){
				high=mid-1;
				idx = mid;
			}else low = mid+1;
		}
		return idx;
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int q = sc.nextInt();

		int arr[] = new int[n];
		for(int i=0;i<n;i++) arr[i] = sc.nextInt();

		int targets[] = new int[q];
		for(int i=0;i<q;i++) targets[i] = sc.nextInt();

		Arrays.sort(arr);

		int preq[] = new int[n+1];
		for(int i=1;i<=n;i++){
			preq[i] = preq[i-1]+arr[i-1];
		}
		int totSum = preq[n];
		List<Integer>li = new ArrayList<>();
		for(int i=0;i<q;i++){
			int idx = bs(arr,targets[i]);
			int leftHalf = targets[i]*idx-preq[idx];
			int rightHalf = totSum-preq[idx]-targets[i]*(n-idx);
			li.add(leftHalf+rightHalf);
		}
		System.out.println(li);
	}
}