Loading...
Loading...
Loading...
A mock placement test has negative marking, so a score can be below zero. The n scores are listed in roll-number order.
For each student, count how many students after them in the list scored strictly less than they did. A student with the same score does not count.
Print the n counts in roll-number order.
Example 1
Input
5 5 2 6 1 3
Output
3 1 2 0 0
After the 5 come 2, 6, 1 and 3, and three of them are smaller. After the 2 only the 1 is smaller. After the 6 come 1 and 3. The last two students have nobody smaller after them.
Example 2
Input
4 4 4 -2 4
Output
1 1 0 0
Equal scores do not count. Each of the first two 4s has only the −2 smaller after it.
Try the problem first. Open one hint at a time.
Checking every later student for each student takes about n²/2 steps, which is 2 × 10^10 when n = 2 × 10^5.
Walk the list from the last student to the first. Then "students after me" are exactly the ones you have already seen.
Scores can be as large as 10^9 or negative. Sort the distinct scores and replace each score by its position in that sorted list, from 1 to m.
Keep a binary indexed tree (Fenwick tree) of counts over those positions. For each student, read how many seen scores have a smaller position, then add 1 at the student's own position.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor