SPOJ - POSTERS

138. Election Posters

Although this problem is actually a good data structure problem, which is meant to be solved by range tree, but as that would need a trick. We only have 40000 nodes so total of 80000 points, but actual range is huge (10^7) for range trees. So, we can map the points so that they span over the minimum range (i.e. compress them). Sounds pathetic, right? However, there are easier ways to solve this.

By using STL set, you can make the problem pretty simulation type. Lets consider a set which contains the ranges, but not as given in input. At any moment, the set will represent the wall at that time, i.e. only visible ranges (so they must be mutually exclusive).

Now, whenever we need to add a new range, we find the leftmost poster (or piece of poster still visible) which must fall under the current one (probably you already got it, it's called lower_bound) and the rightmost poster segment that must fall under it. All the segment between these two segments will be covered, so we remove them from set. Now, we just again insert new left fragment, new right fragment and the new range... that simple it is!

Finally, we can keep and index with each segment so that we can calculate the number of actual different segment at the end of the day :)
For more clarification, consider the sample case:

5
1 4
2 6
8 10
3 4
7 10

The states of the set are shown after each input:

1 4
first entry
{(1,4)}

2 6
{1,4) is leftmost and rightmost at the same time (according to above discussion)
So, we remove it and insert new ranges:
{(1,1),(2,6)}

8 10
no conflict
{(1,1),(2,6),(8,10)}

3 4
conflicts with (2,6) (left and right both)
{(1,1),(2,2),(3,4),(5,6),(8,10)}

7 10
conflicts with (8,10)
{(1,1),(2,2),(3,4),(5,6),(7,10)}

Finally, segments with different id:
(1,1), (2,2), (3,4), (7,10). Note, (2,2) and (5,6) should have same id.

It's good if you have understood what to do, and it's even better if you don't, cause you should solve your problems on your own :p