xuanquang1999's blog

Getting WA on Counting Inversion Problem
By xuanquang1999, history, 9 years ago, In English

I'm having trouble at this problem on Vietnam SPOJ. The problem is: Given array a[1], a[2], ... a[n], count the number of pair (u, v) that u < v and a[u] > a[v]. Constrain: n <= 60000 and a[i] <= 60000.

I tried to this using Fenwick Tree. But I'm getting only 60 points (maximum points is 100). Is there anything wrong in my implementation?

Here's my code.

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

»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

t.add(n, a[i], 1); ---> t.add(60000, a[i], 1);

→ Reply