How can I make this program faster — K Interesting Pairs ?

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

I have tried to solve the problem of finding k-interesting pairs [here].(http://codeforces.net/contest/769/submission/26220768)

My solution is quadratic O(n^2). If it is run on the sequence of numbers given, then n = 10^5 at most. I have followed the trick of the editorial and built an array of the frequencies of each element. This happens in O(n) time, with n = 10^5, at most

And have then applied the quadratic time algorithm on the frequency array so now n = 10^4. However, this isn't enough to get past the time limit.

What are further optimizations I can perform ?

Edit — I have performed some optimizations and managed to get an acceptance. Please tell me how I can make this faster ? I am not able to understand the algorithm some other people who got faster solution used. Some stored only those values of x, for which Population Count[x] is k and then did something I am unable to understand. For example, programs like this one.

Here's my code. Please help me.

Also, one more question — The same program seems to be performing at 78 ms here and at 93 ms here. What is the reason for the difference ? This may help me understand and speeden things up.