Help in D. Powerful array

general
,
1

hey all,

I am trying to learn Mo’s algorithm and am trying to solve various problems with it but as of now failing badly. The problem I am trying is Powerful Arrays from Codeforces. I am pretty sure the query is sorted correctly but its still giving me TLE verdict. How can I optimize it to run quicker. The submission in question: Submission.

Thanks…

2

Ur mo’s is not right firstly.It has a fixed sequence(like first move right pointer ,then left,then…),u cant change that sequence.

1 Like
3

Here’s the link to the discussion of the same problem. You might find it helpful!

1 Like
4

@vivek_1998299, I think its left then right and I am doing that only

5

your code is exactly what I did. For test case #6, its taking Time: 2246 ms in your case and for me its giving TLE. I am doing some optimizations, lets see.

6

Check the optimization on sorting the blocks as suggested by @meooow in the above mentioned link!

7

Finally able to solve it. I wonder who did this in contest time. Thanks :slight_smile:

2 Likes
8

Nope ,it should start from right. (I dont know if its in ur case as it depends on question) Assume that the first query is (2,4) so by moving left pointer first u actually remove the things that were never added which can cause problems in most of sums.Thats why we shoupd move right ,then left.

9

It’s not about left or right, the add operations should be done before the remove operations. However for this problem the order does not matter because the math works out.

1 Like
10

Yeah @meooow is right.

Thanx for correcting.

11

I tried to submit your code with some optimizations but failed miserably due to my poor knowledge in Java xD
Glad you solved it :slight_smile:

12

I have used min no. of long long variables and efficient comparator function.

http://codeforces.com/contest/86/submission/36741218

This passes in 2526ms only!