#P2010. [Ceoi2010]bodyguard

    ID: 1034 传统题 1000ms 259MiB 尝试: 86 已通过: 30 难度: 8 上传者: 标签>CF2400提高+/省选-二分图建模Gale–Ryser 定理一维前缀和同向双指针

[Ceoi2010]bodyguard

[CEOI2010 day1] bodyguards

题目描述

在一个矩阵中,需要在一些行和列上安排目标数量的保镖。每个位置可以放置一名保镖。你需要求出能否安排出一种方案,使得一些行、列上恰好有目标数量的保镖?

输入格式

输入第一行一个整数 RR,表示共有 RR 条行上的约束。

接下来的 RR 行,每行两个整数 a,ba,b,表示有 bb 行需要恰好包含 aa 名保镖。

接下来的一行一个整数 CC,表示共有 CC 条列上的约束。

接下来的 CC 行,每行两个整数 x,yx,y,表示有 yy 列需要恰好包含 xx 名保镖。

输出格式

输出一行一个数字。如果存在这样的方案,输出 1;否则输出 0。

样例 #1

样例输入 #1

2
2 1
1 2
1
2 2

样例输出 #1

1

样例 #2

样例输入 #2

2
3 2
1 1
2
3 2
1 1

样例输出 #2

0

提示

样例 1 解释

有一行需要包含两名保镖,两行需要包含一名保镖;两列需要包含两名保镖,一种方案如下:

XX
X.
.X

其中 X 表示保镖,. 表示空位。

样例 2 解释

有两行必须全部是保镖,但是有一列却要仅有一名保镖,无法实现,故无解。

数据规模与约定

  • 对于 50%50\% 的数据,保证 R,C≤2000R,C\le 2000,最多有 10610^6 名保镖;
  • 对于 100%100\% 的数据,保证保镖总数最多为 101810^{18},所有数字均为不超过 10910^9 的正整数,1≤R,C≤2×1051\le R,C\le 2\times 10^5。