deam0n's blog

By deam0n, 12 years ago, In English

Hello all

I'm trying to solve the problem http://www.spoj.com/problems/HORRIBLE/ but getting WA again n again. I'm using segment trees with lazy propagation. Can somebody please help figure out my mistake.

Thanks in advance.

Code: http://pastebin.com/aT3pvi3K

-- Thanks to diego_v1

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By deam0n, 12 years ago, In English

I'm trying to understand Heavy-Light decomposition method for answering LCA queries , but stuck with it. I'm not able to understand the concept of exactly why you needed "vertex-disjoint" and "edge-disjoint" paths. And as I see in some problems we pre-process "edge-disjoint" paths with segment trees. Why we would do that?

Can some help in rephrasing the whole idea step-by-step? I'm following problem E from http://felix-halim.net/story/icpc10/problems.pdf . Any help would be appreciated.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By deam0n, 12 years ago, In English

I'm trying to solve a RMQ problem at lightoj using Segment Tree , but it always gives me TLE. Can anybody help in pointing out my mistake ?

Problem link : http://www.lightoj.com/volume_showproblem.php?problem=1082

Code link : http://pastebin.com/UqaumDKG

Full text and comments »

Tags rmq
  • Vote: I like it
  • 0
  • Vote: I do not like it