记录编号	472779	评测结果	EEEEEEEEEE
题目名称	单词默写	最终得分	0
用户昵称	swttc	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-11-07 20:49:55	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

int n,m,cnt;
vector<int>sum[1000010];

struct nodes
{
	int val;
	char s[13];
	bool operator < (const nodes & b) const{
		return val<b.val;
	}
}av[100010];

struct tree
{
	int ch[26];
}trie[1000010];

void inser(char *s,int vall)
{
	int l=strlen(s+1),u=0;
	for(int i=1;i<=l;i++){
		int num=(int)(s[i]-'a');		
		if(!trie[u].ch[num]){
			cnt++;
			trie[u].ch[num]=cnt;
			u=cnt;
		}
		else u=trie[u].ch[num];//cout<<u;
		sum[u].push_back(vall);
	}
	return;
}

int query(char *s,int vall)
{
	int l=strlen(s+1),u=0;
	for(int i=1;i<=l;i++){
		int num=(int)(s[i]-'a');		
		if(!trie[u].ch[num]) return 0;
		else u=trie[u].ch[num];
	}//cout<<u<<" "<<trie[u].sum.size()<<endl;
	int ll=0,rr=sum[u].size();
	while(ll!=rr){
		int mid=ll+rr>>1;
		if(sum[u][mid]<vall) ll=mid+1;
		else rr=mid;
	}
	return sum[u].size()-ll;
}

int main()
{
	freopen("engzam.in","r",stdin);
	freopen("engzam.out","w",stdout);
//	cout<<(sizeof(trie)+sizeof(av))/1024/1024<<endl;cout<<"A";
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s%d",av[i].s+1,&av[i].val);
	sort(av+1,av+n+1);
	for(int i=1;i<=n;i++) inser(av[i].s,av[i].val);
	for(int i=1;i<=m;i++){
		char c[13];
		int valll;
		scanf("%s%d",c+1,&valll);
		printf("%d\n",query(c,valll));
	}
	return 0;
 }