
USACO 2020 US Open Contest, Gold
Problem 1. Haircut
Contest has ended.

Log in to allow submissions in analysis mode
Tired of his stubborn cowlick, Farmer John decides to get a haircut. He has N
(1≤N≤105) strands of hair arranged in a line, and strand i is
initially Ai micrometers long (0≤Ai≤N). Ideally, he wants his hair
to be monotonically increasing in length, so he defines the "badness" of his
hair as the number of inversions: pairs (i,j) such that i<j and
Ai>Aj.
Contest has ended. No further submissions allowed.
For each of j=0,1,…,N−1, FJ would like to know the badness of his hair if all strands with length greater than j are decreased to length exactly j.
(Fun fact: the average human head does indeed have about 105 hairs!)
INPUT FORMAT (file haircut.in):
The first line contains N.The second line contains A1,A2,…,AN.
OUTPUT FORMAT (file haircut.out):
For each of j=0,1,…,N−1, output the badness of FJ's hair on a new line.Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).
SAMPLE INPUT:
5 5 2 3 3 0
SAMPLE OUTPUT:
0 4 4 5 7
The fourth line of output describes the number of inversions when FJ's hairs are decreased to length 3. Then A=[3,2,3,3,0] has five inversions: A1>A2,A1>A5,A2>A5,A3>A5, and A4>A5.
SCORING:
- Test case 2 satisfies N≤100.
- Test cases 3-5 satisfy N≤5000.
- Test cases 6-13 satisfy no additional constraints.
Problem credits: Dhruv Rohatgi