Bookings


Submit solution

Points: 100 (partial)
Time limit: 6.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C++

This problem is interactive.

Covid is finally over and you can now go to gym ! To avoid crowding and thus prevent another wave of covid, the administration decided to set up a booking system.

The gym will be open for \(M\) units of time each day. To use any machine a member should make a reservation. A reservation \(i\) has a start time \(s_i\) and a duration \(d_i\) (\(0 \leq s_i < s_i + d_i \leq M\)). Reservations may arbitrarily overlap with one another, and are not necessarily distinct.

You want to use the treadmill, but you are late as other members have already made reservations... Since you are the MAGOI champion, the gym staff can let you book any time interval you want, as long as it doesn't entirely contain another reservation. We would like to know how many intervals you can chose ?

An interval \([x,y]\) is entirely containing another interval \([a,b]\) if for each integer \( u \in [a,b] \implies u \in [x,y]\)

Interaction protocol

Your program should read every value printed by the grader in standard input, and print in standard output the answer corresponding to each query.

First, the grader will output \(M\) (\(1 \leq M \leq 10^9\)) the duration of the opening. After that, the grader will output multiple queries (at most 1000000), one in each line. The i\(^{th}\) query consists of two integers: \(s_i\) the start time and \(d_i\) the duration of the i\(^{th}\) reservation. Right after that you should print the number of time intervals you can chose that don't entirely contain another reservation \(j \leq i\). Print that number modulo \(1000000007\).

Your program should immediately terminate when the grader outputs -1 (do not wait for another input !). Your solution may get the verdict Time limit exceeded if you don't print anything or forget to flush the output buffer.

Scoring

\begin{array}{|c|c|c|} \hline \text{Group} & \text{Points} & \text{Constraints} \cr \hline 1 & 5 & \text{There is only one query} \cr \hline 2 & 10 & \text{M is at most 1000} \cr \hline 3 & 10 & \text{There are at most 1000 queries} \cr \hline 4 & 20 & \text{No two reservations overlap and reservations are given in increasing order of s} \cr \hline 5 & 15 & \text{No two reservations overlap} \cr \hline 6 & 40 & \text{No additional constraint} \cr \hline \end{array}

Sample Interaction

10
1 1 
>>> 37
6 1
>>> 17
1 4 
>>> 17
-1

>>> denotes your output, you should not output it !


Comments

There are no comments at the moment.