Count of Smaller Numbers After Self
HardPractice library · +30 XPfenwick treemerge sortcoordinate compression
For every position i of an array a of n integers, count how many elements to its right are strictly smaller than a[i].
Print all n counts.
Input
Line 1: n
Line 2: n integers
Output
n integers separated by spaces: the count for each position.
Constraints
- 1 <= n <= 100000
- |a[i]| <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB12 hidden tests
Example 1
Input
4 5 2 6 1
Output
2 1 1 0
To the right of 5 are 2 and 1 (smaller), of 2 only 1, of 6 only 1, of 1 nothing.
Example 2
Input
3 -1 -1 -1
Output
0 0 0
Equal values do not count.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
4 5 2 6 1
Example 2 input
3 -1 -1 -1