hi everyone :) i was working on #304 contest (PB D) and it seems like it doesn't work for cin and cout and u should use scanf and printf (which i really dont like to use ) finally even with them i couldn't get AC and can u tell me whats wrong with my code ? or if the algorithm is completely wrong ? thanks :) my code 11371801
can you explain briefly your algorithm?
my dynamic array res[] counts the number of prime factors in each number . then we count the sum of all them from b + 1, b + 2, ... , a
then i guess you should use prefix sum to get your queries in O(1) time
im sorry i dont know how to use prefix sum
just add a loop in which you do this operation res[i] +=res[i-1] then the query for [b,a] will just be the difference res[a]-res[b-1] (you can google it its easy to understand)
This for loop is executed in every test case ... There are 10^6 test cases per file and this loop is O(5*10^6) ... That makes a total of 10^12 which is impossible to run in time.
You can use prefix sum to avoid this.
yeah you are right, but i dont know how to do that. can explain a little more about prefix sum ?
You need to get the sum of a elements in an array 'A' in range from L to R.
Prefix sum can get you the answer in O(1) with O(n) pre-computation.
Make a new sum array 'S' where S[i] = A[0] + A[1] + ... + A[i];
Now to get sum(L, R) = S[R] — S[L — 1]