| Submit | All submissions | Best solutions | Back to list |
POSTERS - Election 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 |
| Date: | 2004-07-19 |
| Time limit: | 7s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
| Resource: | VI Polish Collegiate Team Programming Contest (AMPPZ), 2001 |
hide comments
|
||||||||
|
2023-02-13 18:03:10
You don't need any data structure or algorithm. you can directly simulate using recursion. |
||||||||
|
2021-08-08 15:46:04
Hello Segment tree is good option but set.lower_bound() is better choice . If you don't know set.lower_bound() go and google it and I am sure set.lower_bound() help you in many questions Tried 3-4 month ago but solved now properly Last edit: 2021-08-08 15:46:39 |
||||||||
|
2021-05-02 05:45:08
No need of dsu, co-ordinate compression or lazy segtree . |
||||||||
|
2020-09-07 11:07:45
co-ordinate compression is the easiest way to solve although can be solved using lazy propagation and dsu. |
||||||||
|
2020-07-26 22:10:16
Can someone tell me how to do this problem with lazy propagation. Email id: <snip>@gmail.com Last edit: 2023-06-08 08:13:13 |
||||||||
|
2020-06-15 21:36:35
Nice problem! Many people suggest lazy propagation. However, I find it much more hassle-free to solve it using coordinate-compression. |
||||||||
|
2020-06-11 14:25:10
@fahimcp495. You said, it seems to me that the judge solution is not right according to the problem statement. i.e. for 1 3 20 30 10 20 30 40 output should be 3 but AC code gives 2 I think the judge solution is wrong. It will give 2 for compression. Because then 10 20 will become 2 - 3. But this 2 will be covered by 1 - 10 (1-2 after compressing) and 3 will be covered by 20-30 (3 -4 after compressing). That's because 10 and 20 has a 10 gap in it. But after compression 2 and 3 are adjacent. And nothing is in between them. For this problem, I think we should take compress array with some gaps before and after it. As if the array is [1 10 20 30] then we should consider it as [0 1 2 9 10 11 19 20 21 29 30 31]. Then we can cut off the duplicate or invalid ones. |
||||||||
|
2020-06-03 02:33:17
it seems to me that the judge solution is not right according to the problem statement. i.e. for 1 3 20 30 10 20 30 40 output should be 3 but AC code gives 2 |
||||||||
|
2020-04-07 09:38:35
nice lazy propogation,segtree+coordinate compression |
||||||||
|
2020-03-28 12:52:13
can be solved using coordinate compression and sqrt decomposition |
||||||||
RSS