Can only think of brute force :<

Try binary search.

explain your solution a bit.

I couldnâ€™t solve it, although you can find some explanation here:

https://codeforces.com/blog/entry/73950?#comment-581179

i just saw this damn

both D and E were tough man XD

Ok , this is double binary search .

Iâ€™ll first explain the easier version of this problem , which will help you in understanding the original problemâ€™s solution .

Sort the input-array.

Lets define x,y,z as number of pairs with negative value , zero value , positive-value.

You can calculate these without any effort

Say , the given array is fully positive :- [1,2,4,5,6,7,8,9,11,12,13,14]

And the question is to find the number of pairs whose product is less than 77 .

We can do it in O(N.logN) using binary search .

Step-1 : We are at index-'1' and a[1]=1 . Mid-value[j]=8 , product =a[1].a[7]=8 , this is less than 77, so we increase the mid-value in binary search till we get a[1].a[j]>77

We realize all 11 pairs((a[1],a[2]),(a[1],a[3]).......) have product less than 77.

In this step, we did binary search in the range [2,12]

So, ans=ans+11

Step-2 :- Now, we are at index-'2' and a[2]=2 (Now, we will binary search in the range [3,12]) . Repeat the same process we did at step-1.

Step-3 :- Now, we are at index-'3' and a[3]=4 (Now, we will binary search in the range [4,12]) . Repeat the same process we did at step-1.

Step-4 :- And so onâ€¦till you reach index 'n' .

And ans has the count of all products with values less than 77.

Now, we can solve the harder version of this problem using double binary-search .

(Will add its explanation-soon)

Are u still solving the question for negative part??