DMOPC '16 Contest 1 P5 - Blood Tubes - DMOJ: Modern Online Judge

DMOPC '16 Contest 1 P5 - Blood Tubes

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 0.6s

Memory limit: 64M

Author:

WallE256

Problem types

A few days back, Gigel had to take the yearly blood test which he had avoided for too long. While waiting to be pricked by the needle, he saw the nurse arranging blood tubes on a nearby table in a certain order. This helped him get through this struggle (as he is afraid of needles), since he came up with a problem to distract him. He quickly went home and wrote a draft for it:

A nice nurse brings you a permutation of $N$ ~N~ blood tubes numbered from $1$ ~1~ to $N$ ~N~. You need to place them on the table one by one and form a series with the minimum number of inversions. Each blood tube can only be placed at the beginning or the end of the blood tubes on the table. For example, if you have the blood tube $4$ ~4~ in your hand and the tubes $1\ 3\ 2$ ~1\ 3\ 2~ on the table, after you place it on the table, you can only have $4\ 1\ 3\ 2$ ~4\ 1\ 3\ 2~ or $1\ 3\ 2\ 4$ ~1\ 3\ 2\ 4~ as possible series. Considering $i$ ~i~ and $p_i$ ~p_i~ the element on the position $i$ ~i~, an inversion is when $i < j$ ~i < j~ and $p_i > p_j$ ~p_i > p_j~.

Gigel already knows the solution, but he likes seeing other people's approaches, so he asks you to try to solve this problem.

Input Specification

On the first line of input, you find $N$ ~N~ $(1 < N \le 500\,000)$ ~(1 < N \le 500\,000)~, and on the next line you find $N$ ~N~ space-separated integers which represent the initial permutation.

Output Specification

On the first line, you must print the minimum number of inversions.

Sample Input 1

4
2 1 3 4

Sample Output 1

Sample Input 2

4
2 1 4 3

Sample Output 2

Comments

2

fighterzhu commented on Oct. 11, 2016, 11:18 p.m.

Not sure what the inversion in the question refers to, could someone explain?

0

FatalEagle commented on Oct. 11, 2016, 11:40 p.m.

The definition is given in the problem statement. Additionally, you may consult wikipedia: https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)