#1479. 廊桥分配

廊桥分配

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

当一架飞机抵达机场时,可以停靠在航站楼旁的廊桥,也可以停靠在位于机场边缘的远机位。

乘客一般更期待停靠在廊桥,因为这样省去了坐摆渡车前往航站楼的周折。

然而,因为廊桥的数量有限,所以这样的愿望不总是能实现。

机场分为国内区和国际区,国内航班飞机只能停靠在国内区,国际航班飞机只能停靠在国际区。

一部分廊桥属于国内区,其余的廊桥属于国际区。

L\red L 市新建了一座机场,一共有 n\red n 个廊桥。

该机场决定,廊桥的使用遵循“先到先得”的原则,即每架飞机抵达后,如果相应的区(国内/国际)还有空闲的廊桥,就停靠在廊桥,否则停靠在远机位(假设远机位的数量充足)。

该机场只有一条跑道,因此不存在两架飞机同时抵达的情况。

现给定未来一段时间飞机的抵达、离开时刻,请你负责将 n\red n 个廊桥分配给国内区和国际区,使停靠廊桥的飞机数量最多。

输入格式

输入的第一行,包含三个正整数 n\red n,m1\red {m_1},m2\red {m_2},分别表示廊桥的个数、国内航班飞机的数量、国际航班飞机的数量。

接下来 m1\red {m_1} 行,是国内航班的信息,第 i\red i 行包含两个正整数 a1,i,b1,i\red {a_{1,i},b_{1,i}},分别表示一架国内航班飞机的抵达、离开时刻。

接下来 m2\red {m_2} 行,是国际航班的信息,第 i\red i 行包含两个正整数 a2,i,b2,i\red {a_{2,i},b_{2,i}},分别表示一架国际航班飞机的抵达、离开时刻。

每行的多个整数由空格分隔。

输出格式

输出一个正整数,表示能够停靠廊桥的飞机数量的最大值。

样例

输入样例1

3 5 4
1 5
3 8
6 10
9 14
13 18
2 11
4 15
7 17
12 16

输出样例1

7

输入样例2

2 4 6
20 30
40 50
21 22
41 42
1 19
2 18
3 4
5 6
7 8
9 10

输出样例2

4

提示

样例解释

img

在图中,我们用抵达、离开时刻的数对来代表一架飞机,如 (1,5\red {1,5}) 表示时刻 1\red 1 抵达、时刻 5\red 5 离开的飞机;用 \red {√} 表示该飞机停靠在廊桥,用 ×\red {×} 表示该飞机停靠在远机位。

我们以表格中阴影部分的计算方式为例,说明该表的含义。

在这一部分中,国际区有 2\red 2 个廊桥,4\red 4 架国际航班飞机依如下次序抵达:

  • 1. 首先 (2,11\red {2,11}) 在时刻 2\red {2} 抵达,停靠在廊桥。
  • 2. 然后 (4,15\red {4,15}) 在时刻 4\red {4} 抵达,停靠在另一个廊桥。
  • 3. 接着 (7,17\red {7,17}) 在时刻 7\red {7} 抵达,这时前 2\red {2} 架飞机都还没离开、都还占用着廊桥,而国际区只有 2\red 2 个廊桥,所以只能停靠远机位。
  • 4. 最后 (12,16\red {12,16}) 在时刻 12\red {12} 抵达,这时 (2,11\red {2,11}) 这架飞机已经离开,所以有 1\red 1 个空闲的廊桥,该飞机可以停靠在廊桥。

根据表格中的计算结果,当国内区分配 2\red 2 个廊桥、国际区分配 1\red 1 个廊桥时,停靠廊桥的飞机数量最多,一共 7\red 7 架。

样例解释2

当国内区分配 2\red 2 个廊桥、国际区分配 0\red 0 个廊桥时,停靠廊桥的飞机数量最多,一共 4\red 4 架,即所有的国内航班飞机都能停靠在廊桥。

需要注意的是,本题中廊桥的使用遵循“先到先得”的原则,如果国际区只有 1\red 1 个廊桥,那么将被飞机 (1,19\red {1,19}) 占用,而不会被 (3,4\red {3,4})、(5,6\red {5,6})、(7,8\red {7,8})、(9,10\red {9,10}) 这 4\red 4 架飞机先后使用。

数据范围

对于 20%\red {20\%} 的数据,n100m1+m2100\red {n≤100,m_1+m_2≤100}

对于 40%\red {40\%} 的数据,n5000m1+m25000\red {n≤5000,m_1+m_2≤5000}

对于 100%\red {100\%} 的数据,1n105m1,m21m1+m2105\red {1≤n≤10^5,m_1,m_2≥1,m_1+m_2≤10^5},所有 a1,i,b1,i,a2,i,b2,i\red {a_{1,i},b_{1,i},a_{2,i},b_{2,i}} 为数值不超过 108\red {10^8} 的互不相同的正整数,且保证对于每个 i[1,m1]\red {i∈[1,m_1]},都有 a1,i<b1,i\red {a_{1,i}<b_{1,i}},以及对于每个 i[1,m2]\red {i∈[1,m_2]},都有 a2,i<b2,i\red {a_{2,i}<b_{2,i}}

2020年CSP-S第二轮重现

未参加
状态
已结束
规则
IOI
题目
4
开始于
2023-10-11 9:45
结束于
2023-10-19 17:45
持续时间
200 小时
主持人
参赛人数
15