← 返回题目列表

AtCoder · awc0109_e

E. 压力计

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥有一份处理工作 N 任务按顺序排列。

对于 i- 第一个任务,一个整数 A_i 表示工作负载和一个整数 B_i 。

高桥的压力水平被管理为非负整数 G (最初 0),并且他达到限制的次数被管理为一个非负整数 C (最初 0)。处理任务时 i,按照步骤1、2、3的顺序执行以下操作。

  1. 由于任务的工作量,压力水平增加了 A_i。也就是说, G 更新为 G + A_i.
  2. 由于任务结束后的休息,压力水平降低了 B_i。然而,压力水平不会低于 0。也就是说, G 更新为 \max(0, G - B_i).
  3. 此时,如果 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