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

Автор ak3899, история, 6 лет назад, По-английски

i have stuck on this spoj problem in which i have to calculate dominance of points e.g. a point (x1, y1) is said to be dominating another point (x2, y2) if x1>=x2 and y1>=y2 .

https://www.spoj.com/problems/DCEPC705/

my question is that how can i calculate this using binary index tree? this question was queued under the Binary index tree on a portal.

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

First, make coordinate compression to have 0 ≤ x, y < n. Now sort the points in increasing order of x (order points with equal x in increasing order of y). For any point the number of points, which are dominated by it, is equal to count of points behind current point in the list, whose y coordinate is not greater than y coordinate of current point. So iterate over sorted list and keep a binary indexed tree, which counts the number of points with given y coordinate. The number of points, which are dominated by i-th point, is equal to sum(0, yi), after getting the answer for i-th point add 1 at position i of the tree.

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

There are problem 961E - Tufurama and good tutorial for it