E - ストレスメーター 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 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 から開始し、タスク L_j, L_j + 1, \ldots, R_j をこの順に処理したとき、すべてのタスクの処理（ステップ 3 まで）を終えた後の限界に達した回数 C とストレス値 G を求めてください。

各質問は独立です。ある質問の結果が別の質問に影響することはありません。

制約

  • 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
  • 1 行目には、タスクの個数 N、限界のしきい値 K、質問の個数 Q が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目には、i 番目のタスクの負荷 A_i と休憩による回復量 B_i が、スペース区切りで与えられる。
  • 続く Q 行のうち j 行目には、j 番目の質問で処理する区間の左端 L_j と右端 R_j が、スペース区切りで与えられる。

出力

Q 行出力せよ。j 行目には、j 番目の質問に対する限界に達した回数 C とストレス値 G を、この順にスペース区切りで出力せよ。

入力例 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

Score : 466 pts

Problem Statement

Takahashi has a job where he processes N tasks in order.

For the i-th task, an integer A_i representing the workload and an integer B_i representing the recovery from a break are defined.

Takahashi's stress level is managed as a non-negative integer G (initially 0), and the number of times he has reached his limit is managed as a non-negative integer C (initially 0). When processing task i, the following operations are performed in order of steps 1, 2, 3.

  1. Due to the task's workload, the stress level increases by A_i. That is, G is updated to G + A_i.
  2. Due to the break after the task, the stress level decreases by B_i. However, the stress level does not go below 0. That is, G is updated to \max(0, G - B_i).
  3. At this point, if G \geq K, Takahashi reaches his limit. C is updated to C + 1, and G is updated to 0. If G < K, nothing happens.

After step 3 is completed (whether or not he reached his limit), he proceeds to process the next task.

Aoki asks Q questions of the form "What would happen if only a portion of the task sequence were processed?"

In the j-th question, integers L_j and R_j are given.

Starting from G = 0, C = 0, determine the number of times the limit was reached C and the stress level G after all tasks L_j, L_j + 1, \ldots, R_j have been processed (through step 3) in this order.

Each question is independent. The result of one question does not affect another question.

Constraints

  • 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
  • All inputs are integers.

Input

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
  • The first line contains the number of tasks N, the limit threshold K, and the number of questions Q, separated by spaces.
  • In the following N lines, the i-th line contains the workload A_i and the recovery from a break B_i for the i-th task, separated by spaces.
  • In the following Q lines, the j-th line contains the left endpoint L_j and right endpoint R_j of the interval to be processed in the j-th question, separated by spaces.

Output

Output Q lines. The j-th line should contain the number of times the limit was reached C and the stress level G for the j-th question, in this order, separated by a space.

Sample Input 1

5 10 4
6 2
4 1
8 0
3 5
10 3
1 3
2 4
4 5
3 3

Sample Output 1

1 0
1 0
0 7
0 8

Sample Input 2

4 5 5
1 0
2 5
5 0
6 2
1 1
1 2
1 3
3 4
4 4

Sample Output 2

0 1
0 0
1 0
1 4
0 4

Sample Input 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

Sample Output 3

1 2
2 0
1 0
1 3
3 12
1 12
1 0
2 0
2 1
0 0

Sample Input 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

Sample Output 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

Sample Input 5

1 300 1
1000000000 999999700
1 1

Sample Output 5

1 0