WOSS Dual Olympiad 2022 J4: Fire on Christmas Day

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

In preparation for Christmas and a brand new year, your school is planning to host a fire drill to review the safety protocols in place.

You have decided to analyze the efficiency of the procedure by observing a particular hallway in the school. The hallway can be represented as a number line that is N meters long, labelled from 1 to N. There are M fire exits at locations p_i across the hallway, and they can be accessed from classrooms that are within d_i meters of it. It is guaranteed that there is at most one exit located at any given location p_i. In the event that certain fire exits become too crowded, the school's front entrance (location at position 1) and back door (located at position N) are deemed valid exits for any classroom in the school.

To ensure the drill goes smoothly, write a program that supports Q of the following queries:

  • 1 x: What is the position of the closest reachable exit from the class at position x? If there are multiple equidistant exits, output the one with the lowest p_i.
  • 2 x: If the nearest exit to the class located at x becomes too crowded, how many other valid exits can the class choose to take?


For this problem, you will NOT be required to pass the sample cases in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

3 \le N \le 2 \times 10^5

1 \le Q \le 2 \times 10^5

0 \le M \le N-2

2 \le p_i \le N-1

0 \le d_i \le N-3

For all queries, 2 \le x \le N-1.

Subtask 1 [15%]

3 \le N \le 2 \times 10^3

1 \le Q \le 2 \times 10^3

Subtask 2 [20%]

There are only type 1 queries.

Subtask 3 [20%]

There are only type 2 queries.

Subtask 4 [45%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, N and M.

The next M lines each contain two integers, p_i and d_i.

The next line contains a single integer, Q.

The next Q lines each contain a query.

Output Specification

For each query, output the answer on a new line.

Sample Input

9 3
5 2
6 1
8 0
1 4
1 3
2 4

Sample Output


Explanation of Sample

Query 1: The closest exit from the classroom at 4 is at location 5.

Query 2: From location 3, the front entrance and the exit at location 5 are both a distance of 2 away, but we output 1 because it has a lower p_i value.

Query 3: The exits accessible from location 4 are at locations 1, 5 and 9. Since the closest exit at location 5 becomes too crowded, we are left with 2 exits remaining.


There are no comments at the moment.