Mayor Election Posters
Time limit1sMemory limit192 MB
Given n posters pasted in order over intervals on a huge wall, count how many posters remain at least partially visible after later posters overlap earlier ones.
- Level
Medium6 of 10
- Topics
- Segment tree, Combinatorics, Intervals, Sorting
- Solved
- No attempts yet
Problem
A town is preparing for a mayoral election and wants to place candidate posters on a wall. The election committee has set the following rules.
- Each candidate may place exactly one poster on the wall.
- Every poster has the same height as the wall, and its width may be chosen freely.
- The wall is divided into byte-sized pieces.
- Each poster must cover its assigned wall interval without gaps.
The wall is 100,000,000 bytes wide. Candidates place their posters in the order given in the input. A new poster may be placed on top of posters that are already covering the same interval. After all posters have been placed, determine how many posters have at least some visible part on the wall on the day before the election.
Input
The first line contains the number of posters n, where 1 ≤ n ≤ 10,000.
Each of the next n lines contains two integers l and r, the left and right endpoint positions of the interval covered by one poster. The constraints are 1 ≤ l < r ≤ 100,000,000.
Posters are placed in the order they appear in the input.
Output
Print the total number of posters that are visible after all posters have been placed in input order.