//Хоёртын хайлт(Binary search)
#include <bits/stdc++.h>
using namespace std;
int n, q, a[200000];
bool BS( int X ) {
// bool гэдэг төрөл нь зөвхөн 0 эсвэл 1 гэсэн утга л авдаг
// Байгаа эсвэл байхгүй гэдгийг мэдэх ёстой тул 1 эсвэл 0
// буцаахад хангалттай юм. TRUE = 1, FALSE = 0
int L = 1, R = n;
// Эхлээд бид 1-ээс n завсарт хайх юм.
while( L <= R ) {
// одоо хайх завсар оршин байх буюу зүүн зах нь баруун
// захаасаа бага буюу тэнцүү тохиолдолд хайсаар байх болно.
int mid = (L+R)/2; // энэ завсрын голын элементийн индекс
if( a[mid] == X ) {
// Нөхцөл 1 буюу энэ тоо байгаа тул бид 1-ыг буцаана.
return true;
}
if( a[mid] > X ) {
// Нөхцөл 2 буюу (mid, mid+1, ... , R) хүртэлх бүх тоо нь
// X-ээс эрс их тул алгасах ба одоо бид L, mid-1 завсарт байгаа
// эсэхийг шалгана.
R = mid-1;
} else {
// Нөхцөл 3 буюу (L, L+1, ... , mid) хүртэлх бүх тоо нь
// X-ээс эрс бага тул алгасах ба одоо бид mid+1, R завсарт байгаа
// эсэхийг шалгана.
L = mid+1;
}
}
// хэрвээ бид хайж дуусаад ямар ч утга буцааж чадаагүй бол энэ тоо
// энэ дараалалд байхгүй гэсэн үг ба 0 гэсэн утга буцаана.
return false;
}
int main() {
cin >> n >> q; // дарааллын урт болон хүсэлтийн тоог уншиж байна.
for(int i = 1; i <= n; i++) {
cin >> a[i]; // дарааллын элементүүдийг унших.
}
while( q-- ) { // q нь 0 ээс ялгаатай бол үргэлжилнэ гэсэн утгатай.
// мөн q нэгээр хасагдана.
int x; cin >> x; // бидний хариулах ёстой тоо.
if( BS( x ) ) {
// if( x ) гэсэн тохиолдолд x-ын утга нь 0 ээс ялгаатай бол үнэн
// энэ тоо дараалалд байгаа гэсэн үг.
cout << "YES" << endl;
} else {
// эсрэг тохиолдолд байхгүй гэсэн үг.
cout << "NO" << endl;
}
}
return 0;
}
Ly/QpdC+0ZHRgNGC0YvQvSDRhdCw0LnQu9GCKEJpbmFyeSBzZWFyY2gpCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKCWludCBuLCBxLCBhWzIwMDAwMF07Cgpib29sIEJTKCBpbnQgWCApIHsKCS8vIGJvb2wg0LPRjdC00Y3QsyDRgtOp0YDTqdC7INC90Ywg0LfTqdCy0YXTqdC9IDAg0Y3RgdCy0Y3QuyAxINCz0Y3RgdGN0L0g0YPRgtCz0LAg0LsgINCw0LLQtNCw0LMKCS8vINCR0LDQudCz0LDQsCDRjdGB0LLRjdC7INCx0LDQudGF0LPSr9C5INCz0Y3QtNCz0LjQudCzINC80Y3QtNGN0YUg0ZHRgdGC0L7QuSDRgtGD0LsgMSDRjdGB0LLRjdC7IDAKCS8vINCx0YPRhtCw0LDRhdCw0LQg0YXQsNC90LPQsNC70YLRgtCw0Lkg0Y7QvC4gVFJVRSA9IDEsIEZBTFNFID0gMAoJaW50IEwgPSAxLCBSID0gbjsKCS8vINCt0YXQu9GN0Y3QtCDQsdC40LQgMS3RjdGN0YEgbiDQt9Cw0LLRgdCw0YDRgiDRhdCw0LnRhSDRjtC8LgoKCXdoaWxlKCBMIDw9IFIgKSB7CgkJLy8g0L7QtNC+0L4g0YXQsNC50YUg0LfQsNCy0YHQsNGAINC+0YDRiNC40L0g0LHQsNC50YUg0LHRg9GO0YMg0LfSr9Kv0L0g0LfQsNGFINC90Ywg0LHQsNGA0YPRg9C9CgkJLy8g0LfQsNGF0LDQsNGB0LDQsCDQsdCw0LPQsCDQsdGD0Y7RgyDRgtGN0L3RhtKv0q8g0YLQvtGF0LjQvtC70LTQvtC70LQg0YXQsNC50YHQsNCw0YAg0LHQsNC50YUg0LHQvtC70L3Qvi4KCQlpbnQgbWlkID0gKEwrUikvMjsgLy8g0Y3QvdGNINC30LDQstGB0YDRi9C9INCz0L7Qu9GL0L0g0Y3Qu9C10LzQtdC90YLQuNC50L0g0LjQvdC00LXQutGBCgkJCgkJaWYoIGFbbWlkXSA9PSBYICkgewoJCQkvLyDQndOp0YXRhtOp0LsgMSDQsdGD0Y7RgyDRjdC90Y0g0YLQvtC+INCx0LDQudCz0LDQsCDRgtGD0Lsg0LHQuNC0IDEt0YvQsyDQsdGD0YbQsNCw0L3QsC4KCQkJcmV0dXJuIHRydWU7CgkJfQoKCQlpZiggYVttaWRdID4gWCApIHsKCQkJLy8g0J3TqdGF0YbTqdC7IDIg0LHRg9GO0YMgKG1pZCwgbWlkKzEsIC4uLiAsIFIpINGF0q/RgNGC0Y3Qu9GFINCx0q/RhSDRgtC+0L4g0L3RjAoJCQkvLyBYLdGN0Y3RgSDRjdGA0YEg0LjRhSDRgtGD0Lsg0LDQu9Cz0LDRgdCw0YUg0LHQsCDQvtC00L7QviDQsdC40LQgTCwgbWlkLTEg0LfQsNCy0YHQsNGA0YIg0LHQsNC50LPQsNCwCgkJCS8vINGN0YHRjdGF0LjQudCzINGI0LDQu9Cz0LDQvdCwLgoJCQlSID0gbWlkLTE7CgkJfSBlbHNlIHsKCQkJLy8g0J3TqdGF0YbTqdC7IDMg0LHRg9GO0YMgKEwsIEwrMSwgLi4uICwgbWlkKSDRhdKv0YDRgtGN0LvRhSDQsdKv0YUg0YLQvtC+INC90YwKCQkJLy8gWC3RjdGN0YEg0Y3RgNGBINCx0LDQs9CwINGC0YPQuyDQsNC70LPQsNGB0LDRhSDQsdCwINC+0LTQvtC+INCx0LjQtCBtaWQrMSwgUiDQt9Cw0LLRgdCw0YDRgiDQsdCw0LnQs9Cw0LAKCQkJLy8g0Y3RgdGN0YXQuNC50LMg0YjQsNC70LPQsNC90LAuCgkJCUwgPSBtaWQrMTsKCQl9Cgl9CgkvLyDRhdGN0YDQstGN0Y0g0LHQuNC0INGF0LDQudC2INC00YPRg9GB0LDQsNC0INGP0LzQsNGAINGHINGD0YLQs9CwINCx0YPRhtCw0LDQtiDRh9Cw0LTQsNCw0LPSr9C5INCx0L7QuyDRjdC90Y0g0YLQvtC+CgkvLyDRjdC90Y0g0LTQsNGA0LDQsNC70LDQu9C0INCx0LDQudGF0LPSr9C5INCz0Y3RgdGN0L0g0q/QsyDQsdCwIDAg0LPRjdGB0Y3QvSDRg9GC0LPQsCDQsdGD0YbQsNCw0L3QsC4KCXJldHVybiBmYWxzZTsKfQoKaW50IG1haW4oKSB7CgljaW4gPj4gbiA+PiBxOyAvLyDQtNCw0YDQsNCw0LvQu9GL0L0g0YPRgNGCINCx0L7Qu9C+0L0g0YXSr9GB0Y3Qu9GC0LjQudC9INGC0L7QvtCzINGD0L3RiNC40LYg0LHQsNC50L3QsC4KCglmb3IoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgewoJCWNpbiA+PiBhW2ldOyAvLyDQtNCw0YDQsNCw0LvQu9GL0L0g0Y3Qu9C10LzQtdC90YLSr9Kv0LTQuNC50LMg0YPQvdGI0LjRhS4KCX0KCgl3aGlsZSggcS0tICkgeyAJLy8gcSDQvdGMIDAg0Y3RjdGBINGP0LvQs9Cw0LDRgtCw0Lkg0LHQvtC7INKv0YDQs9GN0LvQttC40LvQvdGNINCz0Y3RgdGN0L0g0YPRgtCz0LDRgtCw0LkuCgkJCQkJLy8g0LzTqdC9IHEg0L3RjdCz0Y3RjdGAINGF0LDRgdCw0LPQtNCw0L3QsC4KCQlpbnQgeDsgY2luID4+IHg7IC8vINCx0LjQtNC90LjQuSDRhdCw0YDQuNGD0LvQsNGFINGR0YHRgtC+0Lkg0YLQvtC+LgoKCQlpZiggQlMoIHggKSApIHsgCgkJCS8vIGlmKCB4ICkg0LPRjdGB0Y3QvSDRgtC+0YXQuNC+0LvQtNC+0LvQtCB4LdGL0L0g0YPRgtCz0LAg0L3RjCAwINGN0Y3RgSDRj9C70LPQsNCw0YLQsNC5INCx0L7QuyDSr9C90Y3QvQoJCQkvLyDRjdC90Y0g0YLQvtC+INC00LDRgNCw0LDQu9Cw0LvQtCDQsdCw0LnQs9Cw0LAg0LPRjdGB0Y3QvSDSr9CzLgoJCQljb3V0IDw8ICJZRVMiIDw8IGVuZGw7CgkJfSBlbHNlIHsKCQkJLy8g0Y3RgdGA0Y3QsyDRgtC+0YXQuNC+0LvQtNC+0LvQtCDQsdCw0LnRhdCz0q/QuSDQs9GN0YHRjdC9INKv0LMuCgkJCWNvdXQgPDwgIk5PIiA8PCBlbmRsOwoJCX0KCX0KCQoJcmV0dXJuIDA7Cn0=