Ryhmät

#include <iostream>
#include <algorithm>
#include <vector>
#include <span>
using namespace std;

const int MN = 1<<19;

struct T {
	T* left;
	T* right;
	int c;
};
T nodes[20*MN];
int C;

T* roots[MN];

T* add(const T& t, int w, int y) {
	T& n = nodes[C++] = t;
	n.c++;
	if (w>1) {
		int w2=w/2;
		if (y<w2) {
			n.left = add(*n.left, w2, y);
		} else {
			n.right = add(*n.right, w2, y-w2);
		}
	}
	return &n;
}

int count(const T& t, int w, int y1, int y2) {
	if (y1<=0 && y2>=w) return t.c;
	if (y2<=0 || y1>=w) return 0;
	if (t.c==0) return 0;
	int w2=w/2;
	return count(*t.left, w2, y1, y2)
		+ count(*t.right, w2, y1-w2, y2-w2);
}

int findy(const T& plus, const T& minus, int w, int c) {
	if (w<=1) return 0;
	int lc = plus.left->c - minus.left->c;
	int w2=w/2;
	if (lc >= c) return findy(*plus.left, *minus.left, w2, c);
	return w2 + findy(*plus.right, *minus.right, w2, c-lc);
}

struct S {
	int x;
	int y;
};
S stack[MN];

struct I {
	int a,b,i;
};
I cs[MN];
int ks[MN];

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	int n,t;cin>>n>>t;
	for(int i=0;i<n;++i) cin>>cs[i].a>>cs[i].b;
	sort(cs,cs+n,[](auto a, auto b){return a.b<b.b;});
	for(int i=0; i<n; ++i) cs[i].i=i;
	sort(cs,cs+n,[](auto a, auto b){return a.a<b.a;});
	T nullt = {&nullt, &nullt, 0};
	T* curt = &nullt;
	for(int x=0,i=0; x<MN; ++x) {
		for(;i<n && cs[i].a==x; ++i) {
			curt = add(*curt, MN, cs[i].i+1);
		}
		roots[x] = curt;
	}
	sort(cs,cs+n,[](auto a, auto b){return a.b<b.b;});
	while(t--) {
		int m;cin>>m;
		for(int i=0; i<m; ++i) cin>>ks[i];
		sort(ks,ks+m);
		bool ok=1;
		int z=0;
		stack[z++] = {0,MN};
		for(int i=0; i<m && ok; ++i) {
			int k = ks[i];
			if (k != stack[z-1].x) {
				int y = partition_point(cs,cs+n,[k](auto c){return c.b<k;})-cs;
				while(stack[z-1].y <= y) --z;
				stack[z++] = {k, y};
			}
			ok = 0;
			while(z>1) {
				int a = count(*roots[stack[z-1].x], MN, stack[z-1].y+1, stack[z-2].y+1)
					- count(*roots[stack[z-2].x], MN, stack[z-1].y+1, stack[z-2].y+1);
				if (a>=k) {
					int p = count(*roots[stack[z-1].x], MN, 0, stack[z-1].y+1)
						- count(*roots[stack[z-2].x], MN, 0, stack[z-1].y+1);
					stack[z-1].y = findy(*roots[stack[z-1].x], *roots[stack[z-2].x], MN, p+k);
					ok=1;
					break;
				} else {
					k -= a;
					--z;
					stack[z-1].x = stack[z].x;
				}
			}
		}
		cout<<(ok?"YES\n":"NO\n");
	}
}

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: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED