Mr.Awesome's blog

By Mr.Awesome, history, 8 years ago, In English

I was trying to solve this problem but i got TLE.

In short terms the problem is :

You are given m queries each contains three integers l,r,x, (l<=x<=r) and you have to fill segment [l,r] with integer x except for the element of indices x, ex. if l=1,r=3 and x=2 segment [l,r] = {2,0,2}.

My solution use an indicator array called nxt to avoid filling the already visited segments and go to the next unvisited item, so this should be done in O(n), however i'm getting a TLE and i can't figure out why.

this is my submission

any help or hint is very appreciated.

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The problem is here

while(i!=nxt[i] && i<=r) i=nxt[i];