DMOPC '19 Contest 7 P5 - Soriya's Programming Project

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 3.0s
Memory limit: 128M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

For her current programming project, Soriya needs to first construct the array a which has length N. However, to entertain herself, she decides to add the elements in the order described by the permutation p. That is, for her ith insertion, she will add the element a_{p_i} to its position in the array. Since Soriya has nothing better to do with her life, she wonders: how many inversions will the array a have after each insertion? An inversion is a pair of indices (i,j) such that 1\leq i< j\leq N and a_i>a_j.

Input Specification

The first line contains the positive integer N.
The second line consists of N positive integers, the array a_1,a_2,\ldots,a_N.
The third line consists of N positive integers, the permutation p_1,p_2,\ldots,p_N.

Output Specification

Output N lines, the ith of which containing a single integer, the number of inversions after Soriya adds her ith element

Constraints

In all subtasks,
1 \le N \le 500\,000
1 \le a_i,p_i \le N

Subtask 1 [15%]

p_i=i for 1\le i\le N

Subtask 2 [25%]

1 \le a_i \le 2

Subtask 3 [60%]

No additional constraints

Sample Input 1

5
4 3 1 2 3
1 2 3 4 5

Sample Output 1

0
1
3
5
6

Sample Input 2

5
4 3 1 2 3
3 5 1 4 2

Sample Output 2

0
0
2
3
6

Comments

There are no comments at the moment.