思路

显然，我们不需要构造一个矩阵，只需要判断是否存在。

那么，我们可以使用 Gale-Ryser 定理：

给定两个非负整数数列 $p_1 \ge p_2 \ge \dots \ge p_n$ 以及 $q_1 \le q_2 \le \dots \le q_m$ 满足 $\sum_{i=1}^{n} p_i = \sum_{i=1}^{m} q_i$，存在一个 $n \times m$ 的 01 矩阵满足每一行的和为 $p_{1 \sim n}$，每一列和为 $q_{1 \sim m}$ 的充要条件为 $\forall k \in [1,n],\sum_{i=1}^{k} p_i \le \sum_{i=1}^{m} \min(q_i,k)$。

:::info[证明] 一个 $n \times m$ 的 01 矩阵 $A = (a_{i,j})$ 可自然对应一个二分图，其左部点为 $x_1,\dots,x_n$，右部点为 $y_1,\dots,y_m$。不妨设 $\forall i \in [1,n],\deg(x_i) = p_i,\forall i \in [1,m],\deg(y_i) = q_i$。

必要性：
对于左部的任意 $k$ 个点，看它们的度数之和。对于每一个右部点 $y_i$，它最多和左部的 $k$ 个点中的 $\min(q_i,k)$ 个有边相连。因此左部任意的 $k$ 个点度数之和 $\le \sum_{i=1}^{m} \min(q_i,k)$。
所以重要性得证。

充分性：
这个定理的充分性要么感性理解，要么归纳构造，所以自己想办法吧。绝对不是因为我不会。 ::: 然后就解决了。

然后我们考虑如何快速计算 $\sum_{i=1}^{m} \min(q_i,k)$。
我们可以先预处理出所需行数和保镖数的前缀和数组，那么在判断的时候就可以用二分查找实现了。

时间复杂度：$O(n\log n)$。

:::success[代码]

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
int n,m,l,r,sum1,sum2,v[200005],h[200005],s[200005];
pii a[200005],b[200005];
inline int check(int k){
	int x=upper_bound(v,v+n,k)-v;//二分 
	return s[x]+(h[n]-h[x])*k;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> a[i].fi >> a[i].se;
		r+=a[i].fi*a[i].se;
	}
	cin >> m;
	for(int i=0;i<m;i++){
		cin >> b[i].fi >> b[i].se;
		l+=b[i].fi*b[i].se;
	}
	if(r!=l) cout << 0,exit(0);
	sort(a,a+n);
	sort(b,b+m,greater<pii>());//倒序排序 
	for(int i=0;i<n;i++){
		v[i]=a[i].fi;
		h[i+1]=h[i]+a[i].se;//行数的前缀和 
		s[i+1]=s[i]+a[i].fi*a[i].se;//保镖数的前缀和 
	}
	for(int i=0;i<m;i++){
		sum1+=b[i].se;
		sum2+=b[i].fi*b[i].se;
		if(sum2>check(sum1)) cout << 0,exit(0);
	}
	cout << 1;
	return 0;
}

:::