Bundled lots
Statement
N lots came up at an auction house. Each lot, numbered 1 through N, has the number of the dealer that put it up and its appraised value written on it.
This auction house has a rule called the bundled lot. Whoever wins a lot may also take, as a bundle, every lot that is valued lower than it and came from a different dealer. A lot with the same appraised value cannot be taken, and neither can a lot that came from the same dealer.
Write a program that computes, in the order the lots came up, the total appraised value of the lots that come along as a bundle when each lot is won.
For example, suppose the information on N=5 lots is given by the table below.
| Lot number | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Dealer number | 1 | 2 | 2 | 3 | 1 |
| Appraised value | 4 | 5 | 6 | 3 | 2 |
The lots that come along when each lot is won, and their total appraised value, are given by the table below.
| Lot number | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Lots taken along | 4 | 1, 4, 5 | 1, 4, 5 | 5 | None |
| Total appraised value | 3 | 9 | 9 | 2 | 0 |
Lot 1 has an appraised value of 4. The lots valued below 4 are lot 4 at 3 and lot 5 at 2, but lot 5 came from dealer 1, the same dealer as lot 1, so it cannot be taken. The total is 3.
Lot 3 has an appraised value of 6. The lots valued below 6 are lot 1 at 4, lot 2 at 5, lot 4 at 3 and lot 5 at 2, but lot 2 came from dealer 2, the same dealer as lot 3, so it cannot be taken. The total is 4 + 3 + 2 = 9.
Lot 5 has an appraised value of 2, and nothing is valued below that. So there is no lot to take and the total is 0. The answer for this case is 3, 9, 9, 2 and 0 in order.
Several lots may share the same appraised value. They cannot take each other, so lots with the same appraised value have no effect on each other's answer.
Input and Output Examples
Example 1
Input
5 1 4 2 5 2 6 3 3 1 2
Output
3 9 9 2 0
Example 2
Input
4 1 1 2 2 3 3 4 4
Output
0 1 3 6
Example 3
Input
3 2 10 1 1656 1 690
Output
0 10 10
Input
The first line holds the number of lots N. N is a natural number from 1 to 200,000.
The next N lines hold the information on lots 1 through N in order. Each line holds the number of the dealer that put the lot up and its appraised value, separated by a space. The dealer number is a natural number from 1 to N, and the appraised value is a natural number from 1 to 2,000.
The whole input is at most about 2.1MB. There are up to 200,001 lines, so read the whole input in one go and split it into lines.
Output
For each lot from 1 to N, print the total appraised value of the lots that come along as a bundle, one per line and in order. If there is no lot to take, print 0 on that line. There are up to 200,000 lines to print, so join the results with newlines and print them in one go.
Requirements
- A lot with the same appraised value cannot be taken. It has to be valued lower
- A lot that came from the same dealer cannot be taken even when it is valued lower
- The output order is the order the lots came up, that is, the order given in the input
- If there is no lot to take, print 0
- N is up to 200,000, so checking every other lot for each lot runs out of time
- You must write a program that reads from standard input and writes to standard output
- Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
- The languages you can use are Python and JavaScript
- The memory limit is 256MB. The browser does not measure it, it only states it
- The time limit is set by measuring the setter's reference solution on the same runtime
- On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
- The output has to match the expected value down to the character. A space inside a line counts the same as any other character.
- There are 16 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
- You have to pass all 16 cases to solve this.
Examples
3 public cases. Judging also uses hidden cases. You have to pass all 16 cases to solve this.
3 2 10 1 1656 1 690
0 10 10
4 1 1 2 2 3 3 4 4
0 1 3 6
5 1 4 2 5 2 6 3 3 1 2
3 9 9 2 0
Solution
Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.
Submitting requires you to log in. Running against the public cases works without one.
You can test with 3 public cases. Submitting runs the hidden cases too.
People who solved this problem
The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.
Log in and you can see the code once you solve this problem.