Description

During university, classrooms often need to be rented. From department events to small study groups, everyone needs to apply to the school to borrow classrooms. Classroom sizes and functions differ, and the borrower’s identity may differ, so the procedures vary as well.

Given a large number of rental requests, we want to solve this problem by programming.

We need to process borrowing requests for the next $n$ days. On day $i$, the school has $r_i$ classrooms available for rent. There are $m$ orders. Each order is described by three positive integers $d_j, s_j, t_j$, meaning a borrower wants to rent $d_j$ classrooms per day from day $s_j$ to day $t_j$ inclusive.

We assume borrowers have no requirements regarding classroom size or location. That is, for each order we only need to provide $d_j$ classrooms each day; which specific classrooms they are, or whether they are the same across days, does not matter.

Borrowing follows a first-come, first-served principle. We process orders in the given order and allocate classrooms accordingly. If, during allocation, an order cannot be fully satisfied, we must stop allocation and notify the current applicant to modify the order. Here, “cannot be satisfied” means that on at least one day between $s_j$ and $t_j$, the remaining number of classrooms is less than $d_j$.

We need to determine whether any order cannot be fully satisfied. If so, which applicant should be notified to modify their order.

Input Format

• The first line contains two positive integers $n, m$, the number of days and the number of orders.
• The second line contains $n$ positive integers; the $i$-th number is $r_i$, the number of classrooms available on day $i$.
• The next $m$ lines each contain three positive integers $d_j, s_j, t_j$, denoting the quantity requested per day and the start and end days of the rental.
• Adjacent numbers on the same line are separated by a single space. Days and orders are both numbered starting from $1$.

Output Format

• If all orders can be satisfied, output a single line containing the integer $0$.
• Otherwise, output two lines: the first line contains the negative integer $-1$, and the second line contains the index of the applicant whose order needs to be modified.

4 3 
2 5 4 3 
2 1 3 
3 2 4 
4 2 4

-1 
2

Hint

Sample explanation:

After satisfying order $1$, the remaining classrooms for $4$ days are $0, 3, 2, 3$. Order $2$ asks for $3$ classrooms per day from day $2$ to day $4$, but on day $3$ the remaining classrooms are $2$, so it cannot be satisfied. Allocation stops, and the applicant of order $2$ is notified to modify the order.

Constraints:

• For $10\%$ of the testdata, $1 \le n, m \le 10$.
• For $30\%$ of the testdata, $1 \le n, m \le 1000$.
• For $70\%$ of the testdata, $1 \le n, m \le 10^5$.
• For $100\%$ of the testdata, $1 \le n, m \le 10^6$, $0 \le r_i, d_j \le 10^9$, $1 \le s_j \le t_j \le n$.

Additional notes:

NOIP 2012 Senior Day 2, Problem 2.

A new set of hack testdata was added on 2022.2.20.

Translated by ChatGPT 5