lllAlonsolll's blog

12 D — Ball
By lllAlonsolll, history, 9 years ago, In English

Hi guys! Can someone explain me please, how to use BIT in this problem? http://mirror.codeforces.com/problemset/problem/12/D I've seen that some contestants has solved it using BIT but I didn't understand how they do. Thanks in advance! :)

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by lllAlonsolll (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

Well, the first think that came into my mind was like sort all ladys by say their Bs, then for each lady u have to make a sum query in 2d(Is, Rs) sparce segment tree. Idk there might be something smoother

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You can do it with 1D BIT too. Sort ladies by their increasing values of beauty. A lady is a self-murderer iff there is some lady who has a higher beauty, intellect and richness. Maintain a BIT which stores the maximum possible value of intellect for each value of richness. When you traverse the above sorted list in reverse order, if you're at position i, you know that the ladies inserted into the BIT already have higher beauty. Now find the maximum possible intellect for any value of richness greater than the richness of the current lady. If this found value > intellect value of current lady, then there is definitely some lady j (j > i in sorted list) who has higher values of all three parameters. Complexity: O(logn) per query, O(nlogn) overall. :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Excellent explanation! Thanks a lot, now I finally understand :)

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yea, u r right, i missunderstood the problem a little(i thought u have to count pairs, in which selfmurdering occurs).

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But we can't make a BIT of size 109

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

std::map is enough

→ Reply