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

Автор Jim_Moriarty_, история, 4 года назад, По-английски

How to proceed after coordinate compression.. Please help.. https://www.spoj.com/problems/POSTERS/ — problem link

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

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

There is a comment in the SPOJ page that specifically says:

Coord compression + Brute force = 0.08s

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

    Actually I wanted to know how to do using segment tree and lazy

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

      Similar problem :LightOj 1207. Only difference is that you have to compress the array in this SPOJ one

      After compressing the array,build a segment tree of size 2e17.

      Updation part is as like as any other lazy propagation but , while pushing up the results, if left child and right child of a node has same value then only the node can have this same value. If left child and right child have different values assigned then you have to assign their parent node with value zero (you can do it differently and then code accordingly).

      In the query function,you have to do the same pushing up as you did in the updation part. When you will get a node having value greater then zero,store this node in a set.

      And then print the size of the set.

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

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

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

...

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

7sec TL and n is 40000, just try straighforward $$$O(n^2)$$$ maybe