题目的规则可以拆成两步:
第 1 步,先在每个主播内部做一次“去重保留最优”:
多多负责多多直播的首页直播排行榜的巡检工作。今天平台一共收到n条候选直播内容,按输入顺序依次编号为1到n
每条直播内容都属于某个主播。为了避免同一主播同时占据多个直播排行榜位置,正式生成榜单前,平台会先做。 一次主播去重:
因此,最终直播排行榜中每个主播至多出现一次,榜单条数恰好等于不同主播的个数。条直播内容是否更优,按以下顺序比较:
1点赞数更多者更优
2.如果点赞数相同,则评论数更多者更优;
3如果点赞数和评论数都相同,则发布时间更早者更优;
4如果以上三项仍然完全相同,则原始编号更小者更优
完成主播去重后,再对所有保留下来的直播内容按完全相同的规则排序,得到最终直播排行榜。
现在给出q个查询。每次查询一条直播内容的最终结果:
第一行输入两个整数n,q,分别表示候选直播内容数和查询条数。
接下来n行,第行输入四个整数ui,ai,bi,ti,表示第i条直播内容所属主播编号、点赞数、评论数和发布
其中,ti越小表示发布时间越早。
接下来q行,每行输入一个整数id,表示询问编号为id的直播内容最终排名。
输出q行,每行一个整数。
1≤n,q≤2∗105
1≤ui≤109
0≤ai,bi,ti≤109
1≤id≤n
输入
5 4
1 100 20 5
1 120 10 8
3 100 25 4
2 100 18 6
1
2
3
5
输出
0
0
1
2
说明
主播1有第1、3两条直播条目,其中第3条更优;
主播2有第2、5两条直播条目,其中第5条更优;
主播3只有第4条直播条目,
因此候选榜单只剩第3、4、5条直播条目,再按规则排序后顺序为3−>5−>4。