记录编号	589928	评测结果	AAAAAAAAAA
题目名称	单词默写	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	1.319 s
提交时间	2024-07-08 17:43:54	内存使用	123.25 MiB

#include <bits/stdc++.h>
using namespace std;

const int N = 700100;

int tot,trie[N][30],sum[N],n,m,res[N],cnt;

struct node{
    int idx;
    int l;
    int ci;
    string wo;
}a[N];

void insert(string s){
    int len=s.size(),p=0;
    for(int i=0;i<len;i++){
        int c=s[i]-'a';
        if(!trie[p][c])trie[p][c]=++tot;
        p=trie[p][c];
        sum[p]++;
//        cout<<p<<"+++"<<s[p]<<endl;
    }
}

int ask(string s){
    int len=s.size(),p=0;
    for(int i=0;i<len;i++){
        int c=s[i]-'a';
        if(trie[p][c]==0)return 0;
        p=trie[p][c];
    }
//    cout<<"???"<<p<<" "<<s[p]<<"TTTTT"<<endl;
    return sum[p];
}

bool cmp(node x,node y){
    if(x.ci==y.ci)return x.l<y.l;
    return x.ci>y.ci;
}

int main(){
    freopen("engzam.in","r",stdin);
    freopen("engzam.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        cin>>a[++cnt].wo;
        scanf("%d",&a[cnt].ci);
        a[cnt].l=1; 
    }
    for(int i=1;i<=m;i++){
        a[++cnt].idx=i;
        cin>>a[cnt].wo;
        scanf("%d",&a[cnt].ci);
        a[cnt].l=2; 
    }
    //    cout<<"TTT"<<endl;
        sort(a+1,a+1+cnt,cmp);
        for(int i=1;i<=cnt;i++){
//        cout<<a[i].wo<<endl;
//          cout<<a[i].l<<" "<<a[i].wo<<' '<<a[i].ci<<endl;
        if(a[i].l==1)insert(a[i].wo);
        else res[a[i].idx]=ask(a[i].wo);
    }
    for(int i=1;i<=m;i++){
        printf("%d\n",res[i]);
    }
//    cout<<endl<<endl;
//    for(int i=1;i<=tot;i++){
//        cout<<trie[i][0]<<" "<<trie[i][1]<<" "<<trie[i][2]<<endl;
//          cout<<s[i]<<endl;
//    } 
    return 0;
}