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

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

Hi guys! Can someone explain me please, how to use BIT in this problem? http://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! :)

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

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

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

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

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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. :)

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

std::map is enough