Блог пользователя unlucky_13

Help on segment tree
Автор unlucky_13, 12 лет назад, По-английски

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

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

  • Проголосовать: нравится
  • -16
  • Проголосовать: не нравится

»
12 лет назад, # |
← Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 ???

    → Ответить