Jim_Moriarty_'s blog

Help in spoj problem POSTERS
By Jim_Moriarty_, history, 5 years ago, In English

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

  • Vote: I like it
  • -2
  • Vote: I do not like it

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

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

Coord compression + Brute force = 0.08s

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

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

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

      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.

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

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

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

...

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

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

→ Reply