#P8890. [入门赛 #7] 打 ACM 最快乐的就是滚榜读队名了 (Hard Version)

[入门赛 #7] 打 ACM 最快乐的就是滚榜读队名了 (Hard Version)

题目背景

本题的题意与 I1 完全相同,区别仅在 mmKK 的范围。

在刚刚结束的 ICPC 杭州赛站上,某 E 经历了刺激的滚榜。她发现打 ACM 最快乐的就是滚榜读队名了。

题目描述

一场 ICPC 正式赛共 55 小时。

队伍的排名由通过题数与罚时决定。通过题数更多的队伍排名更靠前,若通过题数相同,则罚时更小的队伍排名更靠前。通过题数与罚时均相同的队伍排名相同。本题中可能出现队伍排名相同的情况,此时,认为先出现在提交记录中的队伍排名靠前。

罚时是由通过题目的时间和未通过提交的次数决定的。罚时为每一道题通过时比赛开始的分钟数之和,加上该题之前未通过提交的次数乘 2020 分钟得到的。例如,某队在比赛进行 1:28:351:28:35 时通过了 G 题,在此之前共有 33 次未通过的提交,则 G 题对罚时的总贡献为 88+3×20=14888+3 \times 20=148 分钟。

需要注意的是,仅有通过的试题的未通过提交会被计算罚时。例如,某队在 I 题共有 1414 次未通过的提交,但到比赛结束,该队都没有通过 I 题,则这 1414 次未通过的提交不会被计算罚时。在某一题通过后,该队对这一题的任何提交(无论是否能够通过)都不会影响本题通过的结果和本题的罚时。

选手在比赛过程中可以随时提交某一道试题的代码,代码将被立即评测并返回结果(Accepted\texttt{Accepted}Time Limit Exceeded\texttt{Time Limit Exceeded}Memory Limit Exceeded\texttt{Memory Limit Exceeded}Presentation Error\texttt{Presentation Error}Wrong Answer\texttt{Wrong Answer}Runtime Error\texttt{Runtime Error})。其中,评测结果 Accepted\texttt{Accepted} 为通过,其他评测结果均为不通过。

在比赛进行的前四小时(0:00:004:00:000:00:00 \sim 4:00:00),每支队伍的提交均会在排行榜上反映出来。比赛的最后一小时(4:00:015:00:004:00:01 \sim 5:00:00),排行榜将被冻结(封榜),所有的提交在排行榜对应队伍对应试题上均显示为待判题(提交的队伍知道评测结果)。

在比赛结束后,会进行紧张刺激的滚榜环节。滚榜嘉宾将按照封榜时的排行榜,依照从最后一名到第一名,先读出队伍队名,再按照从 A 题依次到最后一题的顺序,公布排行榜上该队“待判题”状态试题最终是否通过。

如果通过,所有队伍的排名将立即重新计算,显然,已经滚榜完成(被滚榜嘉宾念过队名,且所有待判题状态的结果都已经揭晓)的队伍排名不会有影响。若该队伍排名上升,则滚榜嘉宾立即开始下一支队伍的滚榜。因此,一支队伍的队名可能被滚榜嘉宾多次读出。

例如,某队队名为“囤题”,在前四小时没有通过任何一题,封榜时排在最后一名。在封榜后,该队连续通过全部十三道题目。那么滚榜嘉宾有可能读到该队队名七八次。当然,当该队上升到第一名后,其排名不会再发生变化,即使揭晓的判题结果为通过,但其排名没有发生变化,滚榜嘉宾不会再次读出其队名。

现在给出某场 ICPC 完整的提交记录,请你依次输出滚榜嘉宾念出的队名。

一次提交记录都没有的队伍不会在排行榜上出现,也不会在滚榜中被念到队名。

输入格式

输入的第一行为三个整数 n,m,Kn,m,K,依次为该场 ICPC 试题数、该场 ICPC 队伍数、该场 ICPC 提交记录数。

接下来 KK 行,每行为四个空格分隔的字符串,表达一条提交记录。第一个形如 x:yy:zzx:yy:zz,代表该记录在比赛开始 xx 小时 yyyy 分钟 zzzz 秒时提交。第二个字符串为一个大写英文字母,代表试题的编号(A,B,\texttt{A,B,} \cdots)。第三个字符串为队名,保证队名不含空格。第四个字符串(可能含有空格,但为仅出现「题目描述」中的六种评测结果)为该评测记录的评测结果,具体字符串的含义见试题描述部分。

输出格式

输出若干行,为该滚榜嘉宾依次读到的队名。

2 2 4
0:00:01 A abc Wrong Answer
0:00:02 A abc Accepted
0:19:38 A bcd Accepted
4:18:22 B abc Accepted
abc
bcd
abc

提示

样例解释

在封榜前,队伍 abc\texttt{abc} 仅通过 A\texttt{A} 题,且在第二秒的第一次正确提交之前有一次错误提交,因此罚时为 2020 分钟;队伍 bcd\texttt{bcd} 同样仅通过 A\texttt{A} 题,且在 0:19:380:19:38 的第一次正确提交之前没有错误提交,因此罚时为 1919 分钟。

在封榜后,队伍 abc\texttt{abc} 通过了 B\texttt{B} 题。

在滚榜环节开始,由于封榜后的提交未被揭晓,因此暂时认为队伍 abc\texttt{abc}bcd\texttt{bcd} 均只通过一题,且前者罚时较大,排名靠后。

依照从最后一名到第一名的原则,队伍 abc\texttt{abc} 的名字先被念到,并揭晓其在封榜后的提交的结果。其通过了 B\texttt{B} 题,因此其通过题数被更新为 22,罚时同样被更新。同时,所有队伍的排名立即被重新计算。由于此时 abc\texttt{abc} 通过题目数量大于 bcd\texttt{bcd},因此其排名重新计算为第一名,而 bcd\texttt{bcd} 成为最后一名第二名。

这之后,队伍 bcd\texttt{bcd} 的名字被念到,由于其在封榜后没有提交,因此这时所有队伍的排名没有变化,滚榜嘉宾会进行其上一名队伍的滚榜。

最后,队伍 abc\texttt{abc} 的名字被念到,滚榜结束。

需要注意的是,在滚榜过程中是逐题揭晓提交。也就是说,如果一支队伍封榜后通过了多道题,在其进行滚榜过程中,只要按照从 A\texttt{A} 题依次到最后一题的顺序,该队第一个“待判题”状态试题通过,后面的“待判题”同样暂时不会揭晓,而是立刻进行排名更新过程以及可能存在的更换另一支队伍进行滚榜的过程。

数据规模与约定

对于 100%100\% 的数据,1n201 \le n \le 201m2×1051 \le m \le 2 \times 10^51K2×1061 \le K \le 2 \times 10^60x50 \leq x \leq 500yy<6000 \leq yy < 6000zz<6000 \leq zz < 60,且当 x=5x = 5 时保证 yy=zz=00yy = zz = 00

保证提交记录按照提交时间不降序给出,即先给出的提交记录提交时间不会晚于后给出的提交记录的提交时间,试题名称为大写字母 AZ\texttt{A} \sim \texttt{Z},队名均为长度不超过 5050 的由小写字母组成的字符串,评测状态为试题中所给的 66 种之一。