Ryhmät

input/code.cpp: In function 'void solve(int, const std::vector<std::pair<int, int> >&, const std::vector<std::pair<int, int> >&)':
input/code.cpp:264:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::shared_ptr<Tree<2> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  264 |                         for (int i = 0; i < opts.size(); ++i) opts[i] = Tree<D>::prefixDelete(opts[i], ib - 1);
      |                                         ~~^~~~~~~~~~~~~

#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;
}

constexpr ull intPow(ull a, ull b) {
	if (b == 0) return 1;
	if (b & 1) return a * intPow(a, b - 1);
	return intPow(a*a, b / 2);
}

// Persistent merge segment tree
template<int K>
struct Tree {
	private:
		using PTR_T = shared_ptr<Tree<K>>;
		using CHILD_PTR_T = shared_ptr<Tree<K-1>>;
		const static int BS = 2, BF = 3;
		const static int LEN = 64 * BS * intPow(BF, K);
		const static int CHLEN = LEN / BF;

		array<CHILD_PTR_T, BF> ch;
		int popc;
	public:
		static PTR_T zero;

		// Construction; InitTree<K>() must be called first!!
		Tree() : popc(0) {
			for (int j = 0; j < BF; ++j) ch[j] = Tree<K - 1>::zero;
		}

		int count() const { return popc; }
		void print() const { cerr << popc << ' '; ch[0]->print(); }

		// Persistent operations
		static PTR_T clonePtr(PTR_T ptr) { return make_shared<Tree<K>>(*ptr); }

		static PTR_T insert(PTR_T ptr, int x) {
			ptr = clonePtr(ptr);
			auto& obj = *ptr;

			int xj = x / CHLEN;
			obj.popc -= obj.ch[xj]->count();
			obj.ch[xj] = Tree<K-1>::insert(obj.ch[xj], x % CHLEN);
			obj.popc += obj.ch[xj]->count();

			return ptr;
		}
		static PTR_T prefixDelete(PTR_T ptr, int x) {
			ptr = clonePtr(ptr);
			auto& obj = *ptr;

			int xj = x / CHLEN;
			for (int j = 0; j < xj; ++j) {
				obj.popc -= obj.ch[j]->count();
				obj.ch[j] = Tree<K-1>::zero;
			}
			obj.popc -= obj.ch[xj]->count();
			obj.ch[xj] = Tree<K-1>::prefixDelete(obj.ch[xj], x % CHLEN);
			obj.popc += obj.ch[xj]->count();

			return ptr;
		}
		static bool countDelete(vector<PTR_T>& ptrs, const vector<int>& mults, int cou) {
			int k = ptrs.size();

			vector<int> counts(BF, 0);
			for (int i = 0; i < k; ++i) {
				for (int j = 0; j < BF; ++j) {
					counts[j] += (ptrs[i]->ch[j]->count()) * mults[i];
				}
			}
			int xj = 0;
			while(xj < BF && cou > counts[xj]) {
				cou -= counts[xj];
				++xj;
			}
			if (xj >= BF) return false; // there aren't enough elements to delete

			vector<CHILD_PTR_T> rec_ptrs(k);
			for (int i = 0; i < k; ++i) {
				ptrs[i] = clonePtr(ptrs[i]); // Make persistent copy before modifying
				auto& obj = *(ptrs[i]);
				for (int j = 0; j < xj; ++j) {
					obj.popc -= obj.ch[j]->count();
					obj.ch[j] = Tree<K-1>::zero;
				}
				obj.popc -= obj.ch[xj]->count();
				rec_ptrs[i] = obj.ch[xj];
			}

			bool sub = Tree<K-1>::countDelete(rec_ptrs, mults, cou);
			assert(sub == true);

			for (int i = 0; i < k; ++i) {
				ptrs[i]->popc += rec_ptrs[i]->count();
				ptrs[i]->ch[xj] = rec_ptrs[i];
			}
			return true;
		}
};

// Base case of the persistent sparse bitset. All operations are executed naively
template<>
struct Tree<0> {
	private:
		using PTR_T = shared_ptr<Tree<0>>;
		const static int BS = 2;
		array<ull, BS> arr;
		
		// Returns mask where bits {0, ..., x} are set and {x + 1, ..., 63} are not
		static constexpr ull prefMask(int x) {
			return (~0ull) >> (63 - (x & 63));
		}

		// Returns index of nth set bit
		// I don't think there are intrinsics to do this
		// Hopefully the compiler optimizes this for me
		static constexpr int nthSet(ull mask, int n) {
			int res = 0;
			for (int it = 0; it < 6; ++it) {
				int len = 32 >> it;
				ull half = prefMask(len - 1);
				int cou = popcount(mask & half);
				if (cou < n) {
					n -= cou;
					res += len;
					mask >>= len;
				}
			}
			return res;
		}
	public:
		static PTR_T zero;

		// Construction; InitTree<0>() must be called first!!
		Tree() {
			for (int j = 0; j < BS; ++j) arr[j] = 0;	
		}

		int count() const {
			int res = 0;
			for (int j = 0; j < BS; ++j) res += popcount(arr[j]);
			return res;
		}
		void print() const {
			cerr << bitset<64>(arr[0]) << '\n';
		}
		
		// Persistent operations
		static PTR_T clonePtr(PTR_T ptr) { return make_shared<Tree<0>>(*ptr); }

		static PTR_T insert(PTR_T ptr, int x) {
			ptr = clonePtr(ptr);
			
			int xj = x / 64;
			ptr->arr[xj] |= (1ull << (x % 64));
			return ptr;
		}
		static PTR_T prefixDelete(PTR_T ptr, int x) {
			ptr = clonePtr(ptr);
			auto& arr = ptr->arr;

			int xj = x / 64;
			for (int j = 0; j < xj; ++j) arr[j] = 0;
			arr[xj] &= ~prefMask(x);
			return ptr;
		}
		static bool countDelete(vector<PTR_T>& ptrs, const vector<int>& mults, int cou) {
			int k = ptrs.size();

			array<ull, BS> comb = ptrs[0]->arr;
			for (int i = 1; i < k; ++i) {
				for (int j = 0; j < BS; ++j) comb[j] ^= ptrs[i]->arr[j];
			}
			// cerr << "countdelete with comb " << cou << ' ' << bitset<64>(comb[0]) << '\n';

			int xj = 0;
			while(xj < BS && cou > popcount(comb[xj])) {
				cou -= popcount(comb[xj]);
				++xj;
			}
			if (xj >= BS) return false;

			int x = nthSet(comb[xj], cou) + xj * 64;
			// cerr << "countdelete found bit " << x << " of " << bitset<64>(comb[0]) << '\n';
			for (int i = 0; i < k; ++i) ptrs[i] = prefixDelete(ptrs[i], x);
			return true;
		}
};

// Initialize the tree data structure
template<int K>
shared_ptr<Tree<K>> Tree<K>::zero;
shared_ptr<Tree<0>> Tree<0>::zero;

template<int K>
void initTree() {
	initTree<K-1>();
	Tree<K>::zero = make_shared<Tree<K>>();
}
template<>
void initTree<0>() {
	Tree<0>::zero = make_shared<Tree<0>>();
}

// Problem specific
const int N = 1000;
const int THRESHOLD = 10000;
const int D = 2;
int apos[N], bpos[N];
shared_ptr<Tree<D>> prefs[N + 1];

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());

	vector<shared_ptr<Tree<D>>> opts = {Tree<D>::zero};
	vector<int> mults = {1};

	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
		if (ia > cur_ia) {
			int len = ia - cur_ia;
			if (len >= THRESHOLD) {
				// cerr << "Increasing " << cur_ia << ' ' << ia << '\n';
				opts.emplace_back(prefs[ia]);
				opts.emplace_back(prefs[cur_ia]);
				mults.push_back(1);
				mults.push_back(-1);
				cur_ia = ia;
			} else {
				for (; cur_ia < ia; ++cur_ia) {
					// cerr << "Inserting " << bpos[cur_ia] << '\n';
					opts[0] = Tree<D>::insert(opts[0], bpos[cur_ia]);
				}
			}
		}

		// Delete intervals that end before this
		if (ib > 0) {
			// cerr << "Clearing prefix " << ib << '\n';
			for (int i = 0; i < opts.size(); ++i) opts[i] = Tree<D>::prefixDelete(opts[i], ib - 1);
		}

		/*
		cerr << "State when handling " << k << ' ' << ia << ' ' << ib << ' ' << opts.size() << ":\n";
		for (int i = 0; i < opts.size(); ++i) {
			opts[i]->print();
		}
		*/

		// Try to fill
		works &= Tree<D>::countDelete(opts, mults, k);
		
		/*
		cerr << "State after fill: " << works << "\n";
		for (int i = 0; i < opts.size(); ++i) {
			opts[i]->print();
		}
		*/

		// if (! works) 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;
	}

	initTree<D>();
	prefs[0] = Tree<D>::zero;
	for (int i = 1; i <= n; ++i) {
		prefs[i] = Tree<D>::insert(prefs[i-1], bpos[i-1]);
		// prefs[i]->print();
	}
	
	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: RUNTIME ERROR

Test 11

Group: 3

Verdict: RUNTIME ERROR

Test 12

Group: 3

Verdict: RUNTIME ERROR

Test 13

Group: 3

Verdict: RUNTIME ERROR

Test 14

Group: 3

Verdict: RUNTIME ERROR

Test 15

Group: 3

Verdict: RUNTIME ERROR

Test 16

Group: 3

Verdict: RUNTIME ERROR