Ryhmät

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

// returns number of elements strictly smaller than v in vec
template<class T>
int bins(const vector<T>& vec, T v) {
	int low = 0;
	int high = vec.size();
	while(low != high) {
		int mid = (low + high) >> 1;
		if (vec[mid] < v) low = mid + 1;
		else high = mid;
	}
	return low;
}

const int N = 1e5;
int apos[N], bpos[N];

void solve(int n, const vector<pair<int, int>>& as, const vector<pair<int, int>>& bs) {
	int m;
	cin >> m;
	
	vector<int> ks(m);
	for (int& k : ks) cin >> k;
	sort(ks.begin(), ks.end());

	set<int> act;
	int cur_ia = 0;
	bool works = 1;
	for (int k : ks) {
		int ia = bins(as, make_pair(k + 1, -1));
		int ib = bins(bs, make_pair(k, -1));

		// Insert new intervals
		for (; cur_ia < ia; ++cur_ia) act.insert(bpos[cur_ia]);
		
		// Delete intervals that end before this
		while(! act.empty()) {
			auto it = act.begin();
			if ((*it) < ib) act.erase(it);
			else break;
		}

		// Assign k greedily
		int cur = 0;
		while(! act.empty() && cur < k) {
			auto it = act.begin();
			act.erase(it);
			++cur;
		}

		if (cur < k) {
			works = 0;
			break;
		}
	}

	if (! works) cout << "NO" << '\n';
	else cout << "YES" << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, t;
	cin >> n >> t;
	
	vector<pair<int, int>> as(n), bs(n);
	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		as[i] = {a, i};
		bs[i] = {b, i};
	}
	sort(as.begin(), as.end());
	sort(bs.begin(), bs.end());

	vector<int> ra(n);
	for (int ja = 0; ja < n; ++ja) ra[as[ja].second] = ja;
	for (int jb = 0; jb < n; ++jb) {
		int i = bs[jb].second;
		int ja = ra[i];
		apos[jb] = ja;
		bpos[ja] = jb;
	}
	
	for (int ti = 0; ti < t; ++ti) solve(n, as, bs);
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED