Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
E. Валера ба хүсэлтүүд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 512 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Валера хэрчимд их дуртай. Тэрээр нэгэн сонирхолтой бодлого олсон гэн.
Координатын $Ox$ тэнхлэг дээр $n$ хэрчим байгаа бөгөөд $i$-р хэрчим $l_i$ байрлалаас эхэлж $r_i$ байрлал дээр дуусна (Үүнийг $[l_i, r_i]$ гэж тэмдэглэе). Чиний даалгавар бол $m$ ширхэг хүсэлтэнд хариулах юм. Хүсэлт бүрт $cnt_i$ тоо болон $cnt_i$ ширхэг элементтэй координатын $Ox$ тэнхлэг дээр байрлах цэгүүдийн олонлог өгөгдөнө. Асуулгын хариулт нь хичнээн хэрчим нь асуулгад өгөгдсөн цэгүүдээс багадаа нэгийг агуулж байгааг олох юм. Хэрвээ $l ≤ q ≤ r$ бол хэрчим $[l_i, r_i]$ нь $q$ цэгийг агуулж байна гэсэн үг.
Валера энэ бодлогын хариуг олоход хүнд байсан учраас чамаас тусламж хүсчээ. Валерад туслана уу!
Оролт
Эхний мөрөнд хэрчмийн тоо $n$, хүсэлтийн тоо $m$ ($1 ≤ n, m ≤ 3·10^5$) байна.
Дараачийн $n$ мөрөнд хэрчим бүрийн тодорхойлолт буюу мөр бүрт хоёр бүхэл тоог агуулна $l_i$, $r_i$ ($1 ≤ li ≤ ri ≤ 10^6$) - хэрчмийн хоёр хил.
Дараачийн $m$ мөрөнд асуулга бүрийн тодорхойлолт буюу мөрийн эхэнд бүхэл тоо $cnt_i$ ($1 ≤ cnti ≤ 3·10^5$) - $i$ -р асуулгын цэгүүдийн тоо. Үүний араас $cnt_i$ ширхэг ялгаатай бүхэл тоонууд $p_1, p_2, ... , p_{cnt_{i}}$ ($1 ≤ p_1 < p_2 < ... < p_{cnt_{i}} ≤ 10^6$) - $i$-р асуулгын цэгүүд.
Цэгүүдийн тоо болон асуулгын тоо $3·10^5$ хэтрэхгүй.
Гаралт
$m$ ширхэг асуулгын хариултыг хэвлэх ба $i$-р асуулгын хариуг $i$-р мөрөнд хэвлэ.
Орчуулсан: byambadorjp
Жишээ тэстүүд
Оролт
3 3 1 3 4 5 6 7 3 1 4 7 2 4 5 1 8
Гаралт
3 1 0