ak3899's blog

By ak3899, history, 6 years ago, In English

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.

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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