|
|
SPOJ Problem Set (classical)
138. Election Posters
Problem code: POSTERS
|
A parliamentary election was being held in Byteland. Its enterprising and
orderly citizens decided to limit the entire election campaign to a single
dedicated wall, so as not to ruin the panorama with countless posters and
billboards. Every politician was allowed to hang exactly one poster on the
wall. All posters extend from top to bottom, but are hung at different points
of the wall, and may be of different width. The wall is divided horizontally
into sections, and a poster completely occupies two or more adjacent sections.
With time, some of the posters were covered (partially or completely) by those
of other politicians. Knowing the location of all the posters and the order in
which they were hung, determine how many posters have at least one visible section in the end.
Input
The input begins with the integer t, the number of test cases. Then t test
cases follow.
Each test case begins with a line containing integer n - the number of
posters (1<=n<=40000). Then n lines follow, the i-th (1<=i<=n)
containing exactly two integers li ri, denoting the
numbers of the leftmost and rightmost sections covered by the i-th poster
(1<=li< ri<= 107). The input order
corresponds to the order of hanging posters.
Output
For each test case output a line containing one integer - the number of
posters with visible sections.
Example
Sample input:
1
5
1 4
2 6
8 10
3 4
7 10
Sample output:
4
An illustration of the sample input is given below.
| Added by: | Adrian Kosowski |
| Date: | 2004-07-19 |
| Time limit: | 7s
|
| Source limit: | 50000B |
| Languages: | All |
| Resource: | VI Polish Collegiate Team Programming Contest (AMPPZ), 2001 |
|
|
|
|
RSS