比赛场次 618
比赛名称 2024暑假C班集训8
比赛状态 已结束比赛成绩
开始时间 2024-07-08 08:00:00
结束时间 2024-07-08 12:00:00
开放分组 全部用户
注释介绍 难度:T2<[T3,T4]<T1
题目名称 单词默写
输入输出 engzam.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar┭┮﹏┭┮ AAAAAAAAAA 1.240 s 55.48 MiB 100
GravatardarkMoon AAAAAAAAAA 1.367 s 48.85 MiB 100
Gravatarliuyiche AAAAAAAAAA 3.965 s 3.92 MiB 100
Gravatarwzh0425 AAAAAEEEEE 0.983 s 3.04 MiB 50
Gravatar小金 AAAAAEEEEE 1.268 s 32.43 MiB 50
Gravatardream AAAAATTTTT 5.005 s 5.59 MiB 50
GravatarUntitled AAAAATTTTT 5.006 s 5.50 MiB 50
Gravatar彭欣越 AAAAATTTTT 5.009 s 5.50 MiB 50
Gravatarflyfree MMMMMMMMMM 0.010 s 1.36 MiB 0
Gravatarzz WWWWWTTTTT 5.001 s 3.95 MiB 0

单词默写

★☆   输入文件:engzam.in   输出文件:engzam.out   简单对比
时间限制:1 s   内存限制:128 MiB

【问题描述】

小D前一段日子刚刚参加了一次非常苛刻的英语考试。

考试不仅包括了听力、选择、填空等基本题型,还包括了一种特殊的单词默写题。这类题目都是按照以下形式给出的:

在本学期你所学的所有前缀是B的单词中,在课本中出现次数不少于L的有多少个。

例如小D这个学期只学过三个单词a、ab、bc,它们出现的次数分别是1、2、3;若给出询问(B = a,L = 2),那么前缀为a的单词一共有两个,是a和ab,其中频率不少于2的只有一个,是ab。

这个学期小D学过的单词非常多,而考试给出的这类询问也非常多。这么困难的任务小D当然不可能解决,于是这个问题被交给了你。

【输入文件】

输入文件第一行包含两个用空格隔开的整数N、M,分别表示小D本学期学过的单词数和考试中出现的询问数。

接下来N行,每行包含用空格隔开的一个单词A和一个整数P,描述小D本学期学过的一个单词A以及其出现的次数P。

接下来M行,每行包含用空格隔开的一个单词B和一个整数L,描述考试中给出的一个询问。

你可以假定所有单词均由小写字母组成,且长度不超过10。

【输出文件】

输出文件一共包含M行。

对于每个考试的询问输出一行一个整数,表示该问题的答案。

【样例输入】

3 3
a 1
ab 2
bc 3
a 2
a 1
a 3

【样例输出】

1
2
0

【样例说明】

前缀为a的单词一共有两个,是a和ab,出现次数分别为1和2。

大样例:data

【数据规模】

对于50%的测试数据,满足N、M ≤ 1 000

对于100%的测试数据,满足N、M ≤ 100 000,P、L ≤ 100 000

注:数据已加强。