unlucky_13's blog

Help on segment tree
By unlucky_13, 14 years ago, In English

http://acm.timus.ru/problem.aspx?num=1028

can somenone explain me how to do it using segment tree????

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

»
14 years ago, hide # |
← Rev. 3  
Vote: I like it +8 Vote: I do not like it

It's clearly classic segment tree

first of all sort all points in increasing order, then start from first point in sorted list and count number of points with smaller or equal Y than this point in segment tree and after that increase value of point's Y in segment tree and see next point in sorted list ...

this is my accepted code

→ Reply
  • »
    »
    14 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    i am getting WA on test case 3 :(

    here is my code: http://pastebin.com/W0iHVkt2

    i have created a tree the lowest level having leaves like 0-1,1-2,2-3 etc

    the in the query i have add all the ranges which is lower the query number(the global variable L will hold the info)

    like query(5) will return the total numbers which are in range (0-3)+(3-5)

    the i have update the whole tree if the the number is in between the range

    whats wrong with the idea ???

    → Reply