C - 水やりの記録 解説 /

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

配点 : 366 点

問題文

高橋君は学校の園芸委員会に所属しており、花壇の管理を担当しています。

花壇には N 本の植物が一列に並んでおり、先頭から順に植物 1, 植物 2, \ldots, 植物 N と番号が付けられています。各植物 i (1 \leq i \leq N) は、初期の水分量として整数値 A_i を持っています。高橋君はじょうろを使って、これらの植物に水やりを行います。

高橋君は合計 M 回の水やりを行います。j 回目 (1 \leq j \leq M) の水やりでは、植物 L_j から植物 R_j まで（両端含む）の連続した範囲のすべての植物に水を与え、対象となった各植物の水分量を 1 ずつ増加させます。ある植物が複数回の水やりの対象となった場合、対象となった回数だけ水分量が増加します。

すべての水やりが終わった後、水分量が K 以上になった植物の本数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
  • 入力はすべて整数である

入力

N M K
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • 1 行目には、植物の本数を表す整数 N、水やりの回数を表す整数 M、水分量の閾値を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各植物の初期の水分量を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 続く M 行にわたり、各水やりの対象範囲が与えられる。
  • 2 + j 行目 (1 \leq j \leq M) には、j 回目の水やりの対象となる植物の番号の範囲を表す整数 L_j と R_j が、スペース区切りで与えられる。

出力

すべての水やりが終わった後、水分量が K 以上になった植物の本数を 1 行で出力せよ。

入力例 1

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

出力例 1

5

入力例 2

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

出力例 2

2

入力例 3

10 5 1000000000
999999999 0 999999998 500000000 0 1000000000 999999997 0 999999999 0
1 3
1 1
6 7
7 10
3 9

出力例 3

5

Score : 366 pts

Problem Statement

Takahashi is a member of his school's gardening committee and is in charge of managing the flower bed.

The flower bed contains N plants arranged in a row, numbered Plant 1, Plant 2, \ldots, Plant N from the front. Each plant i (1 \leq i \leq N) has an initial moisture level of integer value A_i. Takahashi uses a watering can to water these plants.

Takahashi performs a total of M waterings. In the j-th watering (1 \leq j \leq M), he waters all plants in the contiguous range from Plant L_j to Plant R_j (inclusive), increasing the moisture level of each targeted plant by 1. If a plant is targeted by multiple waterings, its moisture level increases by the number of times it was targeted.

After all waterings are completed, find the number of plants whose moisture level is at least K.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
  • All input values are integers

Input

N M K
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • The first line contains three space-separated integers: N representing the number of plants, M representing the number of waterings, and K representing the moisture threshold.
  • The second line contains space-separated integers A_1, A_2, \ldots, A_N representing the initial moisture level of each plant.
  • The following M lines specify the target range of each watering.
  • The (2 + j)-th line (1 \leq j \leq M) contains two space-separated integers L_j and R_j representing the range of plant numbers targeted by the j-th watering.

Output

Print in one line the number of plants whose moisture level is at least K after all waterings are completed.

Sample Input 1

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

Sample Output 1

5

Sample Input 2

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

Sample Output 2

2

Sample Input 3

10 5 1000000000
999999999 0 999999998 500000000 0 1000000000 999999997 0 999999999 0
1 3
1 1
6 7
7 10
3 9

Sample Output 3

5