PRMQ JUNE17 how do I optimize my solution for this problem

general
,
1

My approach was simple just to sieve out all numbers 2 to 10^6 and keeping the lowest prime factor ,then I can get the sum of powers of primes in range X and Y for that particular number.
my code was: https://www.codechef.com/viewsolution/14162128

but it runs in O(QN(logN)) getting only 30 points. I tried to solve it using segment tree but seeing 4 variables (2 different ranges namely X to Y and L to R) I skipped that.Help! Plz.

2

You might want to use segment tree here, four variables don’t change much, follow thread.

3

You can solve it without using segment trees by maintaining a cumulative sum:

  1. Since X and Y can be a maximum of 10^6, we seive till 10^6 to mark the prime numbers.
  2. Prime factorize every number and store it contigiously in an array, while keeping the index of start of each number in another array.
  3. Divide the entire array into root(n) blocks each of (n) elements.
  4. For each block, calculate the number of each primes (1 to 10^6) and store it as sum in a 2D array with row denoting the block number and columns denoting each prime (2,3,5…)
  5. For every input L R X Y, find the first prime after X and the last prime before Y.
  6. Find the number of blocks that completely lie inside L and R.
  7. Use the following to determine the number of primes between X and Y in the range Block after L to block before R by using the 2D array generated earlier.
  8. For the elements before the first block and after the last block, just iterate through the prime factorization and increment ans if prime is between X and Y (at max root(n) operations.

Here is the link to my solution:
https://www.codechef.com/viewsolution/14155947

4

You can use Segment Tree where each node is itself a vector storing prime factors of the given element.Then keep on merging the prime factors as you go up in tree. After you are done by making segment tree. You can ask the query in logn*logn time.

You can check the code it is pretty simple :- https://www.codechef.com/viewsolution/14188250

5

Quick and easy segment trees : http://codeforces.com/blog/entry/18051

My code: https://www.codechef.com/viewsolution/14060497

6

@abdullah768, my exactly the same solution in java gets TLE. https://www.codechef.com/viewsolution/14242176