I have written the code to solve 1609C - Complex Market Analysis problem, but it gives TLE. I think the complexity of my soln. is O(n*log(log(n) because of Seive rest of the work i have done in linear time. My approach is as follows:
Suppose arr[i] is prime I have calculated the number of chains of 1 on left of arr[i] and similarly on right of arr[i]. Then i have used sum+=onesLeft[i]+onesRight[i]+onesLeft[i]*onesRight[i]; to get the answer.
Here is my submission ----> https://codeforces.com/contest/1609/submission/160055418. Please tell where I am wrong in calculating the time complexity? Thanks in advance.
You are doing sieve for each test case, which is wasteful.
Thankyou algoishard
To expand the previous comment: you can execute isPrime(1e6) line in a main() function before the for loop, because the parameters will never change. Hence, you will you will have no need to execute it every time in a solve() function and your code will be succesfully AC.