#P3661. [USACO17FEB] Why Did the Cow Cross the Road I S

[USACO17FEB] Why Did the Cow Cross the Road I S

题目背景

征求翻译。如果你能提供翻译(不接受百度翻译等机器翻译)或者题意简述,请直接发讨论,感谢你的贡献。

题目描述

Farmer John's cows are trying to learn to cross the road effectively. Remembering the old "why did the chicken cross the road?" joke, they figure the chickens must be experts on crossing the road, and go off in search of chickens to help them.

农夫约翰的牛们正在尝试去学会高效地穿越马路。熟知经典的笑话“为什么鸡要过马路?”,他们想到鸡一定是过马路的专家,便动身寻找能够帮助它们的鸡。

As it turns out, chickens are very busy creatures and have limited time to help the cows. There are CC chickens on the farm (1C20,0001 \leq C \leq 20,000), conveniently numbered 1C1 \ldots C, and each chicken ii is only willing to help a cow at precisely time TiT_i. The cows, never in a hurry, have more flexibility in their schedules. There are NN cows on the farm (1N20,0001 \leq N \leq 20,000), conveniently numbered 1N1 \ldots N, where cow jj is able to cross the road between time AjA_j and time BjB_j. Figuring the "buddy system" is the best way to proceed, each cow jj would ideally like to find a chicken ii to help her cross the road; in order for their schedules to be compatible, ii and jj must satisfy AjTiBjA_j \leq T_i \leq B_j.

牛们发现,鸡是一种特别繁忙的动物,并且只有一定的时间来帮助它们。农场上共有CC 只鸡(1C200001\le C\le 20000),十分便利地被编号为1...C1...C, 而且,每只鸡ii 只有恰好在时间TiT_{i} 时才会愿意帮助牛们。而从不慌张的牛们,有更加灵活的时间安排。农场上共有NN 只牛(1N200001\le N\le 20000),也十分便利地被编号为1...N1...N,牛jj 在时间AjA_{j}BjB_{j} 之间可以穿过马路。想到“小伙伴系统”是最好的行进方式,每只牛jj 会理想地愿意找到一只鸡ii 来帮助她穿过马路;为了是它们的时间表不冲突,iijj 必须满足AjTiBjA_{j}\le T_{i}\le B_{j}

If each cow can be paired with at most one chicken and each chicken with at most one cow, please help compute the maximum number of cow-chicken pairs that can be constructed.

如果每头奶牛最多只能配一只鸡,而每只鸡最多只配上一头牛,请帮忙计算出可以构造的牛鸡对的最大数量。

输入格式

The first line of input contains CC and NN. The next CC lines contain T1TCT_1 \ldots T_C, and the next NN lines contain AjA_j and BjB_j (AjBjA_j \leq B_j) for j=1Nj = 1 \ldots N. The AA's, BB's, and TT's are all non-negative integers (not necessarily distinct) of size at most 1,000,000,000

第一行的输入包括CCNN。下面的CC 行包括T1...TCT1...TC,再接下来的NN 行包括AjA_{j}BjB_{j}(AjBjA_{j}\le B_{j}),j=1...Nj=1...N。所有A,BA,BTT 都是非负整数(可能相等),并皆小于等于1,000,000,0001,000,000,000

输出格式

Please compute the maximum possible number of cow-chicken pairs.

请计算最大的可行牛-鸡配对数。

5 4
7
8
6
2
9
2 5
4 9
0 3
8 13
3

提示

感谢@Darkins 提供翻译