Order book

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.

Restrictions:30s256Mb 1 Score Packages

Feel free to create an issue if you need an extra library from the standard Ubuntu repository.

Name	Version	Description
libc6-dev	2.39-0ubuntu8.7	GNU C Library: Development Libraries and Header Files Contains the symlinks, headers, and object files needed to compile and link programs which use the standard C library.
libclang-common-14-dev	1:14.0.6-19build4	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-15-dev	1:15.0.7-14build3	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-16-dev	1:16.0.6-23ubuntu4	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-17-dev	1:17.0.6-9ubuntu1	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-18-dev	1:18.1.3-1ubuntu1	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-19-dev	1:19.1.1-1ubuntu1~24.04.2	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libclang-common-20-dev	1:20.1.2-0ubuntu1~24.04.2	Clang library - Common development package Clang project is a C, C++, Objective C and Objective C++ front-end based on the LLVM compiler. Its goal is to offer a replacement to the GNU Compiler Collection (GCC). . Clang implements all of the ISO C++ 1998, 11, 14 and 17 standards and also provides most of the support of C++20. . This package contains the Clang generic headers.
libcrypt-dev	1:4.4.36-4build1	libcrypt development files This package contains the files needed for developing applications that use libcrypt.
libgcc-10-dev	10.5.0-4ubuntu2.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libgcc-11-dev	11.5.0-1ubuntu1~24.04.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libgcc-12-dev	12.4.0-2ubuntu1~24.04.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libgcc-13-dev	13.3.0-6ubuntu2~24.04.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libgcc-14-dev	14.2.0-4ubuntu2~24.04.1	GCC support library (development files) This package contains the headers and static library files necessary for building C programs which use libgcc, libgomp, libquadmath, libssp or libitm.
libobjc-13-dev	13.3.0-6ubuntu2~24.04.1	Runtime library for GNU Objective-C applications (development files) This package contains the headers and static library files needed to build GNU ObjC applications.
libssl-dev	3.0.13-0ubuntu3.9	Secure Sockets Layer toolkit - development files This package is part of the OpenSSL project's implementation of the SSL and TLS cryptographic protocols for secure communication over the Internet. . It contains development libraries, header files, and manpages for libssl and libcrypto.
libstdc++-10-dev	10.5.0-4ubuntu2.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libstdc++-11-dev	11.5.0-1ubuntu1~24.04.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libstdc++-12-dev	12.4.0-2ubuntu1~24.04.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libstdc++-13-dev	13.3.0-6ubuntu2~24.04.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libstdc++-14-dev	14.2.0-4ubuntu2~24.04.1	GNU Standard C++ Library v3 (development files) This package contains the headers and static library files necessary for building C++ programs which use libstdc++. . libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which was included up to g++-2.95. The first version of libstdc++-v3 appeared in g++-3.0.
libtbb-dev	2021.11.0-2ubuntu2	parallelism library for C++ - development files TBB is a library that helps you leverage multi-core processor performance without having to be a threading expert. It represents a higher-level, task-based parallelism that abstracts platform details and threading mechanism for performance and scalability. . (Note: if you are a user of the i386 architecture, i.e., 32-bit Intel or compatible hardware, this package only supports Pentium4-compatible and higher processors.) . This package includes the TBB development files.

Back to listOct 15, 2024 20:08

@drytecc

Error

Source Code

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

Challenge History

No challenges yet.

Run Statistics

#	Date	Score	Wall Time	CPU User	CPU System	Memory	Error
1	Oct 15, 2024 20:08	0	0	0	0	0	Error: No answer to stdout. Died or killed?
2	Oct 15, 2024 20:10	0	0	0	0	0	Error: expected "1461510 ", got "1461622 "
3	Oct 15, 2024 20:10	0	0	0	0	0	Error: No answer to stdout. Died or killed?
4	Oct 15, 2024 20:10	0	0	0	0	0	Error: No answer to stdout. Died or killed?
5	Oct 15, 2024 20:10	0	0	0	0	0	Error: No answer to stdout. Died or killed?
6	Oct 15, 2024 20:10	0	0	0	0	0	Error: No answer to stdout. Died or killed?
7	Oct 15, 2024 20:10	0	0	0	0	0	Error: No answer to stdout. Died or killed?
8	Oct 15, 2024 20:10	0	0	0	0	0	Error: expected "1428626 ", got "1894856 "
9	Oct 15, 2024 20:11	0	0	0	0	0	Error: No answer to stdout. Died or killed?
10	Oct 15, 2024 20:11	0	0	0	0	0	Error: No answer to stdout. Died or killed?
11	Oct 15, 2024 20:11	0	0	0	0	0	Error: expected "838950 ", got "884312 "
12	Oct 15, 2024 20:11	0	0	0	0	0	Error: expected "967163 ", got "1063069 "
13	Oct 15, 2024 20:11	0	0	0	0	0	Error: No answer to stdout. Died or killed?
14	Oct 15, 2024 20:11	0	0	0	0	0	Error: No answer to stdout. Died or killed?
15	Oct 15, 2024 20:11	0	0	0	0	0	Error: No answer to stdout. Died or killed?
16	Oct 15, 2024 20:11	0	0	0	0	0	Error: No answer to stdout. Died or killed?
17	Oct 15, 2024 20:11	0	0	0	0	0	Error: expected "1336622 ", got "1338847 "
18	Oct 15, 2024 20:11	0	0	0	0	0	Error: No answer to stdout. Died or killed?
19	Oct 15, 2024 20:11	0	0	0	0	0	Error: No answer to stdout. Died or killed?
20	Oct 15, 2024 20:11	0	0	0	0	0	Error: No answer to stdout. Died or killed?
21	Oct 15, 2024 20:11	0	0	0	0	0	Error: expected "1552319 ", got "2213234 "
22	Oct 15, 2024 20:11	0	0	0	0	0	Error: No answer to stdout. Died or killed?
23	Oct 15, 2024 20:12	0	0	0	0	0	Error: expected "1648023 ", got "1713685 "
24	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
25	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
26	Oct 15, 2024 20:12	0	0	0	0	0	Error: expected "901669 ", got "904844 "
27	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
28	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
29	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
30	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
31	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
32	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
33	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
34	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
35	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
36	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
37	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
38	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
39	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
40	Oct 15, 2024 20:12	0	0	0	0	0	Error: No answer to stdout. Died or killed?
41	Oct 15, 2024 20:13	0	0	0	0	0	Error: No answer to stdout. Died or killed?
42	Oct 15, 2024 20:14	0	0	0	0	0	Error: No answer to stdout. Died or killed?
43	Oct 15, 2024 20:14	0	0	0	0	0	Error: No answer to stdout. Died or killed?
44	Oct 15, 2024 20:14	0	0	0	0	0	Error: No answer to stdout. Died or killed?
45	Oct 15, 2024 20:14	0	0	0	0	0	Error: expected "870541 ", got "895839 "
46	Oct 15, 2024 20:14	0	0	0	0	0	Error: No answer to stdout. Died or killed?
47	Oct 15, 2024 20:14	0	0	0	0	0	Error: No answer to stdout. Died or killed?
48	Oct 15, 2024 20:14	0	0	0	0	0	Error: expected "1474013 ", got "1474953 "
49	Oct 15, 2024 20:14	0	0	0	0	0	Error: No answer to stdout. Died or killed?
50	Oct 15, 2024 20:14	0	0	0	0	0	Error: No answer to stdout. Died or killed?
51	Oct 15, 2024 20:14	0	0	0	0	0	Error: expected "1789465 ", got "1854801 "
52	Oct 15, 2024 20:15	0	0	0	0	0	Error: No answer to stdout. Died or killed?
53	Oct 15, 2024 20:15	0	0	0	0	0	Error: No answer to stdout. Died or killed?
54	Oct 15, 2024 20:15	0	0	0	0	0	Error: No answer to stdout. Died or killed?
55	Oct 15, 2024 20:15	0	0	0	0	0	Error: No answer to stdout. Died or killed?
56	Oct 15, 2024 20:15	0	0	0	0	0	Error: expected "1987625 ", got "1988043 "
57	Oct 15, 2024 20:15	0	0	0	0	0	Error: No answer to stdout. Died or killed?
58	Oct 15, 2024 20:15	0	0	0	0	0	Error: No answer to stdout. Died or killed?
59	Oct 15, 2024 20:15	0	0	0	0	0	Error: No answer to stdout. Died or killed?
60	Oct 15, 2024 20:15	0	0	0	0	0	Error: No answer to stdout. Died or killed?
61	Oct 15, 2024 20:15	0	0	0	0	0	Error: No answer to stdout. Died or killed?
62	Oct 15, 2024 20:16	0	0	0	0	0	Error: No answer to stdout. Died or killed?
63	Oct 15, 2024 20:17	0	0	0	0	0	Error: No answer to stdout. Died or killed?
64	Oct 15, 2024 20:17	0	0	0	0	0	Error: No answer to stdout. Died or killed?
65	Oct 15, 2024 20:17	0	0	0	0	0	Error: No answer to stdout. Died or killed?
66	Oct 15, 2024 20:17	0	0	0	0	0	Error: No answer to stdout. Died or killed?
67	Oct 15, 2024 20:17	0	0	0	0	0	Error: No answer to stdout. Died or killed?
68	Oct 15, 2024 20:17	0	0	0	0	0	Error: No answer to stdout. Died or killed?
69	Oct 15, 2024 20:17	0	0	0	0	0	Error: No answer to stdout. Died or killed?
70	Oct 15, 2024 20:17	0	0	0	0	0	Error: No answer to stdout. Died or killed?
71	Oct 15, 2024 20:20	0	0	0	0	0	Error: expected "759754 ", got "763498 "
72	Oct 15, 2024 20:20	0	0	0	0	0	Error: expected "3659275 ", got "3687595 "
73	Oct 15, 2024 20:20	0	0	0	0	0	Error: No answer to stdout. Died or killed?
74	Oct 15, 2024 20:20	0	0	0	0	0	Error: No answer to stdout. Died or killed?
75	Oct 15, 2024 20:21	0	0	0	0	0	Error: No answer to stdout. Died or killed?
76	Oct 15, 2024 20:21	0	0	0	0	0	Error: expected "846076 ", got "899945 "
77	Oct 15, 2024 20:21	0	0	0	0	0	Error: No answer to stdout. Died or killed?
78	Oct 15, 2024 20:21	0	0	0	0	0	Error: No answer to stdout. Died or killed?
79	Oct 15, 2024 20:21	0	0	0	0	0	Error: No answer to stdout. Died or killed?
80	Oct 15, 2024 20:21	0	0	0	0	0	Error: No answer to stdout. Died or killed?
81	Oct 15, 2024 20:21	0	0	0	0	0	Error: No answer to stdout. Died or killed?
82	Oct 15, 2024 21:13	0	0	0	0	0	Error: expected "1216922 ", got "1221562 "
83	Oct 15, 2024 20:17	63,612	61,802,087	32,907,000	3,988,000	2,359,296
84	Oct 15, 2024 20:17	63,884	63,360,936	33,048,000	4,005,000	2,469,888
85	Oct 15, 2024 20:16	64,279	62,948,892	35,267,000	2,015,000	2,461,696
86	Oct 15, 2024 20:10	64,369	60,463,336	35,316,000	2,018,000	2,457,600
87	Oct 15, 2024 20:16	64,628	66,052,588	33,432,000	4,052,000	2,318,336
88	Oct 15, 2024 20:16	64,690	59,709,512	31,436,000	6,084,000	2,506,752
89	Oct 15, 2024 20:17	64,817	66,298,825	34,546,000	3,048,000	2,342,912
90	Oct 15, 2024 20:10	65,314	64,090,693	34,892,000	2,990,000	2,514,944
91	Oct 15, 2024 20:10	65,386	63,188,078	34,930,000	2,994,000	2,273,280
92	Oct 15, 2024 20:08	65,834	67,936,220	35,170,000	3,014,000	2,400,256
93	Oct 15, 2024 20:08	65,871	67,194,937	35,189,000	3,016,000	2,420,736
94	Oct 15, 2024 20:21	65,895	61,995,539	36,208,000	2,011,000	2,359,296
95	Oct 15, 2024 20:21	66,200	60,407,432	36,376,000	2,020,000	2,465,792
96	Oct 15, 2024 20:21	66,238	60,946,422	35,385,000	3,033,000	2,461,696
97	Oct 15, 2024 21:13	66,359	67,034,649	35,450,000	3,038,000	2,289,664
98	Oct 15, 2024 20:08	66,407	63,483,890	34,462,000	4,054,000	2,465,792
99	Oct 15, 2024 20:08	66,705	66,935,833	36,653,000	2,036,000	2,433,024
100	Oct 15, 2024 20:08	66,776	69,610,999	35,673,000	3,057,000	2,465,792
101	Oct 15, 2024 21:13	67,017	65,638,442	36,877,000	1,993,000	2,461,696
102	Oct 15, 2024 21:13	67,045	72,057,754	34,898,000	3,988,000	2,457,600
103	Oct 15, 2024 20:08	67,057	69,048,771	36,899,000	1,994,000	2,506,752
104	Oct 15, 2024 20:08	67,102	63,355,120	35,926,000	2,993,000	2,465,792
105	Oct 15, 2024 20:21	67,148	66,837,338	36,949,000	1,997,000	2,506,752
106	Oct 15, 2024 21:13	67,157	63,124,317	36,954,000	1,997,000	2,314,240
107	Oct 15, 2024 21:13	67,216	61,028,969	35,987,000	2,998,000	2,265,088
108	Oct 15, 2024 20:08	67,298	73,115,100	37,032,000	2,001,000	2,469,888
109	Oct 15, 2024 20:21	67,350	61,291,751	36,059,000	3,004,000	2,523,136
110	Oct 15, 2024 21:13	67,431	65,432,711	38,108,000	1,002,000	2,469,888
111	Oct 15, 2024 20:08	67,471	61,241,383	35,120,000	4,013,000	2,433,024
112	Oct 15, 2024 20:21	67,478	62,148,691	37,130,000	2,007,000	2,469,888
113	Oct 15, 2024 20:21	67,995	73,417,640	35,393,000	4,044,000	2,465,792
114	Oct 15, 2024 20:21	68,893	68,569,788	36,962,000	2,996,000	2,301,952
115	Oct 15, 2024 20:21	68,981	63,077,401	37,009,000	3,000,000	2,412,544

Model	Intel(R) Xeon(R) CPU E3-1271 v3 @ 3.60GHz
Cores	1