/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
長さ N の 2 つの数列 A=(A_1,\ldots,A_N), B=(B_1,\ldots,B_N) が与えられます。
数列 C を、空の数列から始めて、i=1,2,\ldots,N の順に、C の末尾に B_i を A_i 個追加することで得られる長さ \sum_{i=1}^N A_i の数列とします。
C の転倒数を求めてください。
転倒数とは
数列 C = (C_1, C_2, \dots, C_M) の転倒数とは、1 \leq i < j \leq M かつ C_i > C_j を満たす添字の組 (i, j) の個数のことです。制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^3
- 1 \leq B_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
出力
答えを出力せよ。
入力例 1
3 4 1 2 10 30 20
出力例 1
2
数列 C は (10,10,10,10,30,20,20) となります。転倒数は 2 です。
入力例 2
4 1000 1000 1000 1000 1 1 1 1
出力例 2
0
数列 C の転倒数は 0 です。
入力例 3
13 3 1 4 1 5 9 2 6 5 3 5 8 9 2 7 1 8 2 8 1 7 2 7 4 5 9
出力例 3
499
Problem Statement
You are given two sequences A=(A_1,\ldots,A_N) and B=(B_1,\ldots,B_N) of length N.
Define a sequence C as the one obtained by starting with an empty sequence and appending A_i copies of B_i, resulting in a length of \sum_{i=1}^N A_i.
Find the inversion number of C.
What is inversion number?
The inversion number of the sequence C = (C_1, C_2, \dots, C_M) is defined as the number of pairs of indices (i, j) such that 1 \leq i < j \leq M and C_i > C_j.Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^3
- 1 \leq B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
Output
Print the answer.
Sample Input 1
3 4 1 2 10 30 20
Sample Output 1
2
The sequence C is (10,10,10,10,30,20,20), whose inversion number is 2.
Sample Input 2
4 1000 1000 1000 1000 1 1 1 1
Sample Output 2
0
The inversion number of C is 0.
Sample Input 3
13 3 1 4 1 5 9 2 6 5 3 5 8 9 2 7 1 8 2 8 1 7 2 7 4 5 9
Sample Output 3
499