An auction house is cataloguing n lots for its next sale, numbered 0 to n - 1. Each lot i has been assigned an authentication tier tier[i] (lower tiers indicate earlier, less-scrutinized provenance) and an appraised value value[i].
To help buyers judge how a lot compares against less-authenticated lots, the house computes a rarity credit for every lot: the rarity credit of lot i is the sum of the k largest appraised values among all lots whose authentication tier is strictly less than tier[i]. If fewer than k such lots exist, sum all of them; if none exist, the rarity credit is 0.
Compute the rarity credit of every lot.
Print n integers separated by single spaces: the rarity credit of lot 0, lot 1, ..., lot n - 1, in that order.
Example 1
Input
4 2 2 1 1 3 10 20 30 5
Expected
50 0 0 50
Explanation
Lot 0 (tier 2) has two lower-tier lots, lot 1 and lot 2 (both tier 1, values 20 and 30); their sum is 50. Lot 1 and lot 2 (tier 1) have no lot with a strictly smaller tier, so both get 0. Lot 3 (tier 3) has three lower-tier lots (values 10, 20, 30); the two largest are 30 and 20, summing to 50. Output: 50 0 0 50.
Example 2
Input
1 1 5 100
Expected
0
Explanation
There is only one lot, so no lot has a strictly smaller tier than it. Its rarity credit is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →