A harbor authority keeps two ledgers: a merchant registry recording the date each merchant joined the harbor, and a trade log recording every completed trade, each tagged with the date it happened and the ID of the merchant who purchased in that trade (the buyer side). For an annual report covering one chosen calendar year, the authority wants -- for every registered merchant, whether or not they traded that year -- their registration date and exactly how many trades they made as a buyer during that calendar year.
Given the merchant registry, the trade log, and the year to report on, produce one line of output per merchant.
n m y -- the number of merchants (1 <= n <= 210^5), the number of trade-log entries (0 <= m <= 210^5), and the calendar year to report on (1 <= y <= 9999).n lines each contain an integer merchant_id (1 <= merchant_id <= 10^9, all n values distinct) followed by a date join_date in YYYY-MM-DD format -- the day that merchant registered.m lines each contain a date trade_date in YYYY-MM-DD format followed by an integer buyer_id -- one trade, and the ID of the merchant who was the buyer in it. Every buyer_id that appears is guaranteed to equal some registered merchant's merchant_id.All dates are valid calendar dates given as exactly 10 characters in YYYY-MM-DD form (the year is always written zero-padded to 4 digits).
Print n lines, one per merchant, ordered by join_date ascending, breaking ties by merchant_id ascending. Each line has the format merchant_id join_date count, where count is the number of trade-log entries whose buyer_id equals that merchant's ID and whose trade_date falls in calendar year y.
merchant_id values are distinct positive integers <= 10^9.Example 1
Input
3 4 2019 101 2018-01-01 102 2019-06-01 103 2017-03-15 2019-01-15 101 2019-08-20 101 2020-01-01 101 2019-07-01 103
Expected
103 2017-03-15 1 101 2018-01-01 2 102 2019-06-01 0
Explanation
Sorted by join date ascending: merchant 103 (2017-03-15), merchant 101 (2018-01-01), merchant 102 (2019-06-01). Restricting the trade log to year 2019: merchant 101 bought on 2019-01-15 and 2019-08-20 (the 2020-01-01 purchase is excluded), for a count of 2; merchant 103 bought once on 2019-07-01, for a count of 1; merchant 102 made no purchases at all, so its count is 0.
Example 2
Input
2 1 2020 201 2020-01-01 150 2020-01-01 2020-05-05 150
Expected
150 2020-01-01 1 201 2020-01-01 0
Explanation
Both merchants joined on the same date (2020-01-01), so the tie is broken by merchant_id ascending: merchant 150 is listed before merchant 201. In 2020, merchant 150 bought once (on 2020-05-05) for a count of 1, and merchant 201 made no purchases for a count of 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 →