You should use a segment tree with lazy propagation. After all updates are done, query every point to see which poster is there.

It's only necessary to check points that are either endpoints or posters or at distance 1 from some endpoint, so you can safely compress the coordinates first and then use a segment tree of size 2¹⁷.

Hi, I used a sweep line aproach. For each poster consider its begin and end in a vector, then sort by coordinate (if two are equal first the begin). Now store the current posters in a set by index (order in the input), when you find a begin in the vector add the index, otherwise delete it from de set (O(logN). In each step you could ask wich is the greater index in the set ( if the current coordinate is different from the previous one ) using iterators (for C++, I dont know other languages) and add it to other set. The answer will be the final size of this new set.

I hope you understand my explanation, send me a MP if you continue having problems to send you me AC code

PD: Sorry for my english

1. Compress input numbers. Let's say M is the greatest number now.
2. Keep a set which contains free positions. Initially it contains all numbers from 1 to M.
3. Process the posters in reverse order. If there is a number between a_i and b_i in the set (you can check this with set.lower_bound() function), then this poster is not entirely covered by the posters after it. In this case, remove all numbers that are between a_i and b_i from the set.

this problem can be solved without segment tree or bit, create your own Doubly linked list and process posters in reverse order , more hint : each node of your Doubly linked list should hold two value (l,r) , left and right ;-)

There are numerous solution known for this problem, but I personally think this is the best solution. It is an improvement to sparik's solution.

First, compress the coordinate / reverse the query.

Now consider this recursive function :

void paint(int s, int e, int x){
if(s == e) return;
if(!painted[s]) painted[s] = x;
paint(s+1, e, x);

This function is obvious but slow.

Now it can be optimized using simillar mechanism to disjoint sets. First, initialize nxt[i] = i;

int paint(int s, int e, int x){
if(s >= e) return s;
if(!painted[s]) painted[s] = x;
return nxt[s] = paint(nxt[s]+1, e, x);

This program runs in O(nlgn), but in practice it is roughly linear. http://mirror.codeforces.com/blog/entry/21476#comments

I have solved it using sets
Do like this
1.Compress the coordinates
For example : Map (12,3,13,14) to (2,1,3,4) , (13,6,23,25,11) to (3,1,4,5,2)
2. Initialize a set inserted with all elements from min value(1) to max_value of coordinate obtained input (After compressing).
3.Now start from the last coordinates suppose (x,y):
a.find lower_bound of first coordinate of x(it)
b.find upper_bound of last coordinate of y(jt)
if(it != jt)
count += 1
4.print count
(count is number the posters visible on the wall)
Here is link to solution : http://ideone.com/AibFQ7