比赛场次 614
比赛名称 2024暑期C班集训4
比赛状态 已结束比赛成绩
开始时间 2024-07-04 08:00:00
结束时间 2024-07-04 12:00:00
开放分组 全部用户
注释介绍 3 + 1
题目名称 梦境
输入输出 dream.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar┭┮﹏┭┮ AAAAAAAAAA 0.239 s 2.41 MiB 100
Gravatar小金 AAAAAAAAAA 0.353 s 2.46 MiB 100
Gravatarliuyiche AAAAAAAAAA 0.388 s 1.88 MiB 100
Gravatarwdsjl AAAAAAAAAA 0.388 s 2.64 MiB 100
GravatarUntitled AAAAAAAAAA 0.432 s 2.46 MiB 100
Gravatarwzh0425 AAAAAAATTT 3.009 s 4.39 MiB 70
Gravatar陆晨洗 AAAAAAATTT 3.025 s 5.16 MiB 70
Gravatar彭欣越 AAAAAWWEEE 0.652 s 3.29 MiB 50
GravatardarkMoon AAAAAWWEEE 2.457 s 3.95 MiB 50
Gravatar123 AAAAAWWTTT 3.000 s 2.63 MiB 50
GravatarAeeE5x AAAWWWWWWW 0.305 s 2.53 MiB 30
Gravatar蜀山鸭梨大 AAAWWWWWWW 0.743 s 2.41 MiB 30
Gravatardjyqjy WWWAAWWTTT 3.000 s 3.15 MiB 20
Gravatarflyfree MMMMMMMMMM 0.000 s 0.00 MiB 0
Gravatardream WWWWWWWWWW 0.796 s 2.86 MiB 0
Gravatar健康铀 WWWWWWWWWW 1.789 s 4.12 MiB 0

梦境

★☆   输入文件:dream.in   输出文件:dream.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

智者奥尔曼曾说过:有缘的人即使相隔海角天涯,也会在梦境中相遇。

IcePrince 和 IcePrincess 便是如此。有一天 IcePrincess 突发奇想:为什么不用梦境操控仪器来增加她和 IcePrince 的缘分呢?

IcePrincess 的梦境可以用 $n$ 个区间来表示,第 $i$ 个区间 $[l_i,r_i]$ 表示她的第 $i$ 个梦境会在 $l_i$ 时刻开始,在 $r_i$ 时刻结束(包含 $l_i$ 和 $r_i$ 两个时刻)。因为 IcePrincess 经常做白日梦,所以 $n$ 可能很大。

两个人的梦境不是什么时候都能融合的。只有在一些关键的与另一个人相关的梦境转折点两个人的梦境相遇,才能完成融合,形成浪漫的梦境。IcePrincess探测到IcePrince近期的 m 个与 IcePrincess相关的梦境转折点,第 i 个转折点 ti 表示他的第 i 个梦境转折点会在 ti 时刻出现。因为 IcePrince和 IcePrincess很有缘,IcePrince经常梦到 IcePrincess,所以 m 可能会很大。

当 IcePrincess 的一个梦境包含了 IcePrince 的一个梦境转折点时,两个人的这两段梦境就能得到融合。但要注意 IcePrincess 的每段梦境只能和 IcePrince 的一个梦境转折点融合,类似的,IcePrince 的每个梦境转折点只能和 IcePrincess的一段梦境融合,否则会引发时空混乱。

IcePrincess 很喜欢做和 IcePrince 相关的梦。所以她想算出她的这些梦境最多能和 IcePrince 的梦境转折点融合出多少个浪漫的梦境。IcePrincess 擅长文学但不擅长计算机,所以只能找你帮忙。

【输入格式】

文件的第一行为有两个正整数 n,m,表示 IcePrincess 的梦境个数和 IcePrince的与 IcePrincess相关的梦境转折点个数。

第 2 至第 n+1 行,每行两个正整数 li,ri,第 i+1 行的两个数刻画了 IcePrincess的第 i 段梦境,含义如题面中所述。

第 n+2 至第 n+m+1 行,每行一个正数 ti,第 i 行的两个数刻画了 IcePrinc 的第 i-n-1个梦境转折点,含义如题面中所述。

【输出格式】

输出文件仅一行,一个非负整数 N 表示 IcePrincess 最多能获得多少段浪漫的梦境。

【样例输入1】

2 2
1 3
2 4
1
3

【样例输出1】

2

【提示】

IcePrincess 可以将自己的第一段梦境和第一个梦境转折点匹配,第二段梦境和第二个梦境转折点匹配,从而获得两段浪漫的梦境。因为 IcePrincess 一共只做了两个梦,所以这一定是最多的数量。

【样例输入2】

5 7 
4 7
3 5
5 8
1 3
6 8
6 
2 
4 
1 
7 
8 
9

【样例输出2】

5

【数据规模与约定】

对于 30%的数据,n<=10,m<=10;

对于 50%的数据,n<=100,m<=100;

对于 70%的数据,n<=2000,m<=2000;

对于 100%的数据,n<=200,000,m<=200,000,1<=li,ri<=1,000,000,000,1<=ti<=1,000,000,000,保证对于每段梦境,li<=ri。

大洋里