Need help with INSQ15_C

Problem link

My code

I am getting TLE. I tried to follow the approach in the editorial. I divided the array into two parts and found subsets of size less than equal to k. I stored them in vectors and sorted first vector based on number of elements in the subset. I used binary search to find required pairs in first and second vector.