Mock CCO '17 Problem 6 - Dire Consequences

View as PDF

Submit solution

Points: 20
Time limit: 1.8s
Memory limit: 256M

Author:
Problem types

imaxblue has completed his mission, but he realizes he has much more events to alter. There are N key points in space-time, numbered 0 to N-1, conveniently represented by positive points on the coordinate grid. imaxblue has M events he would like to change, also represented by points in space-time (note that these are not necessarily key points). However, changing a point will affect all points contained within the square of that point and the origin (0, 0). Formally, changing point (x_k, y_k) will affect all points (x_i, y_i) with x_i \le x_k and y_i \le y_k for i between 0 and N-1. imaxblue would like to make sure that no key point is affected by more than 1 changed event. Help imaxblue find the largest number of key points he can change, without changing any key point twice.

Subtasks

For all cases: N, M \le 200\,000.
For 3 points, N, M \le 5\,000.
For additional 2 points, y_i=1.

Sample Input

5 5
1 5
2 4
3 2
8 2
5 3
8 2
6 3
1 10
2 4
100 1

Sample Output

4

Explanation

Change points (8, 2), (1, 10) and (2, 4) to affect points (1, 5), (2, 4), (3, 2) and (8, 2).


Comments

There are no comments at the moment.