G - K-th element

Contest Duration: 2021-09-18(Sat) 04:00 - 2021-09-18(Sat) 09:00 (local time) (300 minutes) Back to Home

G - K-th element Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $6$ 点

注意

この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

数列が $N$ 個あり、 $i$ 番目の数列は長さ $A_i$ , 初項 $B_i$ , 公差 $C_i$ の等差数列です。
$N$ 個の数列を全て連結して $1$ つの数列にしたとき、小さい方から $K$ 番目の要素を答えてください。

制約

$2 \leq N \leq 10^5$
$1 \leq A_i \leq 10^9$
$1 \leq B_i \leq 10^9$
$1 \leq C_i \leq 10^9$
$\displaystyle 1 \leq K \leq \sum_{i=1}^N A_i$
入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $K$ 
 $A_1$   $B_1$   $C_1$ 
 $\vdots$ 
 $A_N$   $B_N$   $C_N$

出力

連結した数列の小さい方から $K$ 番目の要素を出力せよ。

入力例 1Copy

Copy

2 4
3 2 2
2 3 4

出力例 1Copy

Copy

$1$ 番目の数列は $(2, 4, 6)$ 、 $2$ 番目の数列は $(3, 7)$ なので、この二つの数列を連結すると $(2, 4, 6, 3, 7)$ になります。
よって $4$ 番目に小さい要素は $6$ となります。

入力例 2Copy

Copy

2 10
4 1000000000 1000000000
6 1000000000 1000000000

出力例 2Copy

Copy

6000000000

答えが $32$ bit 整数に収まらない可能性があることに注意してください。

入力例 3Copy

Copy

出力例 3Copy

Copy

Score : $6$ points

Warning

Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have $N$ sequences of numbers. The $i$ -th of them is an arithmetic progression of length $A_i$ with the initial term $B_i$ and the common difference $C_i$ .
If all these $N$ sequences are concatenated into one sequence, what is the $K$ -th smallest element of that sequence?

Constraints

$2 \leq N \leq 10^5$
$1 \leq A_i \leq 10^9$
$1 \leq B_i \leq 10^9$
$1 \leq C_i \leq 10^9$
$\displaystyle 1 \leq K \leq \sum_{i=1}^N A_i$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $K$ 
 $A_1$   $B_1$   $C_1$ 
 $\vdots$ 
 $A_N$   $B_N$   $C_N$

Output

Print the $K$ -th smallest element of the sequence after the concatenation.

Sample Input 1Copy

Copy

2 4
3 2 2
2 3 4

Sample Output 1Copy

Copy

The first sequence is $(2, 4, 6)$ , and the second sequence is $(3, 7)$ , so we have $(2, 4, 6, 3, 7)$ after the concatenation.
Therefore, the fourth smallest element is $6$ .

Sample Input 2Copy

Copy

2 10
4 1000000000 1000000000
6 1000000000 1000000000

Sample Output 2Copy

Copy

6000000000

Note that the answer may not fit into a $32$ -bit integer.

Sample Input 3Copy

Copy

Sample Output 3Copy

Copy