Log inSign up
Problems / B119

Bundled lots

400 ptsCases 16Set by dongbinna
Added October 30.
1 solved1 attempted2 submissionssolvers took 2.0 tries on average

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 number12345
Dealer number12231
Appraised value45632

The lots that come along when each lot is won, and their total appraised value, are given by the table below.

Lot number12345
Lots taken along41, 4, 51, 4, 55None
Total appraised value39920

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.
Read the requirements carefully before solving. Tampering with the grading to make a submission look like a pass can get you sanctioned if caught. The code you submit is published on the leaderboard along with the result.

Examples

3 public cases. Judging also uses hidden cases. You have to pass all 16 cases to solve this.

Input
Expected output
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.

0 chars1 lineMemory 256MB (recorded only)Reference 252ms

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.

1bampal22.06s631 charsPythonWindows NT 10.0 / Chrome/156.0.0.0 / 8코어 / 16GB

Log in and you can see the code once you solve this problem.