AtCoder Weekday Contest 0006 Beta

A - 的当てゲーム

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

配点 : 200 点

問題文

高橋君は夏祭りの的当てゲームに挑戦しています。

高橋君の前には N 個のボールが用意されています。各ボールはそれぞれ重さが異なり、 i 番目のボールの重さは D_i です。高橋君がボールを投げると、ボールの重さに比例した距離だけ飛びます。具体的には、重さが D のボールを投げると、ちょうど距離 D だけ飛びます。

的は高橋君から距離 L の位置に設置されています。的には幅があり、高橋君からの距離が L - W 以上 L + W 以下の範囲にボールが落ちれば、的に当たったとみなされます。

高橋君が N 個のボールをすべて 1 つずつ投げたとき、的に当たるボールの数を求めてください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq W \leq L \leq 10^9
1 \leq D_i \leq 10^9 (1 \leq i \leq N)
D_i はすべて異なる
入力はすべて整数

入力

N L W
D_1 D_2 \ldots D_N

1 行目には、ボールの個数を表す N 、的までの距離を表す L 、的の幅に関する値 W が、スペース区切りで与えられる。
2 行目には、各ボールの重さを表す D_1, D_2, \ldots, D_N が、スペース区切りで与えられる。

出力

的に当たるボールの数を 1 行で出力せよ。

入力例 1

5 10 3
5 8 10 13 15

出力例 1

入力例 2

4 50 5
1 10 30 100

出力例 2

入力例 3

10 100 20
50 79 80 95 100 120 121 150 200 60

出力例 3

入力例 4

20 500000000 100000000
1 100000000 399999999 400000000 400000001 450000000 500000000 550000000 599999999 600000000 600000001 700000000 800000000 999999999 1000000000 250000000 123456789 500000001 499999999 350000000

出力例 4

入力例 5

1 1 1
1

出力例 5

Score : 200 pts

Problem Statement

Takahashi is playing a target shooting game at a summer festival.

In front of Takahashi, N balls are prepared. Each ball has a different weight, and the weight of the i-th ball is D_i. When Takahashi throws a ball, it flies a distance proportional to its weight. Specifically, when a ball of weight D is thrown, it flies exactly a distance of D.

A target is placed at distance L from Takahashi. The target has some width, and a ball is considered to have hit the target if it lands at a distance from Takahashi that is at least L - W and at most L + W.

When Takahashi throws all N balls one by one, find the number of balls that hit the target.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq W \leq L \leq 10^9
1 \leq D_i \leq 10^9 (1 \leq i \leq N)
All D_i are distinct
All inputs are integers

Input

N L W
D_1 D_2 \ldots D_N

The first line contains N representing the number of balls, L representing the distance to the target, and W representing the value related to the target's width, separated by spaces.
The second line contains D_1, D_2, \ldots, D_N representing the weight of each ball, separated by spaces.

Output

Output the number of balls that hit the target in one line.

Sample Input 1

5 10 3
5 8 10 13 15

Sample Output 1

Sample Input 2

4 50 5
1 10 30 100

Sample Output 2

Sample Input 3

10 100 20
50 79 80 95 100 120 121 150 200 60

Sample Output 3

Sample Input 4

20 500000000 100000000
1 100000000 399999999 400000000 400000001 450000000 500000000 550000000 599999999 600000000 600000001 700000000 800000000 999999999 1000000000 250000000 123456789 500000001 499999999 350000000

Sample Output 4

Sample Input 5

1 1 1
1

Sample Output 5

B - 効率の良いクエスト

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

配点 : 233 点

問題文

高橋君は RPG ゲームを遊んでいます。このゲームには N 個のクエストがあり、i 番目のクエスト (1 \leq i \leq N) には消費スタミナ D_i と獲得経験値 R_i が設定されています。各クエストはクリアしないか、1回だけクリアするかのいずれかを選べます。

高橋君は「効率の良いクエストだけをクリアする」というプレイスタイルを持っています。高橋君にとって効率の良いクエストとは、獲得経験値が消費スタミナの K 倍以上であるクエスト、すなわち R_i \geq K \times D_i を満たすクエストのことです。ここで K は高橋君が定めた効率の基準倍率です。

高橋君はこのプレイスタイルに従い、効率の良いクエストをすべてクリアし、それ以外のクエストは一切クリアしません。

高橋君がこのプレイスタイルに従ったとき、クリアしたクエストから得られる獲得経験値の合計が目標経験値 T 以上になるかどうかを判定してください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq K \leq 100
1 \leq T \leq 10^{18}
1 \leq D_i \leq 10^4
1 \leq R_i \leq 10^9
入力はすべて整数

入力

N K T
D_1 R_1
D_2 R_2
\vdots
D_N R_N

1 行目には、クエストの数 N 、効率の基準倍率 K 、目標経験値 T が、スペース区切りで与えられる。
2 行目から N + 1 行目では、各クエストの情報が与えられる。
1 + i 行目には、i 番目のクエストの消費スタミナ D_i と獲得経験値 R_i が、スペース区切りで与えられる。

出力

高橋君が効率の良いクエストをすべてクリアしたとき、獲得経験値の合計が目標経験値 T 以上になるならば Yes を、そうでなければ No を出力せよ。

入力例 1

出力例 1

No

入力例 2

出力例 2

No

入力例 3

8 5 1000000000
100 600
200 1000
500 2500
1000 5000
300 1000
150 900
400 2000
250 1500

出力例 3

No

Score : 233 pts

Problem Statement

Takahashi is playing an RPG game. The game has N quests, and the i-th quest (1 \leq i \leq N) has a stamina cost of D_i and an experience reward of R_i. For each quest, he can choose either not to clear it or to clear it exactly once.

Takahashi has a playstyle of "only clearing efficient quests." For Takahashi, an efficient quest is one whose experience reward is at least K times its stamina cost, that is, a quest satisfying R_i \geq K \times D_i. Here, K is the efficiency threshold multiplier set by Takahashi.

Following this playstyle, Takahashi clears all efficient quests and does not clear any other quests.

Determine whether the total experience gained from the quests Takahashi clears following this playstyle is at least the target experience T.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq K \leq 100
1 \leq T \leq 10^{18}
1 \leq D_i \leq 10^4
1 \leq R_i \leq 10^9
All inputs are integers

Input

N K T
D_1 R_1
D_2 R_2
\vdots
D_N R_N

The first line contains the number of quests N, the efficiency threshold multiplier K, and the target experience T, separated by spaces.
From the 2nd line to the (N + 1)-th line, the information for each quest is given.
The (1 + i)-th line contains the stamina cost D_i and the experience reward R_i of the i-th quest, separated by spaces.

Output

If the total experience gained when Takahashi clears all efficient quests is at least the target experience T, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

No

Sample Input 2

Sample Output 2

No

Sample Input 3

8 5 1000000000
100 600
200 1000
500 2500
1000 5000
300 1000
150 900
400 2000
250 1500

Sample Output 3

No

C - エアコンの温度調整

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

配点 : 300 点

問題文

高橋君はオフィスビルの管理人です。夏の暑い日、各部屋のエアコンが故障してしまい、部屋の温度が上がりすぎてしまいました。

ビルには N 個の部屋があり、部屋 i (1 \leq i \leq N) の現在の室温は T_i 度です。社員が快適に仕事できるよう、すべての部屋の温度を目標温度 M 度以下にする必要があります。

高橋君は冷却パックを必要なだけいくつでも使うことができます。冷却パック 1 個を使うと、選んだ 1 つの部屋の温度をちょうど D 度下げることができます。冷却パックは部分的に使うことはできず、1 個あたり必ず D 度ちょうど下がります。同じ部屋に対して冷却パックを複数個使うこともでき、その結果として部屋の温度が M 度を大きく下回ったり、負の値になったりしても構いません。

すべての部屋の温度を M 度以下にするために必要な冷却パックの最小個数を求めてください。

制約

1 \leq N \leq 10^5
0 \leq M \leq 10^9
1 \leq D \leq 10^9
0 \leq T_i \leq 10^9 (1 \leq i \leq N)
入力はすべて整数

入力

N M D
T_1 T_2 \ldots T_N

1 行目には、部屋の個数を表す整数 N 、目標温度を表す整数 M 、冷却パック 1 個で下げられる温度を表す整数 D が、スペース区切りで与えられる。
2 行目には、各部屋の現在の温度を表す整数 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。

出力

すべての部屋の温度を M 度以下にするために必要な冷却パックの最小個数を整数で 1 行に出力してください。

入力例 1

3 25 5
30 28 20

出力例 1

入力例 2

5 20 3
35 20 29 18 25

出力例 2

入力例 3

10 100 7
150 99 200 100 85 163 101 50 120 142

出力例 3

Score : 300 pts

Problem Statement

Takahashi is the building manager of an office building. On a hot summer day, the air conditioner in each room has broken down, causing the room temperatures to rise too high.

The building has N rooms, and the current temperature of room i (1 \leq i \leq N) is T_i degrees. To ensure employees can work comfortably, the temperature of every room must be brought to at most the target temperature of M degrees.

Takahashi can use as many cooling packs as needed. Using 1 cooling pack lowers the temperature of one chosen room by exactly D degrees. A cooling pack cannot be used partially; each pack always lowers the temperature by exactly D degrees. Multiple cooling packs can be used on the same room, and it is acceptable if a room's temperature drops well below M degrees or even becomes negative as a result.

Find the minimum number of cooling packs needed to bring the temperature of every room to M degrees or below.

Constraints

1 \leq N \leq 10^5
0 \leq M \leq 10^9
1 \leq D \leq 10^9
0 \leq T_i \leq 10^9 (1 \leq i \leq N)
All inputs are integers

Input

N M D
T_1 T_2 \ldots T_N

The first line contains three space-separated integers: N representing the number of rooms, M representing the target temperature, and D representing the temperature decrease per cooling pack.
The second line contains space-separated integers T_1, T_2, \ldots, T_N representing the current temperature of each room.

Output

Print a single integer on one line: the minimum number of cooling packs needed to bring the temperature of every room to M degrees or below.

Sample Input 1

3 25 5
30 28 20

Sample Output 1

Sample Input 2

5 20 3
35 20 29 18 25

Sample Output 2

Sample Input 3

10 100 7
150 99 200 100 85 163 101 50 120 142

Sample Output 3

D - 警備員の配置

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

配点 : 400 点

問題文

高橋君は、直線状に並んだ N 個の区画（区画 1 から区画 N まで）からなる長い廊下の警備計画を立てています。すべての区画に警備が行き届くようにしなければなりません。

高橋君は M 人の警備員候補を集めました。各警備員候補 i （ 1 \leq i \leq M ）は、区画 L_i から区画 R_i までの連続する範囲を担当することができます。つまり、警備員候補 i を配置すると、区画 L_i, L_i + 1, \ldots, R_i のすべてに警備が行き届きます。

高橋君は、 N 個すべての区画に警備が行き届くようにしたいと考えています。具体的には、 M 人の警備員候補の中から何人かを選び、選んだ警備員たちが担当する区画の集合の和集合が \{1, 2, \ldots, N\} と一致するようにしたいです。ただし、各警備員候補は選ぶか選ばないかの二択であり、同じ候補を複数回選ぶことはできません。

このとき、配置する警備員の人数の最小値を求めてください。ただし、どのように警備員を選んでもすべての区画に警備を行き届かせることが不可能な場合は、 -1 を出力してください。

制約

1 \leq N \leq 10^9
1 \leq M \leq 2 \times 10^5
1 \leq L_i \leq R_i \leq N （ 1 \leq i \leq M ）
入力はすべて整数である

入力

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

1 行目には、区画の数を表す整数 N と、警備員候補の数を表す整数 M が、空白区切りで与えられる。
2 行目から M + 1 行目では、各警備員候補が担当できる区画の範囲が与えられる。
i + 1 行目（ 1 \leq i \leq M ）では、警備員候補 i が担当できる区画の範囲の左端 L_i と右端 R_i が、空白区切りで与えられる。

出力

すべての区画に警備を行き届かせるために必要な警備員の最小人数を 1 行で出力してください。不可能な場合は -1 を出力してください。

入力例 1

出力例 1

入力例 2

出力例 2

-1

入力例 3

1000000000 5
1 300000000
200000000 500000000
400000000 700000000
600000000 900000000
800000000 1000000000

出力例 3

Score : 400 pts

Problem Statement

Takahashi is creating a security plan for a long corridor consisting of N sections (from section 1 to section N) arranged in a straight line. He must ensure that all sections are covered by security.

Takahashi has gathered M guard candidates. Each guard candidate i (1 \leq i \leq M) can cover a contiguous range from section L_i to section R_i. That is, if guard candidate i is assigned, sections L_i, L_i + 1, \ldots, R_i are all covered.

Takahashi wants all N sections to be covered. Specifically, he wants to select some of the M guard candidates such that the union of the sections covered by the selected guards equals \{1, 2, \ldots, N\}. Each guard candidate can either be selected or not selected; the same candidate cannot be selected more than once.

Find the minimum number of guards that need to be assigned. If it is impossible to cover all sections regardless of how the guards are selected, output -1.

Constraints

1 \leq N \leq 10^9
1 \leq M \leq 2 \times 10^5
1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
All inputs are integers

Input

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

The first line contains an integer N representing the number of sections and an integer M representing the number of guard candidates, separated by a space.
From the 2nd line to the (M + 1)-th line, the range of sections each guard candidate can cover is given.
The (i + 1)-th line (1 \leq i \leq M) contains the left endpoint L_i and right endpoint R_i of the range of sections that guard candidate i can cover, separated by a space.

Output

Output in a single line the minimum number of guards needed to cover all sections. If it is impossible, output -1.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

-1

Sample Input 3

1000000000 5
1 300000000
200000000 500000000
400000000 700000000
600000000 900000000
800000000 1000000000

Sample Output 3

E - 店舗売上管理

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

配点 : 433 点

問題文

高橋君は、全国にチェーン展開する小売企業の本部で働いています。この企業では、各店舗の売上を一元管理するシステムを運用しています。

全国には N 店舗があり、それぞれ 1 から N までの店舗番号が付けられています。各店舗 i (1 \leq i \leq N) には、初期の売上額 S_i が記録されています。

高橋君は、経営分析のため、以下の 2 種類のクエリを合計 Q 回、与えられた順に処理する必要があります。

タイプ 1（1 L R）：店舗番号が L 以上 R 以下であるすべての店舗の売上額の合計、すなわち S_L + S_{L+1} + \cdots + S_R を出力する。
タイプ 2（2 X V）：店舗 X の売上額 S_X を V に上書きする。すなわち、S_X \leftarrow V とする。

各タイプ 1 のクエリでは、それ以前のすべてのタイプ 2 のクエリによる変更が反映された状態での売上額の合計を求めます。

高橋君の代わりに、各タイプ 1 のクエリに対する答えを求めてください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
0 \leq S_i \leq 10^9 (1 \leq i \leq N)
タイプ 1 のクエリについて：1 \leq L \leq R \leq N
タイプ 2 のクエリについて：1 \leq X \leq N, 0 \leq V \leq 10^9
タイプ 1 のクエリは 1 つ以上存在する
入力はすべて整数
タイプ 1 のクエリの答えは 64 ビット符号付き整数型に収まることが保証される

入力

N Q
S_1 S_2 \ldots S_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

1 行目には、店舗の数 N とクエリの数 Q が、スペース区切りで与えられる。
2 行目には、各店舗の初期売上額 S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
続く Q 行に、Q 個のクエリが 1 行ずつ与えられる。各クエリは先頭の整数でタイプが区別され、i 番目のクエリ \mathrm{query}_i は以下のいずれかの形式で与えられる。
タイプ 1 の場合：1 L R（店舗番号 L 以上 R 以下の売上額の合計を求める）
タイプ 2 の場合：2 X V（店舗 X の売上額を V に上書きする）

出力

タイプ 1 のクエリが処理されるたびに、対応する売上額の合計を 1 行に出力せよ。

入力例 1

5 4
10 20 30 40 50
1 1 3
2 2 100
1 1 3
1 2 5

出力例 1

60
140
220

入力例 2

8 7
100 200 300 400 500 600 700 800
1 1 8
1 3 6
2 4 1000
1 3 6
2 1 0
1 1 4
1 1 1

出力例 2

入力例 3

10 12
1000000000 500000000 300000000 200000000 100000000 50000000 25000000 12500000 6250000 3125000
1 1 10
1 1 5
2 1 0
1 1 10
2 5 999999999
1 4 7
2 3 0
2 4 0
1 1 10
1 10 10
2 10 1000000000
1 9 10

出力例 3

Score : 433 pts

Problem Statement

Takahashi works at the headquarters of a retail company that operates a chain of stores nationwide. The company runs a system that centrally manages the sales of each store.

There are N stores nationwide, each assigned a store number from 1 to N. For each store i (1 \leq i \leq N), an initial sales amount S_i is recorded.

For business analysis, Takahashi needs to process a total of Q queries of the following 2 types, in the given order.

Type 1 (1 L R): Output the total sales amount of all stores whose store numbers are between L and R inclusive, that is, S_L + S_{L+1} + \cdots + S_R.
Type 2 (2 X V): Overwrite the sales amount S_X of store X with V. That is, set S_X \leftarrow V.

For each Type 1 query, the total sales amount should be computed with all changes from previous Type 2 queries already applied.

Please find the answer to each Type 1 query on behalf of Takahashi.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
0 \leq S_i \leq 10^9 (1 \leq i \leq N)
For Type 1 queries: 1 \leq L \leq R \leq N
For Type 2 queries: 1 \leq X \leq N, 0 \leq V \leq 10^9
There is at least 1 Type 1 query
All input values are integers
It is guaranteed that the answers to Type 1 queries fit in a 64-bit signed integer type

Input

N Q
S_1 S_2 \ldots S_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

The first line contains the number of stores N and the number of queries Q, separated by a space.
The second line contains the initial sales amounts S_1, S_2, \ldots, S_N of each store, separated by spaces.
The following Q lines each contain one of the Q queries. Each query is distinguished by the leading integer indicating its type. The i-th query \mathrm{query}_i is given in one of the following formats:
Type 1: 1 L R (compute the total sales amount of stores with numbers from L to R inclusive)
Type 2: 2 X V (overwrite the sales amount of store X with V)

Output

Each time a Type 1 query is processed, output the corresponding total sales amount on a single line.

Sample Input 1

5 4
10 20 30 40 50
1 1 3
2 2 100
1 1 3
1 2 5

Sample Output 1

60
140
220

Sample Input 2

8 7
100 200 300 400 500 600 700 800
1 1 8
1 3 6
2 4 1000
1 3 6
2 1 0
1 1 4
1 1 1

Sample Output 2

Sample Input 3

10 12
1000000000 500000000 300000000 200000000 100000000 50000000 25000000 12500000 6250000 3125000
1 1 10
1 1 5
2 1 0
1 1 10
2 5 999999999
1 4 7
2 3 0
2 4 0
1 1 10
1 10 10
2 10 1000000000
1 9 10

Sample Output 3