Problem link
Formally, the condition for the legend being true reads
min(|x−y|,|x+y|)≤|x|,|y|≤max(|x−y|,|x+y|)
Now, it is possible to characterize when this condition happens through casework on the signs and sizes of x and y, but this can be tricky to do right. However, there is a neat trick that allows us to solve the problem without any casework. What happens if we change x into −x? The values of |x| and |y| stay the same, while |x−y| and |x+y| will swap values. This means that the pair {x,y} works if and only if {−x,y} works. Similarly, we can switch the sign of y. This means that we can replace x and y by their absolute values, and the original pair works if and only if the new one works.
If x≥0 and y≥0 then the condition becomes |x−y|≤x,y≤x+y. The upper bound obviously always holds, while the lower bound is equivalent by some simple algebra to
x≤2y and y≤2x
So the problem reduces to counting the number of pairs {x,y} with |x|≤2|y| and |y|≤2|x|. To solve this we now take the absolute values of all the ai and sort them into an array b1≤b2≤⋯≤bn. The answer to the problem is the number of pairs (l,r) with l<r and br≤2bl. For each fixed l we calculate the largest r that satisfies this condition, and just add r−l to the answer, as the values l+1,l+2,…,r are all the ones that work for this l. We can either do a binary search for the best r at each l, or calculate the optimal r's for all of the l's in O(n) using two pointers. Either way, our final complexity is O(nlogn) as this is the time required to sort the array.
Complexity: O(nlogn)
Formally, the condition for the legend being true reads
min(|x−y|,|x+y|)≤|x|,|y|≤max(|x−y|,|x+y|)
Now, it is possible to characterize when this condition happens through casework on the signs and sizes of x and y, but this can be tricky to do right. However, there is a neat trick that allows us to solve the problem without any casework. What happens if we change x into −x? The values of |x| and |y| stay the same, while |x−y| and |x+y| will swap values. This means that the pair {x,y} works if and only if {−x,y} works. Similarly, we can switch the sign of y. This means that we can replace x and y by their absolute values, and the original pair works if and only if the new one works.
If x≥0 and y≥0 then the condition becomes |x−y|≤x,y≤x+y. The upper bound obviously always holds, while the lower bound is equivalent by some simple algebra to
x≤2y and y≤2x
So the problem reduces to counting the number of pairs {x,y} with |x|≤2|y| and |y|≤2|x|. To solve this we now take the absolute values of all the ai and sort them into an array b1≤b2≤⋯≤bn. The answer to the problem is the number of pairs (l,r) with l<r and br≤2bl. For each fixed l we calculate the largest r that satisfies this condition, and just add r−l to the answer, as the values l+1,l+2,…,r are all the ones that work for this l. We can either do a binary search for the best r at each l, or calculate the optimal r's for all of the l's in O(n) using two pointers. Either way, our final complexity is O(nlogn) as this is the time required to sort the array.
Complexity: O(nlogn)
A solution in c++
){kind=link}
0 Comments
If you have any doubts, Please let me know