AtCoder Weekday Contest 0096 Beta

A - Closing Time of the Reception Window

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

ある役所には受付窓口が 1 つだけあり、N 人の来客に番号 1, 2, \ldots, N の順番で対応します。窓口では同時に 1 人の来客にしか対応できません。

i 番目の来客は時刻 A_i に役所に到着し、対応には B_i の時間がかかります。来客の到着時刻は番号順に単調非減少、すなわち A_1 \leq A_2 \leq \cdots \leq A_N が保証されます。

窓口は時刻 0 以降に対応可能であり、来客 1 から来客 N まで必ずこの番号順に対応します。来客 i への対応は、窓口が空いていて、かつ来客 i が到着済みである最も早い時刻に開始されます。来客 i の対応開始時刻を S_i とすると、

S_1 = A_1
S_i = \max(S_{i-1} + B_{i-1},\ A_i) （i \geq 2）

であり、来客 i への対応は時刻 S_i + B_i に終了します。

最後の来客（来客 N）への対応が終了する時刻 S_N + B_N を求めてください。

制約

1 \leq N \leq 2 \times 10^5
0 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 10^9
1 \leq B_i \leq 10^9 (1 \leq i \leq N)
入力はすべて整数

入力

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

1 行目には、来客の人数を表す整数 N が与えられる。
続く N 行のうち i 行目には、i 番目の来客の到着時刻 A_i と対応にかかる時間 B_i がスペース区切りで与えられる。

出力

最後の来客への対応が終了する時刻を 1 行で出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

出力例 3

入力例 4

出力例 4

入力例 5

1
1000000000 1000000000

出力例 5

2000000000

Score : 266 pts

Problem Statement

A certain government office has only 1 service window, which serves N visitors in order, numbered 1, 2, \ldots, N. The window can serve only 1 visitor at a time.

The i-th visitor arrives at the office at time A_i, and serving them takes B_i units of time. It is guaranteed that the arrival times are non-decreasing in order of their numbers, i.e., A_1 \leq A_2 \leq \cdots \leq A_N.

The window is available for service from time 0 onwards, and it always serves visitors in order from visitor 1 to visitor N. Service for visitor i begins at the earliest time when the window is free and visitor i has already arrived. Letting S_i denote the start time of service for visitor i:

S_1 = A_1
S_i = \max(S_{i-1} + B_{i-1},\ A_i) （i \geq 2）

Service for visitor i ends at time S_i + B_i.

Find the time S_N + B_N at which service for the last visitor (visitor N) ends.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 10^9
1 \leq B_i \leq 10^9 (1 \leq i \leq N)
All inputs are integers.

Input

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

The first line contains an integer N representing the number of visitors.
The following N lines each contain, on the i-th line, the arrival time A_i and the service duration B_i of the i-th visitor, separated by a space.

Output

Print the time at which service for the last visitor ends, on a single line.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

Sample Output 4

Sample Input 5

1
1000000000 1000000000

Sample Output 5

2000000000

B - Adventurer's Staircase

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君はダンジョンの攻略に挑戦しています。

このダンジョンは N 階層からなり、各階層には 1 から N までの番号が下から順に付けられています。高橋君は最初、階層 1（最下層）にいます。目標は階層 N（最上層）に到達することです。

各階層 i（1 \leq i \leq N - 1）にはモンスターが 1 体ずつ待ち構えており、そのモンスターの強さは E_i です。階層 N にはモンスターはいません。

高橋君は階層 1 から順に 1 階層ずつ上へ進みます。階層を飛ばしたり、引き返したりすることはできません。高橋君が階層 i（1 \leq i \leq N - 1）にいるとき、その階層のモンスターと戦い、勝利しなければ次の階層 i + 1 に進むことはできません。

高橋君の戦闘力は戦闘を通じて変化します。階層 i のモンスターと戦う時点での高橋君の戦闘力を P とすると：

P \geq E_i ならば、高橋君はモンスターを倒すことに成功し、階層 i + 1 に進みます。このとき、倒したモンスターの力を吸収し、戦闘力が P + E_i になります。
P < E_i ならば、高橋君はモンスターに敗北し、それ以上先に進むことはできません。

高橋君はダンジョンに入る前に「強化薬」を使用することができます。強化薬を 1 個使用すると、戦闘力が 1 増加します。使用する強化薬の個数は 0 個以上 K 個以下の範囲で自由に選べます。強化薬の使用はダンジョンに入る前にのみ行え、冒険中に使用することはできません。

強化薬を使用する前の高橋君の戦闘力は S です。強化薬を j 個（0 \leq j \leq K）使用した場合、冒険開始時（階層 1 のモンスターと戦う前）の戦闘力は S + j となります。

高橋君が階層 N に到達できるような強化薬の使用個数の最小値を求めてください。K 個の強化薬をすべて使用しても階層 N に到達できない場合は -1 を出力してください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq S \leq 10^9
0 \leq K \leq 10^{18}
1 \leq E_i \leq 10^9（1 \leq i \leq N - 1）
入力はすべて整数である。

入力

N S K
E_1 E_2 \ldots E_{N-1}

1 行目には、ダンジョンの階層数を表す整数 N、高橋君の強化薬使用前の初期戦闘力を表す整数 S、強化薬の最大使用個数を表す整数 K が、スペース区切りで与えられる。
2 行目には、各階層のモンスターの強さを表す N - 1 個の整数 E_1, E_2, \ldots, E_{N-1} が、スペース区切りで与えられる。

出力

高橋君が階層 N に到達するために必要な強化薬の最小使用個数を 1 行で出力せよ。K 個の強化薬をすべて使用しても到達できない場合は -1 を出力せよ。

入力例 1

5 2 5
2 5 1 8

出力例 1

入力例 2

4 1 3
10 1 1

出力例 2

-1

入力例 3

8 1 1000000000000000000
3 8 12 5 20 50 100

出力例 3

Score : 300 pts

Problem Statement

Takahashi is attempting to conquer a dungeon.

This dungeon consists of N floors, each numbered from 1 to N from bottom to top. Takahashi starts on floor 1 (the bottommost floor). His goal is to reach floor N (the topmost floor).

On each floor i (1 \leq i \leq N - 1), a monster is waiting, and its strength is E_i. There is no monster on floor N.

Takahashi proceeds upward one floor at a time starting from floor 1. He cannot skip floors or go back. When Takahashi is on floor i (1 \leq i \leq N - 1), he must fight and defeat the monster on that floor before he can advance to the next floor i + 1.

Takahashi's combat power changes through battles. Let P be Takahashi's combat power at the time he fights the monster on floor i:

If P \geq E_i, Takahashi successfully defeats the monster and advances to floor i + 1. At this time, he absorbs the defeated monster's power, and his combat power becomes P + E_i.
If P < E_i, Takahashi is defeated by the monster and cannot proceed any further.

Before entering the dungeon, Takahashi can use "enhancement potions." Using one enhancement potion increases his combat power by 1. He can freely choose to use any number of potions from 0 to K inclusive. Enhancement potions can only be used before entering the dungeon and cannot be used during the adventure.

Takahashi's combat power before using any enhancement potions is S. If he uses j potions (0 \leq j \leq K), his combat power at the start of the adventure (before fighting the monster on floor 1) becomes S + j.

Find the minimum number of enhancement potions Takahashi needs to use in order to reach floor N. If he cannot reach floor N even after using all K enhancement potions, output -1.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq S \leq 10^9
0 \leq K \leq 10^{18}
1 \leq E_i \leq 10^9 (1 \leq i \leq N - 1)
All input values are integers.

Input

N S K
E_1 E_2 \ldots E_{N-1}

The first line contains three space-separated integers: N, the number of floors in the dungeon; S, Takahashi's initial combat power before using enhancement potions; and K, the maximum number of enhancement potions he can use.
The second line contains N - 1 space-separated integers E_1, E_2, \ldots, E_{N-1}, representing the strength of the monster on each floor.

Output

Output in a single line the minimum number of enhancement potions Takahashi needs to use in order to reach floor N. If he cannot reach floor N even after using all K enhancement potions, output -1.

Sample Input 1

5 2 5
2 5 1 8

Sample Output 1

Sample Input 2

4 1 3
10 1 1

Sample Output 2

-1

Sample Input 3

8 1 1000000000000000000
3 8 12 5 20 50 100

Sample Output 3

C - Watering the Flower Bed

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は N 個の区画からなる細長い花壇の管理を任されています。

各区画には 1 から N までの番号が付けられており、それぞれの区画 i（1 \leq i \leq N）には現在の土の水分量 A_i が記録されています。

高橋君は花壇に水をやるため、以下の操作を好きな回数（0 回でもよい）行うことができます。

1 \leq l \leq N - K + 1 を満たす整数 l を 1 つ選び、区画 l から区画 l + K - 1 までの連続する K 個の区画それぞれの水分量を 1 増加させる。

各回の操作で選ぶ l の値は自由に決めてよく、同じ値を複数回選ぶこともできます。なお、この操作では水分量を増加させることのみが可能であり、減少させることはできません。

高橋君は、すべての区画の水分量をちょうど目標値にしたいと考えています。具体的には、すべての i（1 \leq i \leq N）について、区画 i の水分量がちょうど B_i に等しい状態を達成したいです。各区画の水分量が目標値と一致しなければ、不足していても超過していても達成とはみなしません。

すべての区画の水分量をちょうど目標値にすることが可能かどうか判定し、可能な場合は必要な最小の操作回数を求めてください。

制約

1 \leq K \leq N \leq 3 \times 10^5
0 \leq A_i \leq 10^9
0 \leq B_i \leq 10^9
入力はすべて整数
目標値を達成可能な場合、最小の操作回数は 3 \times 10^{14} 以下であることが保証される（注：答えが32ビット整数の範囲を超える場合があります）

入力

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

1 行目には、区画の個数を表す整数 N と、1 回の操作で水分量を増加させる連続する区画の個数を表す整数 K が、スペース区切りで与えられる。
2 行目には、各区画の現在の水分量を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
3 行目には、各区画の目標の水分量を表す整数 B_1, B_2, \ldots, B_N が、スペース区切りで与えられる。

出力

すべての区画の水分量をちょうど目標値にすることが可能な場合は、必要な最小の操作回数を出力してください。不可能な場合は -1 を出力してください。出力は 1 行からなります。

入力例 1

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

出力例 1

入力例 2

3 2
0 0 0
0 1 0

出力例 2

-1

入力例 3

10 4
5 1 0 7 3 2 9 4 0 6
7 3 5 13 7 8 13 7 3 7

出力例 3

入力例 4

30 6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 4 8 10 10 12 13 12 11 11 15 10 10 13 10 10 11 12 11 12 14 15 10 10 10 6 4 1 1

出力例 4

入力例 5

1 1
0
1000000000

出力例 5

1000000000

Score : 366 pts

Problem Statement

Takahashi is in charge of managing a long, narrow flower bed consisting of N sections.

Each section is numbered from 1 to N, and for each section i (1 \leq i \leq N), the current soil moisture level A_i is recorded.

To water the flower bed, Takahashi can perform the following operation any number of times (possibly 0 times):

Choose an integer l satisfying 1 \leq l \leq N - K + 1, and increase the moisture level by 1 for each of the K consecutive sections from section l to section l + K - 1.

The value of l chosen in each operation can be freely decided, and the same value may be chosen multiple times. Note that this operation can only increase moisture levels; it cannot decrease them.

Takahashi wants to make the moisture level of every section exactly equal to its target value. Specifically, he wants to achieve a state where, for all i (1 \leq i \leq N), the moisture level of section i is exactly equal to B_i. If any section's moisture level does not match its target value, it is not considered achieved, whether it is below or above the target.

Determine whether it is possible to make the moisture level of every section exactly equal to its target value, and if so, find the minimum number of operations required.

Constraints

1 \leq K \leq N \leq 3 \times 10^5
0 \leq A_i \leq 10^9
0 \leq B_i \leq 10^9
All inputs are integers
When achieving the target values is possible, it is guaranteed that the minimum number of operations is at most 3 \times 10^{14} (Note: the answer may exceed the range of 32-bit integers)

Input

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

The first line contains the integer N representing the number of sections and the integer K representing the number of consecutive sections whose moisture levels are increased in one operation, separated by a space.
The second line contains the integers A_1, A_2, \ldots, A_N representing the current moisture levels of each section, separated by spaces.
The third line contains the integers B_1, B_2, \ldots, B_N representing the target moisture levels of each section, separated by spaces.

Output

If it is possible to make the moisture level of every section exactly equal to its target value, output the minimum number of operations required. If it is impossible, output -1. The output consists of a single line.

Sample Input 1

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

Sample Output 1

Sample Input 2

3 2
0 0 0
0 1 0

Sample Output 2

-1

Sample Input 3

10 4
5 1 0 7 3 2 9 4 0 6
7 3 5 13 7 8 13 7 3 7

Sample Output 3

Sample Input 4

30 6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 4 8 10 10 12 13 12 11 11 15 10 10 13 10 10 11 12 11 12 14 15 10 10 10 6 4 1 1

Sample Output 4

Sample Input 5

1 1
0
1000000000

Sample Output 5

1000000000

D - Hiking and Rest

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は山を登っている。登山道は N 個の区間に分かれており、高橋君の現在の標高は最初 0 である。

i 番目の区間（ i = 1, 2, \ldots, N ）を通過すると、標高が D_i だけ変化する（ D_i が正なら上り、負なら下り、 0 なら平坦を意味する）。ただし、標高は常に 0 以上であり、変化後の標高が負になる場合は 0 になる。すなわち、通過前の標高を h とすると、通過後の標高は \max(h + D_i,\ 0) となる。

高橋君は体力を温存するために、登山の途中で ちょうど 1 回「ロープウェイ」を利用しなければならない。ロープウェイを利用すると、現在の標高 h が即座に \lfloor h / 2 \rfloor（ h を 2 で割って小数点以下を切り捨てた値）に変わる。

ロープウェイを利用できるタイミングは以下の N + 1 箇所のうちいずれか 1 つである：

1 番目の区間の前
i 番目の区間と i+1 番目の区間の間（ i = 1, 2, \ldots, N-1 ）
N 番目の区間の後

高橋君は、全 N 個の区間の通過およびロープウェイの利用をすべて終えた後の標高を最小化したい。最適なタイミングでロープウェイを利用したときの、最終的な標高の最小値を求めよ。

制約

1 \leq N \leq 5 \times 10^5
-10^9 \leq D_i \leq 10^9
入力はすべて整数である。

入力

N
D_1 D_2 \ldots D_N

1 行目には、区間の個数を表す整数 N が与えられる。
2 行目には、各区間での標高の変化量を表す N 個の整数 D_1, D_2, \ldots, D_N がスペース区切りで与えられる。

出力

最適なタイミングでロープウェイをちょうど 1 回利用したときの、最終的な標高の最小値を 1 行で出力せよ。

入力例 1

5
3 4 -2 5 -6

出力例 1

入力例 2

4
-5 10 -3 2

出力例 2

入力例 3

12
8 -3 15 -20 7 0 12 -5 -30 25 -4 6

出力例 3

入力例 4

30
100 -40 25 -200 300 -150 0 80 -30 60 -500 400 10 -20 35 -5 -5 90 -100 250 -60 70 -10 -400 500 -250 125 -75 30 -15

出力例 4

入力例 5

1
1000000000

出力例 5

500000000

Score : 400 pts

Problem Statement

Takahashi is climbing a mountain. The trail is divided into N sections, and Takahashi's current altitude is initially 0.

When passing through the i-th section (i = 1, 2, \ldots, N), the altitude changes by D_i (positive D_i means ascending, negative means descending, and 0 means flat). However, the altitude is always non-negative, and if the altitude after the change would be negative, it becomes 0. That is, if the altitude before passing is h, the altitude after passing becomes \max(h + D_i,\ 0).

To conserve his energy, Takahashi must use a ropeway exactly once during the climb. When using the ropeway, the current altitude h instantly changes to \lfloor h / 2 \rfloor (the value obtained by dividing h by 2 and rounding down).

The ropeway can be used at exactly one of the following N + 1 points:

Before the 1st section
Between the i-th section and the (i+1)-th section (i = 1, 2, \ldots, N-1)
After the N-th section

Takahashi wants to minimize his altitude after completing all N sections and using the ropeway. Find the minimum possible final altitude when the ropeway is used at the optimal timing.

Constraints

1 \leq N \leq 5 \times 10^5
-10^9 \leq D_i \leq 10^9
All inputs are integers.

Input

N
D_1 D_2 \ldots D_N

The first line contains an integer N representing the number of sections.
The second line contains N integers D_1, D_2, \ldots, D_N separated by spaces, representing the altitude change for each section.

Output

Print in one line the minimum possible final altitude when the ropeway is used exactly once at the optimal timing.

Sample Input 1

5
3 4 -2 5 -6

Sample Output 1

Sample Input 2

4
-5 10 -3 2

Sample Output 2

Sample Input 3

12
8 -3 15 -20 7 0 12 -5 -30 25 -4 6

Sample Output 3

Sample Input 4

30
100 -40 25 -200 300 -150 0 80 -30 60 -500 400 10 -20 35 -5 -5 90 -100 250 -60 70 -10 -400 500 -250 125 -75 30 -15

Sample Output 4

Sample Input 5

1
1000000000

Sample Output 5

500000000

E - Mountain Range Vista

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は山岳写真家です。東西に一直線に連なる山脈があり、西から東へ順に 1 から N までの番号がついた N 個の山があります。山 i の標高は H_i です。

高橋君は Q 回の撮影を計画しています。各撮影 j では、山 L_j から山 R_j までの区間を対象とし、この区間を西側（左側）から眺めて写真を撮ります。

西側から山並みを眺めたとき、区間 [L_j, R_j] に含まれる山 k（L_j \le k \le R_j）が見えるとは、区間内でそれより西側にある山のうち、山 k より厳密に高いものが存在しないことを意味します。形式的には、L_j \le m < k かつ H_m > H_k を満たす m が存在しないとき、山 k は見えます。特に、区間の左端の山 L_j は常に見えます。

言い換えると、区間 [L_j, R_j] の標高の列を左から順に見ていき、その時点までの最大標高以上の標高をもつ山に出会うたびに数を 1 増やすとき、最終的な数が見える山の個数です。

各撮影について、見える山の個数を求めてください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq H_i \leq 10^9（1 \leq i \leq N）
1 \leq L_j < R_j \leq N（1 \leq j \leq Q）
入力はすべて整数である。

入力

N Q
H_1 H_2 \ldots H_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

1 行目には、山の数を表す整数 N とクエリの数を表す整数 Q が、スペース区切りで与えられる。
2 行目には、各山の標高を表す整数 H_1, H_2, \ldots, H_N がスペース区切りで与えられる。
3 行目から Q 行にわたり、各撮影の区間の左端 L_j と右端 R_j を表す整数がスペース区切りで与えられる。

出力

Q 行出力せよ。j 行目には、j 番目の撮影で見える山の個数を出力せよ。

入力例 1

出力例 1

入力例 2

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

出力例 2

入力例 3

12 10
5 1 5 7 3 7 8 2 8 6 9 4
1 12
1 4
2 7
3 9
4 10
5 12
6 9
7 11
8 12
10 12

出力例 3

入力例 4

40 25
12 7 15 15 3 20 18 20 25 1 25 24 30 5 6 30 29 31 31 2 40 35 40 41 10 9 42 42 8 50 49 50 51 11 52 52 4 60 59 60
1 40
1 10
1 20
5 25
10 30
15 40
2 39
3 8
6 13
9 16
11 23
14 28
17 33
20 37
21 40
22 32
24 35
26 38
28 40
30 40
31 36
33 39
34 40
36 38
38 40

出力例 4

入力例 5

2 1
1000000000 1000000000
1 2

出力例 5

Score : 466 pts

Problem Statement

Takahashi is a mountain photographer. There is a mountain range stretching in a straight line from west to east, consisting of N mountains numbered 1 to N from west to east. The elevation of mountain i is H_i.

Takahashi is planning Q photo shoots. For each photo shoot j, he targets the interval from mountain L_j to mountain R_j, and takes a photo viewing this interval from the west side (left side).

When viewing the mountain range from the west side, a mountain k (L_j \le k \le R_j) within the interval [L_j, R_j] is visible if there is no mountain to its west within the interval that is strictly taller than mountain k. Formally, mountain k is visible if there is no m satisfying L_j \le m < k and H_m > H_k. In particular, the leftmost mountain L_j of the interval is always visible.

In other words, if you scan the sequence of elevations in the interval [L_j, R_j] from left to right, incrementing a counter each time you encounter a mountain whose elevation is greater than or equal to the maximum elevation seen so far, the final count is the number of visible mountains.

For each photo shoot, determine the number of visible mountains.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq H_i \leq 10^9 (1 \leq i \leq N)
1 \leq L_j < R_j \leq N (1 \leq j \leq Q)
All input values are integers.

Input

N Q
H_1 H_2 \ldots H_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

The first line contains an integer N representing the number of mountains and an integer Q representing the number of queries, separated by a space.
The second line contains integers H_1, H_2, \ldots, H_N representing the elevation of each mountain, separated by spaces.
The following Q lines each contain integers representing the left endpoint L_j and right endpoint R_j of each photo shoot's interval, separated by a space.

Output

Output Q lines. On the j-th line, output the number of visible mountains in the j-th photo shoot.

Sample Input 1

Sample Output 1

Sample Input 2

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

Sample Output 2

Sample Input 3

12 10
5 1 5 7 3 7 8 2 8 6 9 4
1 12
1 4
2 7
3 9
4 10
5 12
6 9
7 11
8 12
10 12

Sample Output 3

Sample Input 4

40 25
12 7 15 15 3 20 18 20 25 1 25 24 30 5 6 30 29 31 31 2 40 35 40 41 10 9 42 42 8 50 49 50 51 11 52 52 4 60 59 60
1 40
1 10
1 20
5 25
10 30
15 40
2 39
3 8
6 13
9 16
11 23
14 28
17 33
20 37
21 40
22 32
24 35
26 38
28 40
30 40
31 36
33 39
34 40
36 38
38 40

Sample Output 4

Sample Input 5

2 1
1000000000 1000000000
1 2