DMOPC '21 Contest 7 P4 - Rocket Race

View as PDF

Submit solution

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

Problem types

Tyler is a competitive rocket racer. Unlike in normal foot racing, rocket racers use their own collection of rockets to move instead of their feet. Tyler's collection consists of N single-use rockets. The i-th rocket propels him a_i meters forwards, but sends him b_i meters backwards immediately after. Of course, rocket technology is constantly evolving, and racers need to update their collection frequently to ensure optimal performance. As Tyler's coach, you must handle Q of the following events, each starting with a value t_j:

  • If t_j = 0 then an integer r_j follows, and you must tell Tyler the minimum number of rockets he needs to complete an r_j meter race. Note that the race is completed if Tyler reaches or passes the finish line at the r_j meter mark at any point. Also, all rockets may only be used in the forward direction (i.e. initially towards the finish line).
  • If t_j > 0 then two integers x_j and y_j follow, indicating that Tyler replaces the t_j-th rocket with one that propels him x_j meters forwards but sends him y_j meters backwards immediately after.


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

1 \le a_i, b_i, r_j, x_j, y_j \le 10^9

0 \le t_j \le N

Subtask 1 [25%]

1 \le N, Q \le 3 \times 10^3

Subtask 2 [25%]

t_j = 0

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains an integer N.

The next N lines each contain 2 integers a_i and b_i.

The next line contains an integer Q.

The next Q lines each contain the description of an event on a single line, as described in the statement.

Output Specification

For each event with t_j = 0 output the answer on its own line, or -1 if it is impossible to complete that race.

Sample Input

2 1
5 7
4 1
5 4
7 3
9 4
1 6
6 4
5 2
4 5
0 15
0 8
6 7 5
0 11
0 8
0 100

Sample Output



For the first event, Tyler should use his 5-th, 6-th, and 8-th rockets in that order. This reaches a maximum forward distance of 15 meters, which is just enough to complete the race.

For the fifth event, Tyler should use his 5-th rocket and then his 2-nd rocket. This reaches a maximum forward distance of 9 meters, enough to complete the race.

For the sixth event, it is impossible for Tyler to complete the race regardless of which rockets he chooses to use.


There are no comments at the moment.