First please enclose your code in triple``` ticks like this
This is a sample code
Also descibe the problem weatrher you are getting WA or TLE…
Second thing that your code will not pass the time constraints bro you have used one loop inside the another 1sec = 10^8 operations. O(NQ) will be 10^10…
1≤N,Q≤2⋅105 |ai|≤109
for each valid i* a1,a2,…,aN
are pairwise distinct
|xi|≤109
for each valid i
So optimise your code .
If you use Binary search then time comlexity will be O(Qlog(N)) which will pass the tiem constarints.
Hint you can use binary search for finding the index/no of elements greater or smaller than it if the elements in array are distinct using binary search.
Idea :(x-x1)(x-x2)…polynomial
Now we know that x-x1>0 if x>x1 so if we find the no elements in ary greater than qi (Each query ) we know that it will contribute to -ve value …count them using binary search …
Link :to my code CodeChef: Practical coding for everyone
I used binary but got TLEcan you please help me with the code attached. I used the binary approach in which I first search whether num is in the array or not then found the index of the number in the array then used the fact that alternative roots are pos and neg code is here Help is highly appreciated
Same happened to me also .I did write binary search myself and got tle. Changed the same to lower_bound (Which uses binary search BTW) then my solution got accepted. I will attach my submissions link. It wasted my time, I was so close on solving 3rd question but no time due to this issue.
But the time complexity is still O((n+q)logn) so why TLE I mean I did call by referrence now but why I was getting TLE before. Can you please explain @ssjgz
}
}
2 for loops ,one nested inside other …
O(Q*N) = 10^10 operations …(worst case )
In 1 sec only 10^8 is allowed ,optimise your code buddy .
Use binary search …