比赛场次 | 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 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
┭┮﹏┭┮ | AAAAAAAAAA | 0.239 s | 2.41 MiB | 100 |
小金 | AAAAAAAAAA | 0.353 s | 2.46 MiB | 100 |
liuyiche | AAAAAAAAAA | 0.388 s | 1.88 MiB | 100 |
wdsjl | AAAAAAAAAA | 0.388 s | 2.64 MiB | 100 |
Untitled | AAAAAAAAAA | 0.432 s | 2.46 MiB | 100 |
wzh0425 | AAAAAAATTT | 3.009 s | 4.39 MiB | 70 |
陆晨洗 | AAAAAAATTT | 3.025 s | 5.16 MiB | 70 |
彭欣越 | AAAAAWWEEE | 0.652 s | 3.29 MiB | 50 |
darkMoon | AAAAAWWEEE | 2.457 s | 3.95 MiB | 50 |
123 | AAAAAWWTTT | 3.000 s | 2.63 MiB | 50 |
AeeE5x | AAAWWWWWWW | 0.305 s | 2.53 MiB | 30 |
蜀山鸭梨大 | AAAWWWWWWW | 0.743 s | 2.41 MiB | 30 |
djyqjy | WWWAAWWTTT | 3.000 s | 3.15 MiB | 20 |
flyfree | MMMMMMMMMM | 0.000 s | 0.00 MiB | 0 |
dream | WWWWWWWWWW | 0.796 s | 2.86 MiB | 0 |
健康铀 | WWWWWWWWWW | 1.789 s | 4.12 MiB | 0 |
智者奥尔曼曾说过:有缘的人即使相隔海角天涯,也会在梦境中相遇。
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 最多能获得多少段浪漫的梦境。
2 2 1 3 2 4 1 3
2
IcePrincess 可以将自己的第一段梦境和第一个梦境转折点匹配,第二段梦境和第二个梦境转折点匹配,从而获得两段浪漫的梦境。因为 IcePrincess 一共只做了两个梦,所以这一定是最多的数量。
5 7 4 7 3 5 5 8 1 3 6 8 6 2 4 1 7 8 9
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。