Hello, I'm trying to solve E — New Year Domino from last contest, following the tutorial #1.
The tutorial mentions that you can calculate R[i] "using a segment tree or using a stack". My first approach was to try using a stack to see how it could be done, but I'm getting TLE on test 12: Here's my code/submission: http://mirror.codeforces.com/contest/500/submission/9349751 Is there something wrong with the way I'm using the stack to do it?
I also tried to do it with a segment tree then, but I'm getting "WA on test 7" with this approach. Code: http://mirror.codeforces.com/contest/500/submission/9352369 (the segment tree code is from the book Competitive Programming — 3rd edition). It's essentialy the same approach as before, but using the segtree instead of a stack. Printing the contents of U and R for the small test cases is giving me the correct values, so I was unable to find the error. Can someone please help?
PS: in the code:
pos[i] and len[i] are the x-position and length of the i-th domino
R[i] is the maximum x position covered when you drop the i-th domino
U[i][j] has the 2^jth "uncovered" piece index when you drop domino i (the 2^jth piece to 'break the interval'), as described in the tutorial
S[i][j] has the value needed to cover from i to U[i][j].
I just reviewed your code which uses a stack.
There's no problem with your stack implementation, it is with your build part for 2^j interval breakdown. See this Updated Code ,I just exchanged the position of for loop for (i,j)
P.S -> I prefer doing query with something like this Updated Query
Wow, thanks a lot!
I don't get why changing the loop make such a difference though (from TLE of 2s on test 12 to AC with 436ms :O).
I mean, I can see why it's better, you break from a N loop instead of a log N loop. But it's still O(N logN) with N=2x10^5 (and TL = 2s). That should be ok, shouldn't it? Is there something I'm missing?
The updated query is indeed neater!
Actually if the ith loop is written first and then the jth(logN one) then, Suppose if you are computing the value for i = 0, j = 2 and U[i][1] = 2 then for computing the value for U[0][2] you need the value for U[2][1] which is not computed until now.
while exchanging both the loops it won't be a problem as all the values of U[i][1] is already computed for i in range(0,n-1).
The updated query is picked up directly from the LCA tutorial of topcoder :)
give me — please