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.


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.


For each test case output a line containing one integerĀ - the number of posters with visible sections.


Sample input:
1 4
2 6
8 10
3 4
7 10

Sample output:

An illustration of the sample input is given below.

The wall with posters

hide comments
chinhchamhoc: 2019-11-29 04:22:32

could someone tells me how to solve using DSU pls

hduoc2003: 2019-09-28 18:08:29

Weak test cases.
segtree + lazy = 0.02s
dsu = 0.01s
But i used co-ordinate compression for both :D.
Can anyone tell me how to do lazy without compressing pls :))

Last edit: 2019-09-28 18:09:26
prmondal: 2019-07-01 17:39:21

Last edit: 2019-07-05 08:55:25
ab_biswas09: 2019-03-16 17:21:41

co-ordinate compression => 0.04 sec

tanmayak99: 2019-01-13 15:05:14

Did it with (Lazy+Segtree) . How to do it with Coordinate compression ?

anshumanc007: 2018-12-14 11:36:03

solved with lazy prop! how to do with DSU?

phoemur: 2018-11-24 23:13:14

With coordinate compression even a naive O(n*m) gets AC here

Segtree + lazy = 0.02s
Coord compression + Brute force = 0.08s

Last edit: 2018-11-24 23:18:08
lapmid: 2018-10-26 16:54:47

AC using Lazy , Anyone Please explain this using DSU

dlp_302: 2018-10-08 16:21:21


kaiser17: 2018-07-11 21:04:20

too easy

Added by:adrian
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:VI Polish Collegiate Team Programming Contest (AMPPZ), 2001