记录编号	589933	评测结果	AAAAAAAAAA
题目名称	单词默写	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	1.913 s
提交时间	2024-07-08 18:28:10	内存使用	52.19 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
struct word{
    string s;
    int p;
}a[100001];
struct ask{
    string f;
    int l,bh;
}b[100001];
int n,m,tot=1,ans[100001],t[700010][26],sum[1000001]; 
//vector<int> t[1000001];
bool cmp1(word x,word y)
{
    return x.p>y.p;
}
bool cmp2(ask x,ask y)
{
    return x.l>y.l;
}
bool cmp3(ask x,ask y)
{
    return x.bh<y.bh;
}
void insert(int x)
{
    string str=a[x].s;
    int len=str.length();
    int p=1;
    for(int k=0;k<len;k++)
    {
        int ch=str[k]-'a';
        if(t[p][ch]==0)
        {
            tot++;
            t[p][ch]=tot;
        }
        p=t[p][ch];
        sum[p]++;
    }
}
void search(int x)
{
    int now=b[x].bh;
    string str=b[x].f;
    int len=str.length();
    int p=1;
    for(int k=0;k<len;k++)
    {
        p=t[p][str[k]-'a']; 
    }
    ans[now]=sum[p];
}
int main()
{
    freopen("engzam.in","r",stdin);
    freopen("engzam.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].s>>a[i].p;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>b[i].f>>b[i].l;
        b[i].bh=i;
    }
    sort(a+1,a+n+1,cmp1);
    sort(b+1,b+m+1,cmp2);
    int j=1;
    for(int i=1;i<=m;i++)
    {
        while(a[j].p>=b[i].l)
        {
            insert(j);
            j++;
        }
        search(i);
    }
    for(int i=1;i<=m;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}