Ryhmät

input/code.cpp: In function 'std::vector<int> makeIdx(std::span<const int>, std::span<const int>)':
input/code.cpp:21:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::span<const int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |                 while(i < cs.size() && cs[i] < x) ++i;
      |                       ~~^~~~~~~~~~~

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

const int MN = 1<<19;

struct T {
	vector<int> xs;
	vector<int> li;
	vector<int> ri;
};
T tree[2*MN];

vector<int> makeIdx(span<const int> ps, span<const int> cs) {
	vector<int> res;
	res.reserve(ps.size()+1);
	int i=0;
	for(int x: ps) {
		while(i < cs.size() && cs[i] < x) ++i;
		res.push_back(i);
	}
	res.push_back(cs.size());
	return res;
}
void add(int x, int y) {
	for(y+=MN; y>=1; y/=2) {
		tree[y].xs.push_back(x);
	}
}
int rcount(int i1, int i2, int y1, int y2, int i, int l, int r) {
	if (l>=y1 && r<=y2) return i2-i1;
	if (r<=y1 || l>=y2) return 0;
	int m = (l+r)/2;
	return rcount(tree[i].li[i1],tree[i].li[i2],y1,y2,2*i,l,m)
		+ rcount(tree[i].ri[i1],tree[i].ri[i2],y1,y2,2*i+1,m,r);
}
int count(int x1, int x2, int y1, int y2) {
	int i1 = lower_bound(tree[1].xs.begin(), tree[1].xs.end(), x1) - tree[1].xs.begin();
	int i2 = lower_bound(tree[1].xs.begin(), tree[1].xs.end(), x2) - tree[1].xs.begin();
	return rcount(i1,i2,y1,y2,1,0,MN);
}
int findy(int x1, int x2, int c) {
	int i1 = lower_bound(tree[1].xs.begin(), tree[1].xs.end(), x1) - tree[1].xs.begin();
	int i2 = lower_bound(tree[1].xs.begin(), tree[1].xs.end(), x2) - tree[1].xs.begin();
	int i=1;
	int y=0;
	for(int w=MN/2;w>=1;w/=2) {
		int lc = tree[i].li[i2] - tree[i].li[i1];
		if (lc >= c) {
			i1 = tree[i].li[i1];
			i2 = tree[i].li[i2];
			i = 2*i;
		} else {
			c -= lc;
			i1 = tree[i].ri[i1];
			i2 = tree[i].ri[i2];
			i = 2*i+1;
			y += w;
		}
	}
	return y;
}
void build() {
	for(T& t: tree) sort(t.xs.begin(),t.xs.end());
	for(int i=1; i<MN; ++i) {
		tree[i].li = makeIdx(tree[i].xs, tree[2*i].xs);
		tree[i].ri = makeIdx(tree[i].xs, tree[2*i+1].xs);
	}
}

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

typedef pair<int,int> P;
P ps[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>>ps[i].second>>ps[i].first;
	sort(ps,ps+n);
	for(int i=0; i<n; ++i) add(ps[i].second,i+1);
	build();
	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 = lower_bound(ps,ps+n,P(k,0))-ps;
				while(stack[z-1].y <= y) --z;
				stack[z++] = {k, y};
			}
			ok = 0;
			while(z>1) {
				int a = count(stack[z-2].x+1, stack[z-1].x+1, stack[z-1].y+1, stack[z-2].y+1);
				if (a>=k) {
					int p = count(stack[z-2].x+1, stack[z-1].x+1, 0, stack[z-1].y+1);
					stack[z-1].y = findy(stack[z-2].x+1, stack[z-1].x+1, 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