/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
※ E 問題の問題文は C 問題と同じです。赤字で示された制約のみが異なります。
0 以上 M-1 以下の整数からなる整数列 A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_{N-1}) が与えられます。
A,B の長さはそれぞれ N,N-1 です。
A に対して以下の操作を好きな回数行うことができます。
- 1 以上 N 以下の整数 i を 1 つ選び、A_i に 1 を加える。
以下の条件を満たすようにするために必要な操作回数の最小値を求めてください。
なお、問題の制約下では、必ず条件を満たすようにできることが証明できます。
- i=1,2,\dots,N-1 について、A_i+A_{i+1} を M で割った余りは B_i に等しい。
制約
- 2 \leq N \leq 2 \times 10^5
- 3 \leq M \leq 10^9
- 0 \leq A_i \leq M-1
- 0 \leq B_i \leq M-1
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_{N-1}
出力
答えを 1 行で出力せよ。
入力例 1
3 10 4 6 7 5 5
出力例 1
5
1 回目の操作で i=2 を選ぶと、A=(4,7,7) となります。
2 回目の操作で i=1 を選ぶと、A=(5,7,7) となります。
3 回目の操作で i=1 を選ぶと、A=(6,7,7) となります。
4 回目の操作で i=2 を選ぶと、A=(6,8,7) となります。
5 回目の操作で i=1 を選ぶと、A=(7,8,7) となります。
A_1+A_2=7+8=15,\;A_2+A_3=8+7=15 なので、条件を満たします。
また、4 回以下の操作で条件を満たすようにはできないため、答えは 5 です。
入力例 2
2 3 1 2 2
出力例 2
2
入力例 3
10 10 0 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1
出力例 3
40
Score : 450 points
Problem Statement
The problem statement of Problem E is the same as Problem C. Only the constraint shown in red differ.
You are given integer sequences A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_{N-1}) consisting of integers between 0 and M-1, inclusive.
The lengths of A and B are N and N-1, respectively.
You can perform the following operation on A any number of times.
- Choose an integer i with 1 \leq i \leq N, and add 1 to A_i.
Find the minimum number of operations required to satisfy the following condition.
It can be proved that the condition can always be satisfied under the constraints of this problem.
- For i=1,2,\dots,N-1, the remainder when A_i+A_{i+1} is divided by M equals B_i.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 3 \leq M \leq 10^9
- 0 \leq A_i \leq M-1
- 0 \leq B_i \leq M-1
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_{N-1}
Output
Output the answer on one line.
Sample Input 1
3 10 4 6 7 5 5
Sample Output 1
5
If we choose i=2 for the first operation, we get A=(4,7,7).
If we choose i=1 for the second operation, we get A=(5,7,7).
If we choose i=1 for the third operation, we get A=(6,7,7).
If we choose i=2 for the fourth operation, we get A=(6,8,7).
If we choose i=1 for the fifth operation, we get A=(7,8,7).
Since A_1+A_2=7+8=15 and A_2+A_3=8+7=15, the condition is satisfied.
The condition cannot be satisfied with four or fewer operations, so the answer is 5.
Sample Input 2
2 3 1 2 2
Sample Output 2
2
Sample Input 3
10 10 0 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1
Sample Output 3
40