atlasworld's blog

By atlasworld, history, 12 months ago, In English,

Can anyone please share the idea behind , how to solve 35E

any help ... since no tutorial is available..

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You need a segment tree with interval set max operation and get value at some position query. Perform set operation for each triple (l, r, h) in input. Then iterate in increasing order by combined array of l's and r's (delete duplicates). Lets say that we are currently solving position x. Then if get(x)!=get(x-0.5) add vertices (x,get(x-0.5)) and (x,get(x)), and if get(x)!=get(x+0.5) add vertices (x,get(x)) and (x,get(x+0.5)) to the solution.

My code: https://codeforces.com/contest/35/submission/42893914