시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB | 195 | 92 | 86 | 49.425% |
Maximizer has two permutations $A=[a_1,a_2,\cdots,a_N]$ and $B=[b_1,b_2,\cdots,b_N]$. Both $A, B$ have length $N$ and consists of distinct integers from $1$ to $N$.
Maximizer wants to maximize the sum of differences of each element, $\sum_{i=1}^{N} |a_i - b_i|$. But he can only swap two adjacent elements in $A$. Precisely, he can only swap $a_i$ and $a_{i+1}$ for some $i$ from $1$ to $N-1$. He can swap as many times as he wants.
What is the minimum number of swaps required for maximizing the difference sum?
The first line contains an integer $N$. ($1 \leq N \leq 250\,000$)
The second line contains $N$ integers $a_1,a_2,\cdots,a_N$ ($1 \leq a_i \leq N$).
The third line contains $N$ integers $b_1,b_2,\cdots,b_N$ ($1 \leq b_i \leq N$).
Each of $[a_1,a_2,\cdots,a_N]$ and $[b_1,b_2,\cdots,b_N]$ is a permutation. In other words, it is consisted of distinct integers from $1$ to $N$.
Print an integer, the minimum number of swaps required for maximizing the difference sum.
3 1 2 3 1 2 3
2
4 3 4 1 2 3 2 4 1
3
University > KAIST > 2019 KAIST 9th ICPC Mock Competition H번
Contest > Open Cup > 2019/2020 Season > Stage 5: Grand Prix of Korea H번