Order book Yuriy Lyfenko

Simulate a sell-side order book and calculate the cost of a final purchase as fast as possible.

Input

1,000,000 order updates on STDIN, one per line:

  • + <price> <size> – add a new sell order
  • - <position> – delete the order at the given position
  • = <size> – buy <size> shares from the top of the order book

After all updates are processed, buy 1,000 shares from the top of the order book.

Output

Print the total cost of the final 1,000-share purchase to STDOUT.

Order Book Rules

Orders are sorted by price ascending (lower is better). Orders at the same price are sorted by arrival time (earlier first). Position 0 is the best (lowest-price) offer.

The = (buy) operation consumes shares starting from position 0. If an order is fully consumed, it is removed from the book.

Example

Input Order book state
+ 1137 100 (1137,100)
+ 1130 10 (1130,10), (1137,100)
+ 1130 50 (1130,10), (1130,50), (1137,100)
- 0 (1130,50), (1137,100)
+ 1150 200 (1130,50), (1137,100), (1150,200)
= 200 (1150,150)

Total cost of the last buy: 50 * 1130 + 100 * 1137 + 50 * 1150.

Back to listOct 18, 2024 08:26matsuoka-601matsuoka-601Score: 1,973,683Success
Source Code

Source code access is restricted. Log in to request access.

Challenge History

No challenges yet.

Run Statistics
#DateScoreWall TimeCPU UserCPU SystemMemoryError
1Oct 18, 2024 07:4719,38328,657,6139,198,0002,044,0002,269,184
2Oct 18, 2024 15:1419,41233,569,6329,212,0002,047,0002,273,280
3Oct 18, 2024 15:0419,80933,923,44610,445,0001,044,0002,273,280
4Oct 18, 2024 06:4220,62128,654,4809,967,0001,993,0002,273,280
5Oct 18, 2024 15:1520,75231,047,27510,030,0002,006,0002,424,832
6Oct 18, 2024 15:0820,76928,488,70910,039,0002,007,0002,433,024
7Oct 18, 2024 06:4320,94827,819,07710,125,0002,025,0002,424,832
8Oct 18, 2024 06:3621,03427,778,96710,167,0002,033,0002,535,424
9Oct 18, 2024 15:1521,13130,314,79211,235,0001,021,0002,273,280
10Oct 18, 2024 15:0921,16631,734,98310,230,0002,046,0002,428,928
11Oct 18, 2024 06:3721,63331,121,19711,502,0001,045,0002,273,280
12Oct 18, 2024 06:3921,80230,166,17212,645,00002,535,424
13Oct 18, 2024 06:4821,94328,891,07311,667,0001,060,0002,273,280
14Oct 18, 2024 06:5021,94531,222,07211,668,0001,060,0002,273,280
15Oct 18, 2024 07:3522,37130,239,00111,977,000998,0002,273,280
16Oct 18, 2024 06:3922,38330,777,36510,985,0001,997,0002,428,928
17Oct 18, 2024 06:4222,55033,974,89411,067,0002,012,0002,273,280
18Oct 18, 2024 08:2522,94133,948,98412,283,0001,023,0002,273,280
19Oct 18, 2024 06:4223,08129,014,49813,387,00002,433,024
20Oct 18, 2024 06:3623,22135,449,58712,432,0001,036,0002,273,280
21Oct 18, 2024 06:3723,54131,184,40212,679,000975,0002,535,424
22Oct 18, 2024 07:4123,59534,140,53212,633,0001,052,0002,428,928
23Oct 18, 2024 15:1523,71633,690,93612,697,0001,058,0002,273,280
24Oct 18, 2024 15:1523,97142,027,62312,910,000993,0002,428,928
25Oct 18, 2024 15:1424,31732,320,88413,097,0001,007,0002,433,024
26Oct 18, 2024 15:0824,62634,413,73312,243,0002,040,0002,273,280
27Oct 18, 2024 08:2524,63334,080,35913,267,0001,020,0002,273,280
28Oct 18, 2024 15:0924,73340,014,59713,321,0001,024,0002,535,424
29Oct 18, 2024 15:1425,10732,740,00614,562,00002,273,280
30Oct 18, 2024 06:3725,26746,977,79714,655,00002,273,280
31Oct 18, 2024 06:3925,31632,281,97514,683,00002,433,024
32Oct 18, 2024 15:1525,32831,408,64514,690,00002,510,848
33Oct 18, 2024 06:4725,40040,745,94514,732,00002,433,024
34Oct 18, 2024 06:3825,81632,312,31512,977,0001,996,0002,428,928
35Oct 18, 2024 15:0925,82632,356,81312,982,0001,997,0002,424,832
36Oct 18, 2024 07:3725,84046,757,04612,989,0001,998,0002,437,120
37Oct 18, 2024 06:4326,55235,140,53514,374,0001,026,0002,433,024
38Oct 18, 2024 06:4226,55343,413,76014,375,0001,026,0002,535,424
39Oct 18, 2024 15:1526,71736,173,91315,496,00002,273,280
40Oct 18, 2024 15:0626,92236,169,21615,615,00002,535,424
41Oct 18, 2024 15:15883,897542,389,207510,662,0001,998,0002,486,272
42Oct 18, 2024 15:15896,105547,334,176516,743,0002,998,0002,371,584
43Oct 18, 2024 15:15896,921541,064,003518,214,0002,000,0002,379,776
44Oct 18, 2024 07:351,959,8451,159,438,7441,134,711,0001,999,0002,482,176
45Oct 18, 2024 08:251,964,1291,173,658,1681,138,195,0001,000,0002,482,176
46Oct 18, 2024 06:431,967,1781,168,079,7981,137,964,0002,999,0002,482,176
47Oct 18, 2024 06:471,968,1431,170,928,8941,138,525,0002,998,0002,482,176
48Oct 18, 2024 15:091,968,4311,165,152,5821,139,691,0001,999,0002,482,176
49Oct 18, 2024 07:361,969,9761,171,943,3561,140,587,0001,999,0002,371,584
50Oct 18, 2024 15:041,970,0881,173,640,6251,139,652,0002,999,0002,367,488
51Oct 18, 2024 15:081,970,5221,165,171,4971,139,904,0002,999,0002,535,424
52Oct 18, 2024 15:041,970,7831,172,258,0621,140,054,0003,000,0002,482,176
53Oct 18, 2024 06:381,970,8591,169,125,5731,140,101,0002,997,0002,375,680
54Oct 18, 2024 06:391,971,2211,173,405,6911,141,310,0001,998,0002,482,176
55Oct 18, 2024 06:361,971,2641,170,565,7131,139,336,0003,997,0002,482,176
56Oct 18, 2024 06:571,971,3121,175,922,7801,139,364,0003,997,0002,482,176
57Oct 18, 2024 06:351,971,3261,171,256,7781,140,371,0002,998,0002,482,176
58Oct 18, 2024 06:371,971,3761,168,896,8811,142,399,000999,0002,306,048
59Oct 18, 2024 08:261,971,4091,170,984,1361,140,419,0002,998,0002,482,176
60Oct 18, 2024 07:471,971,6601,171,894,6421,141,564,0001,999,0002,273,280
61Oct 18, 2024 06:361,971,8281,166,398,7951,142,661,000999,0002,482,176
62Oct 18, 2024 15:081,971,8481,164,962,1211,141,673,0001,999,0002,535,424
63Oct 18, 2024 07:361,971,8791,174,537,8101,141,691,0001,999,0002,449,408
64Oct 18, 2024 07:411,972,0931,170,079,1351,140,815,0002,999,0002,363,392
65Oct 18, 2024 06:501,972,3981,173,355,5391,138,992,0004,999,0002,482,176
66Oct 18, 2024 07:411,972,9411,170,327,3481,138,310,0005,996,0002,371,584
67Oct 18, 2024 06:371,972,9621,176,239,0321,140,321,0003,997,0002,535,424
68Oct 18, 2024 07:471,973,1411,169,377,5571,140,425,0003,997,0002,375,680
69Oct 18, 2024 06:391,973,4831,169,576,1021,142,621,0001,999,0002,482,176
70Oct 18, 2024 06:491,973,6831,171,686,3631,141,737,0002,999,0002,482,176
71Oct 18, 2024 15:111,973,7661,175,680,0671,143,785,000999,0002,273,280
72Oct 18, 2024 07:411,973,8741,176,749,4751,141,848,0002,999,0002,482,176
73Oct 18, 2024 07:371,973,9861,172,340,2511,142,913,0001,999,0002,482,176
74Oct 18, 2024 07:411,974,0521,176,426,9691,142,951,0001,999,0002,482,176
75Oct 18, 2024 06:421,974,0531,171,732,5311,143,952,000999,0002,482,176
76Oct 18, 2024 15:091,974,0981,172,922,6231,141,978,0002,999,0002,273,280
77Oct 18, 2024 15:091,974,1221,168,815,1051,141,992,0002,999,0002,379,776
78Oct 18, 2024 06:351,974,2141,174,758,0121,143,044,0002,000,0002,482,176
79Oct 18, 2024 06:351,974,2451,172,385,9121,142,065,0002,997,0002,482,176
80Oct 18, 2024 07:351,974,6791,170,877,6161,141,317,0003,997,0002,482,176
81Oct 18, 2024 15:141,974,6951,172,504,3341,141,326,0003,997,0002,273,280
82Oct 18, 2024 15:091,974,7281,177,650,9881,144,343,000999,0002,482,176
83Oct 18, 2024 08:251,974,7401,168,777,9091,143,351,0001,998,0002,482,176
84Oct 18, 2024 06:431,974,8001,170,833,9691,142,386,0002,998,0002,482,176
85Oct 18, 2024 08:251,974,8221,172,375,7911,143,399,0001,998,0002,482,176
86Oct 18, 2024 15:081,975,0671,169,521,8711,143,540,0001,999,0002,371,584
87Oct 18, 2024 08:251,975,2881,171,186,7191,144,668,000999,0002,482,176
88Oct 18, 2024 15:081,975,2951,177,072,8101,140,673,0004,998,0002,371,584
89Oct 18, 2024 15:111,975,5831,168,625,2151,142,839,0002,999,0002,469,888
90Oct 18, 2024 06:511,975,6521,164,077,6201,141,879,0003,999,0002,457,600
91Oct 18, 2024 06:391,975,9051,174,610,1331,139,031,0006,994,0002,371,584
92Oct 18, 2024 15:041,975,9141,168,631,6551,144,030,0002,000,0002,482,176
93Oct 18, 2024 06:481,975,9261,171,501,1521,145,038,000999,0002,482,176
94Oct 18, 2024 15:061,975,9331,172,323,8181,145,041,0001,000,0002,371,584
95Oct 18, 2024 15:151,975,9341,169,099,3921,144,044,0001,998,0002,482,176
96Oct 18, 2024 07:351,976,1601,172,541,4261,145,173,0001,000,0002,482,176
97Oct 18, 2024 07:411,976,2861,172,666,6681,142,249,0003,997,0002,482,176
98Oct 18, 2024 15:141,976,2981,175,408,5031,142,256,0003,997,0002,482,176
99Oct 18, 2024 06:471,976,3711,174,410,6211,143,297,0002,998,0002,371,584
100Oct 18, 2024 06:361,976,5361,173,158,4441,143,393,0002,998,0002,482,176
101Oct 18, 2024 15:091,976,6841,171,335,3611,143,479,0002,998,0002,482,176
102Oct 18, 2024 07:401,976,7101,179,355,4851,140,495,0005,997,0002,367,488
103Oct 18, 2024 07:371,976,7171,172,327,1841,145,497,000999,0002,367,488
104Oct 18, 2024 07:361,976,7601,173,852,0871,141,524,0004,997,0002,371,584
105Oct 18, 2024 07:411,976,8741,175,760,7841,145,588,000999,0002,482,176
106Oct 18, 2024 07:471,976,8971,175,815,3021,145,601,000999,0002,482,176
107Oct 18, 2024 15:091,976,9021,179,589,4291,144,604,0001,999,0002,375,680
108Oct 18, 2024 06:391,977,0171,175,199,5981,145,671,000999,0002,371,584
109Oct 18, 2024 06:391,977,0171,170,695,8451,145,671,000999,0002,367,488
110Oct 18, 2024 06:431,977,3281,177,201,7921,143,854,0002,996,0002,371,584
111Oct 18, 2024 06:491,977,3281,171,888,9981,143,851,0002,999,0002,482,176
112Oct 18, 2024 15:091,977,3341,173,241,2381,144,855,0001,999,0002,371,584
113Oct 18, 2024 15:151,977,5501,173,422,4831,146,979,00002,363,392
114Oct 18, 2024 06:361,977,5791,174,285,7391,146,996,00002,367,488
115Oct 18, 2024 15:061,977,6691,172,944,4391,146,048,0001,000,0002,367,488
116Oct 18, 2024 06:391,977,7051,178,904,0591,146,070,000999,0002,482,176
117Oct 18, 2024 07:401,977,7761,174,501,9261,147,110,00002,453,504
118Oct 18, 2024 07:411,978,0211,178,215,1371,143,255,0003,997,0002,482,176
119Oct 18, 2024 06:421,978,0431,176,383,1281,145,267,0001,998,0002,482,176
120Oct 18, 2024 06:421,978,1571,174,106,4151,142,334,0004,997,0002,375,680
121Oct 18, 2024 07:361,978,2051,176,838,4961,146,360,000999,0002,478,080
122Oct 18, 2024 06:361,978,2401,173,937,5361,139,384,0007,995,0002,535,424
123Oct 18, 2024 06:371,978,2591,176,797,1691,145,392,0001,998,0002,371,584
124Oct 18, 2024 06:571,978,3811,172,862,1071,146,462,000999,0002,371,584
125Oct 18, 2024 06:391,978,4401,174,861,8891,146,496,000999,0002,535,424
126Oct 18, 2024 15:091,978,5501,179,571,0251,144,561,0002,998,0002,453,504
127Oct 18, 2024 06:511,978,5571,173,583,5711,144,565,0002,998,0002,367,488
128Oct 18, 2024 06:431,978,7811,174,953,2671,145,694,0001,999,0002,371,584
129Oct 18, 2024 06:361,978,8841,174,860,7561,146,754,000999,0002,482,176
130Oct 18, 2024 07:471,978,9431,171,980,0761,144,788,0002,999,0002,482,176
131Oct 18, 2024 07:471,979,4261,174,202,1501,145,067,0003,000,0002,371,584
132Oct 18, 2024 06:381,979,4451,176,060,7411,147,078,0001,000,0002,535,424
133Oct 18, 2024 15:081,979,6831,176,571,6091,146,218,0001,998,0002,363,392
134Oct 18, 2024 07:361,979,7361,175,626,0841,146,249,0001,998,0002,273,280
135Oct 18, 2024 06:471,979,7761,177,287,6051,145,272,0002,998,0002,482,176
136Oct 18, 2024 06:391,979,7811,177,875,7631,145,275,0002,998,0002,482,176
137Oct 18, 2024 06:431,979,9911,176,411,6181,147,396,000999,0002,482,176
138Oct 18, 2024 07:471,980,0881,174,248,6961,146,452,0001,999,0002,375,680
139Oct 18, 2024 15:141,980,1531,176,454,1611,147,490,000999,0002,367,488
140Oct 18, 2024 07:411,980,2101,177,397,7251,143,525,0004,997,0002,273,280
141Oct 18, 2024 15:061,980,3501,176,002,8031,144,605,0003,998,0002,482,176
142Oct 18, 2024 06:491,980,4661,177,588,1541,148,670,00002,367,488
143Oct 18, 2024 15:151,980,5471,172,197,8831,143,719,0004,998,0002,371,584
144Oct 18, 2024 07:351,980,6191,178,553,1201,147,760,000999,0002,482,176
145Oct 18, 2024 06:391,980,9711,176,939,6061,147,964,000999,0002,482,176
146Oct 18, 2024 07:401,981,2261,180,036,4131,147,111,0002,000,0002,482,176
147Oct 18, 2024 06:471,981,3211,177,070,4371,147,168,0001,998,0002,371,584
148Oct 18, 2024 06:361,981,3971,173,247,3021,146,213,0002,997,0002,273,280
149Oct 18, 2024 15:081,981,6641,175,778,0851,147,367,0001,998,0002,375,680
150Oct 18, 2024 15:041,981,7221,173,132,9231,146,401,0002,998,0002,482,176
151Oct 18, 2024 06:421,981,7551,177,244,5721,146,420,0002,998,0002,367,488
152Oct 18, 2024 15:111,982,1241,175,740,1431,145,634,0003,998,0002,371,584
153Oct 18, 2024 15:141,982,1431,177,384,5451,147,644,0001,999,0002,482,176
154Oct 18, 2024 07:351,982,5161,179,043,4221,147,861,0001,998,0002,273,280
155Oct 18, 2024 06:371,982,7411,177,898,8301,147,991,0001,999,0002,482,176
156Oct 18, 2024 15:041,982,8471,179,716,0911,148,051,0002,000,0002,367,488
157Oct 18, 2024 06:361,982,9501,181,373,9981,147,111,0003,000,0002,371,584
158Oct 18, 2024 06:421,983,0901,176,884,2581,147,192,0003,000,0002,375,680
159Oct 18, 2024 06:471,983,1101,183,524,6281,147,207,0002,997,0002,367,488
160Oct 18, 2024 15:141,983,2741,179,306,2101,148,301,0001,998,0002,482,176
161Oct 18, 2024 07:471,983,3211,177,737,7451,146,329,0003,997,0002,273,280
162Oct 18, 2024 06:431,983,3281,177,511,4161,149,331,000999,0002,367,488
163Oct 18, 2024 06:361,983,3451,177,199,9301,146,343,0003,997,0002,482,176
164Oct 18, 2024 06:511,983,3531,175,019,2101,148,347,0001,998,0002,273,280
165Oct 18, 2024 15:061,983,7361,173,667,9301,145,569,0004,998,0002,375,680
166Oct 18, 2024 08:261,983,7781,181,367,0661,145,593,0004,998,0002,482,176
167Oct 18, 2024 15:091,984,1261,178,756,9661,149,794,000999,0002,273,280
168Oct 18, 2024 06:371,984,2521,172,912,8501,148,867,0001,999,0002,486,272
169Oct 18, 2024 06:571,984,2951,178,855,5091,149,892,000999,0002,371,584
170Oct 18, 2024 06:431,984,6841,182,520,8301,150,117,0001,000,0002,457,600
171Oct 18, 2024 06:361,984,7021,178,673,1011,148,130,0002,997,0002,375,680
172Oct 18, 2024 08:261,985,0051,182,993,3251,148,305,0002,998,0002,371,584
173Oct 18, 2024 15:141,985,0861,178,730,8131,148,352,0002,998,0002,482,176
174Oct 18, 2024 15:061,985,5241,182,254,2991,150,605,000999,0002,482,176
175Oct 18, 2024 06:501,985,7431,176,851,6041,149,732,0001,999,0002,478,080
176Oct 18, 2024 06:481,986,2071,181,977,7151,151,001,000999,0002,273,280
177Oct 18, 2024 07:471,986,2171,182,617,4201,149,006,0003,000,0002,482,176
178Oct 18, 2024 15:081,988,5951,184,939,1981,152,386,000999,0002,482,176
179Oct 18, 2024 06:372,254,0381,335,414,3391,302,345,0004,997,0002,482,176
180Oct 18, 2024 07:362,350,4331,390,093,3031,361,253,0001,998,0002,482,176