A streaming archive tracks every title it has ever added to its catalog and every time a viewer opens one of them. The operations team wants to flag titles that appear to have gone dormant. Given a particular "today" (expressed as a day number), a title is only a candidate for the dormant flag if it has been in the catalog for at least 30 days as of today — a title added within the last 30 days hasn't had a fair chance yet and must be skipped entirely, regardless of its view count. Among the remaining, eligible titles, flag a title as dormant if the total number of views logged for it strictly within the trailing 365-day window ending on today (that is, on any day strictly after today - 30\... wait", the window is any day strictly after today - 365 and no later than today) is fewer than 10. Given the full catalog and the full view log, report every dormant title.
Line 1: two integers n m — the number of titles in the catalog and the number of view-log entries.
Line 2: one integer today — the reference day.
Each of the next n lines contains a title's name and the day it was added: name addedDay, where name is a string of 1 to 50 lowercase letters, digits, and underscores, unique across all titles.
Each of the next m lines contains one view-log entry: name views day, meaning the title called name logged views view-events on day day. Every name appearing in a view-log entry also appears among the n titles. A title may have zero, one, or several view-log entries, and entries for the same title on the same day are never pre-merged in the input — you must sum them yourself.
Print the names of all dormant titles, one per line, sorted in ascending lexicographic order. If no title is dormant, print nothing.
1 <= n <= 5000 <= m <= 50001 <= today <= 10^91 <= addedDay <= today1 <= day <= today1 <= views <= 10^6Example 1
Input
3 4 400 alpha 10 beta 390 gamma 5 alpha 3 50 alpha 4 200 beta 100 60 gamma 2 398
Expected
alpha gamma
Explanation
today is 400, so the eligibility cutoff is today - 30 = 370 and the view window is any day strictly after 35 and up to 400. `beta` was added on day 390, which is after the cutoff, so it is skipped entirely even though it logged 100 views. `alpha` (added day 10, eligible) logged views on day 50 and day 200, both inside the window, for a total of 3 + 4 = 7, which is under 10, so it is dormant. `gamma` (added day 5, eligible) logged 2 views on day 398, inside the window, for a total of 2, also under 10, so it is dormant. Sorted alphabetically, the dormant titles are `alpha` then `gamma`.
Example 2
Input
3 5 1000 delta 1 epsilon 990 zeta 500 delta 5 100 delta 6 700 zeta 12 800 zeta 1 900 epsilon 20 950
Expected
delta
Explanation
today is 1000, so the cutoff is 970 and the window is any day strictly after 635 and up to 1000. `epsilon` was added on day 990, after the cutoff, so it is skipped regardless of its 20 views. `delta` (added day 1, eligible) has a view entry on day 100, which falls outside the window and is ignored, and an entry on day 700, inside the window, for a total of 6 — under 10, so `delta` is dormant. `zeta` (added day 500, eligible) has entries on day 800 and day 900, both inside the window, totalling 12 + 1 = 13 — not under 10, so `zeta` is not dormant. The only dormant title is `delta`.
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 →