/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 425 点
問題文
1 周の長さが M である池があり、その周上に 1 つの小屋と N 人の人が立っています。
実数 x (0\leq x <M) について、小屋から時計回りに x だけ進んだところを地点 x と定義します。
i 番目の人は、 地点 A_i にいます。
複数の人が同じ場所に立っていることもあります。
また、N 以下の整数 C が与えられます。 i=0,1,\ldots,M-1 について、X_i を次のように定義します。
- 高橋君は地点 (i+0.5) からスタートして、時計回りに動き始める。
- 高橋君は出会った人数の合計が C 未満である限り（時計回りに）動き続け、C 以上になったら止まる。ここで、「地点 y にいる人と出会う」とは、高橋君が地点 y に到達することを指す。
- 高橋君が止まるまでに出会った人数を X_i とする。ここで、高橋君が止まった地点に複数の人がいる場合、そこにいた人はすべて出会った人として数えられ、特に X_i は C より大きくなる可能性がある。
i=0,1,\ldots,M-1 にわたる X_i の総和、すなわち \displaystyle\sum_{i=0}^{M-1} X_i を求めてください。
制約
- 1\leq N\leq 5\times 10^5
- 1\leq M\leq 10^{12}
- 0\leq A_i\leq M-1
- 1\leq C\leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M C A_1 A_2 \ldots A_N
出力
i=0,1,\ldots,M-1 にわたる X_i の総和を一行に出力せよ。
入力例 1
5 3 2 1 2 1 0 1
出力例 1
9
i=0 のとき、高橋君は地点 0.5 からスタートして時計回りに動きます。その後、次のようになります。
- 地点 1 で 1,3,5 番目の 3 人と出会い、今まで出会った人数の合計は 3 となる。これは C=2 以上であるため、高橋くんはそこで止まる。よって、X_0=3 である。
i=1 のとき、高橋君は地点 1.5 からスタートして時計回りに動きます。その後、次のようになります。
- 地点 2 で 2 番目の人と出会う。今まで出会った人数の合計は 1 であるため、動き続ける。
- 地点 0 で 4 番目の人と出会い、今まで出会った人数の合計は 2 となる。これは C=2 以上であるため、高橋くんはそこで止まる。よって、X_1=2 である。
i=2 のとき、高橋君は地点 2.5 からスタートして時計回りに動きます。その後、次のようになります。
- 地点 0 で 4 番目の人と会う。今まで出会った人数の合計は 1 であるため、動き続ける。
- 地点 1 で 1,3,5 番目の 3 人と会い、今まで出会った人数の合計は 4 となる。これは C=2 以上であるため、高橋くんはそこで止まる。よって、X_2=4 である。
よって、答えは X_0+X_1+X_2=3+2+4=9 となります。
入力例 2
1 1000000000000 1 1
出力例 2
1000000000000
高橋君はスタートする位置によらず、池の周りに立っている唯一の人である、地点 1 にいる人に出会った時に止まります。
よって、i によらず X_i=1 であり、答えは 10^{12} となります。
Score : 425 points
Problem Statement
There is a pond with a circumference of M, and on its shore stand one hut and N people.
For a real number x (0\leq x <M), define point x as the location that is x distance clockwise from the hut.
The i-th person is at point A_i.
Multiple people may be standing at the same location.
Additionally, an integer C not greater than N is given. For i=0,1,\ldots,M-1, define X_i as follows:
- Takahashi starts at point (i+0.5) and begins moving clockwise.
- Takahashi continues moving (clockwise) as long as the total number of people he has met is less than C, and stops when it becomes C or more. Here, "meeting a person at point y" means that Takahashi reaches point y.
- Let X_i be the number of people Takahashi met before stopping. Here, if there are multiple people at the point where Takahashi stopped, all the people there are counted as people he met, and particularly, X_i may be greater than C.
Find the sum of X_i over i=0,1,\ldots,M-1, that is, \displaystyle\sum_{i=0}^{M-1} X_i.
Constraints
- 1\leq N\leq 5\times 10^5
- 1\leq M\leq 10^{12}
- 0\leq A_i\leq M-1
- 1\leq C\leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M C A_1 A_2 \ldots A_N
Output
Print the sum of X_i over i=0,1,\ldots,M-1 on a single line.
Sample Input 1
5 3 2 1 2 1 0 1
Sample Output 1
9
When i=0, Takahashi starts at point 0.5 and moves clockwise. Then, the following happens:
- At point 1, he meets the 1st, 3rd, and 5th people, a total of three people, and the total number of people met so far is 3. This is not less than C=2, so Takahashi stops there. Therefore, X_0=3.
When i=1, Takahashi starts at point 1.5 and moves clockwise. Then, the following happens:
- At point 2, he meets the 2nd person. The total number of people met so far is 1, so he continues moving.
- At point 0, he meets the 4th person, and the total number of people met so far is 2. This is not less than C=2, so Takahashi stops there. Therefore, X_1=2.
When i=2, Takahashi starts at point 2.5 and moves clockwise. Then, the following happens:
- At point 0, he meets the 4th person. The total number of people met so far is 1, so he continues moving.
- At point 1, he meets the 1st, 3rd, and 5th people, a total of three people, and the total number of people met so far is 4. This is not less than C=2, so Takahashi stops there. Therefore, X_2=4.
Therefore, the answer is X_0+X_1+X_2=3+2+4=9.
Sample Input 2
1 1000000000000 1 1
Sample Output 2
1000000000000
Regardless of the starting position, Takahashi stops when he meets the only person standing around the pond, who is at point 1.
Therefore, X_i=1 regardless of i, and the answer is 10^{12}.