2797:积木-4

时间限制:2 S   /  内存限制:65536 KB
AC:4   /  Submit:26
问题描述

有 n 堆积木,初始时每堆积木的数量都为零,涂涂很无聊,于是他重复了 m 次以下操作:

向区间 [L,R] 内的每堆积木中添加一个,即对于 L <= i <= R,a[i] += 1。

这时罗少来了,他给出了一个他认为好看的积木序列,涂涂希望再经过一次上述操作后,每堆积木的数量与罗少给出序列对应位置上的数字尽可能多的相同。

比如涂涂经过 m 次操作完以后积木的数量为:1 1 2 3 2,罗少给出的积木序列为:2 2 3 3 3,那么涂涂可以向区间 [1,3] 内的每堆积木都添加一个使其变成:2 2 3 3 2,如此以来对应位置相同的数量就为 4(第1、2、3、4堆对应相同),当然,涂涂也可以选择向区间 [1,5] 内的每堆积木都添加一个使其变成:2 2 3 4 3,这样对应位置相同的数量也为 4(第1、2、3、5堆对应相同)。

值得注意的是,如果罗少给出的序列与涂涂操作完 m 次以后的积木数量完全一致时,涂涂可以选择放弃最后的操作。

输入描述

第一行是一个正整数 n 代表积木的堆数。(1 <= n <= 100000)

然后是一个正整数 m 代表涂涂操作的次数。(1 <= m <= 100000)

接下来 m 行,每行包含两个数字代表 L 和 R。(1 <= L <= R <= n)

最后是 n 个整数,代表罗少给出的积木序列。

输出描述

最多可以有多少堆积木的数量与罗少给出序列对应位置的数字相等,不要换行。

样例输入复制样例

5

3

1 5

3 5

4 4

2 2 3 3 3

样例输出

4

提示说明

样例就是描述中的例子。

相关

19-20(2)第4次线上赛


Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1