For the Benefit of All (hard version)
All submissions for this problem are available.The only difference between the easy and hard versions is the contraints. In the new secret NASA, there are n astronauts. Professor Brand wants to form a team headed by Dr Mann for the Lazarus mission. Astronauts will team up in pairs for the mission. But there is one condition: two astronauts will team up with one another if and only if each person believes that the other person is good enough for him. An astronaut considers another good enough for him if and only if the other person has an astronaut rating of at least half of his own. The professor now wonders, how many pairs can be formed among the astronauts. Find the number of pairs possible. ###Input Format - The first line contains $T$, the number of test cases. - For each test case, the first line contains $n$, the number of astronauts. - The next line has $n$ integers, the ratings of the astronauts. ###Constraints - $1 \leq T \leq 10$ - $1 \leq n \leq10^5$ - $1 \leq a[i] \leq 10^9$ ###Output Format Output one line for each test case - the number of pairs possible among the astronauts. ###Sample Input 2 5 1 4 9 16 25 6 2 3 4 4 18 22 ###Sample Output 2 7
|Tags||binary-search, medium, shpc2019, shriram_c253, two-pointers|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.