No.3665 Two Important Tasks
タグ : / 解いたユーザー数 8
作問者 :
sepa38
Problem Statement
There are $N$ jobs, and you are going to choose some of them to do.
If you do the $i$-th job, you must work on it every day during the period from day $L_i$ to day $R_i$. Also, doing the $i$-th job gives you a reward of $C_i$.
Note that you cannot do multiple jobs on the same day.
Now, you know that there are two important jobs that you must do.
You are given $Q$ queries, so answer the following problem for each of them. The $j$-th query is as follows.
- Output the maximum total reward you can obtain when the important jobs are the $a_j$-th and $b_j$-th jobs. If it is impossible to do both important jobs, output
-1.
Constraints
- $2 \leq N,Q \leq 2 \times 10^5$
- $1 \leq L_i \leq R_i \leq N$
- For any integer $p$, there are at most $5$ integers $i$ satisfying $L_i \leq p \leq R_i$
- $1 \leq C_i \leq 10^9$
- $1 \leq a_j < b_j \leq N$
- All input values are integers
Input
The input is given from standard input in the following format.
$N$ $Q$ $L_1$ $R_1$ $C_1$ $L_2$ $R_2$ $C_2$ $\vdots$ $L_N$ $R_N$ $C_N$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_Q$ $b_Q$
Output
Output $Q$ lines.
On the $i$-th line, output the answer to the $i$-th query.
Sample
Sample 1
Input
5 4 1 2 4 3 4 5 2 3 10 5 5 2 1 1 3 1 2 1 3 2 5 3 4
Output
11 -1 10 15
In the $1$-st query, doing the $1$-st, $2$-nd, and $4$-th jobs gives a total reward of $11$.
In the $2$-nd query, the periods of the two important jobs overlap, so you cannot do both.
Sample 2
Input
4 3 1 4 100 1 1 10 2 2 20 3 4 30 1 2 2 4 3 4
Output
-1 60 60
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。