眼花缭乱的街市

NC24638. 眼花缭乱的街市

描述

水宝宝的美食街开始营业喽

美食街八大菜肴：烤绿鸟（主食），拔丝QAQ套餐（副食），红烧KMP（主菜），Treap刺身（副菜），油炸内存条（小吃），奶油CPU（甜品），SPFA奶盖（饮品），冰镇机油（饮品）

水宝宝美食街开张第二天，wza神犇来到水宝宝美食街，却被琳琅满目的食品吓住了，他急需知道水宝宝的美食街有没有他想吃的东西

给出n个食物编号,然后有m个询问,每个询问一个整数,询问该整数是否在n个食物编号中出现过,保证编号为正整数

输入描述

第一行：n

第二行：m

第三行：n个询问的编号

第四行：m个询问的编号

输出描述

一共m行,若出现则输出"YES",否则输出"NO"

示例1

输入:

15
3
4 2 1 6 16 4 41 19 37 40 8 71 34 87 47
2 8 198

输出:

YES
YES
NO

说明:

对于10%的数据,1<=n,m<=1000

对于30%的数据,1<=n,m<=10000

对于60%的数据,1<=n,m<=200000

对于100%的数据,1<=n,m<=1000000

所有数据<=1e17

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 677ms, 内存消耗: 11360K, 提交时间: 2019-05-25 21:40:09

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1000005;
ll a[maxn];
int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
	ll n,m,x;
	cin>>n>>m;
	for(int i=0;i<n;i++)	cin>>a[i];
	sort(a,a+n);
	while(m--)
	{
		cin>>x;
		if(binary_search(a,a+n,x))	puts("YES");
		else	puts("NO");
	}
	return 0;
}

C++(clang++11) 解法, 执行用时: 665ms, 内存消耗: 11176K, 提交时间: 2020-11-01 11:59:11

#include<bits/stdc++.h>
using namespace std;
long long n,m,x,i,a[1000001];
int main()
{
    ios::sync_with_stdio(0);
	cin>>n>>m;
	for(;i<n;i++)cin>>a[i];
	sort(a,a+n);
	for(;m--;)
	{
		cin>>x;
		if(binary_search(a,a+n,x))puts("YES");
		else puts("NO");
	} 
}