分数: 466 分
问题陈述
高桥有一份处理工作 N 任务按顺序排列。
对于 i- 第一个任务,一个整数 A_i 表示工作负载和一个整数 B_i 。
高桥的压力水平被管理为非负整数 G (最初 0),并且他达到限制的次数被管理为一个非负整数 C (最初 0)。处理任务时 i,按照步骤1、2、3的顺序执行以下操作。
- 由于任务的工作量,压力水平增加了 A_i。也就是说, G 更新为 G + A_i.
- 由于任务结束后的休息,压力水平降低了 B_i。然而,压力水平不会低于 0。也就是说, G 更新为 \max(0, G - B_i).
- 此时,如果 G \geq K,高桥达到了他的极限。 C 更新为 C + 1,和 G 更新为 0。如果 G < K,什么也没发生。
步骤3完成后(无论是否达到极限),他将继续处理下一个任务。
青木问 Q 形式的问题“如果只处理任务序列的一部分会发生什么?”
在 j第题,整数 给出了 L_j 和 R_j 。
从 G = 0, C = 0,确定达到限制的次数 C 和压力水平 G 完成所有任务后 L_j, L_j + 1, \ldots, R_j 已按此顺序处理(通过步骤 3)。
每个问题都是独立的。一个问题的结果不会影响另一个问题。
约束
- 1 \leq N \leq 6 \times 10^4
- 1 \leq K \leq 300
- 1 \leq Q \leq 6 \times 10^4
- 1 \leq A_i \leq 10^9
- 0 \leq B_i \leq 10^9
- 1 \leq L_j \leq R_j \leq N
- 所有输入均为整数。
输入
N K Q A_1 B_1 A_2 B_2 \vdots A_N B_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- 第一行包含任务数 N,限制阈值 K,以及问题数量 Q,用空格分隔。
- 如下 N 行, i- 第行包含工作负载 A_i 以及从休息中恢复 B_i 为 i- 第一个任务,以空格分隔。
- 如下 Q 行, j第行包含左端点 L_j 和右端点 R_j 中要处理的区间 j第一个问题,用空格分隔。
输出
输出 Q 行。的 j- 第行应包含达到限制的次数 C 和压力水平 G 为 j第一个问题,按此顺序,用空格分隔。
示例输入 1
5 10 4 6 2 4 1 8 0 3 5 10 3 1 3 2 4 4 5 3 3
示例输出 1
1 0 1 0 0 7 0 8
示例输入 2
4 5 5 1 0 2 5 5 0 6 2 1 1 1 2 1 3 3 4 4 4
示例输出 2
0 1 0 0 1 0 1 4 0 4
示例输入 3
15 20 10 7 3 12 5 4 10 25 0 3 1 18 4 6 6 30 15 9 0 2 8 14 2 5 20 21 1 8 7 11 0 1 5 2 8 4 4 6 10 1 15 9 15 11 13 3 12 7 14 10 10
示例输出 3
1 2 2 0 1 0 1 3 3 12 1 12 1 0 2 0 2 1 0 0
示例输入 4
40 300 25 120 30 250 100 80 0 500 250 40 60 1000 800 299 0 1 0 600 350 75 75 310 10 20 5 450 200 90 10 200 50 150 200 700 401 60 0 30 100 1000000000 999999900 5 0 295 10 400 120 55 55 180 30 240 100 360 80 15 0 90 20 600 600 280 0 35 10 100 0 500 260 70 30 330 40 10 100 220 10 410 200 50 0 1 10 5 15 10 20 15 25 20 30 25 35 30 40 1 40 7 7 11 18 19 22 23 29 31 36 34 40 2 39 4 13 8 27 12 32 16 16 20 20 21 40 1 1 40 40 6 24 14 38
示例输出 4
3 250 3 150 3 100 3 0 3 85 3 40 4 50 13 50 0 299 3 60 1 0 2 85 3 0 2 50 12 0 3 265 6 0 6 25 0 0 0 100 6 50 0 90 0 50 5 280 7 210
示例输入 5
1 300 1 1000000000 999999700 1 1
示例输出 5
1 0