Odd and Even
题目描述
给定一个长度为 K 的整数序列 A=(a1,a2,…,aK)。你可以把它划分成若干个非空的连续子数组,每个元素必须且只能属于其中一个子数组。
设划分后,元素和为奇数的子数组有 p 个,元素和为偶数的子数组有 q 个。
你需要回答 m 个相互独立的询问。每个询问给定一个整数 r,要求把整个序列恰好划分成 r 个非空连续子数组,并分别求出:
- p 能达到的最大值;
- q 能达到的最大值。
两个最大值分别求取,允许使用不同的划分方案。 不要求输出的两个数之和等于 r。
由于序列可能很长,输入使用游程编码描述 A:给出 n 对整数 (v1,l1),(v2,l2),…,(vn,ln)。从空序列开始,依次把 li 个 vi 添加到序列末尾,即可得到 A,因此
K=i=1∑nli.
输入格式
每个输入文件只有一组测试数据。
第一行包含两个整数 n,m,分别表示游程编码的长度和询问数量。
接下来 n 行,第 i 行包含两个整数 vi,li,表示向序列末尾添加 li 个值为 vi 的元素。保证相邻游程的值不同,即 vi=vi+1。
接下来 m 行,每行包含一个整数 ri,表示这次询问要求划分成的子数组数量。
输出格式
对每个询问输出一行,包含两个用空格隔开的整数,依次表示恰好划分成 ri 个子数组时,奇数和子数组数量的最大值,以及偶数和子数组数量的最大值。
数据范围
- 1≤n,m≤2×105;
- 1≤vi,li≤109;
- 相邻游程满足 vi=vi+1;
- 1≤ri≤K。
注意,展开长度 K 可能达到 2×1014。
样例输入 1
3 6
5 3
2 2
7 1
1
2
3
4
5
6
样例输出 1
0 1
2 2
2 1
4 2
4 3
4 2
样例说明
展开后的序列为
A=(5,5,5,2,2,7).
第二个询问要求划分成两个子数组。
- 为了让奇数和子数组尽可能多,可以划分为 (5,5,5)∣(2,2,7),两段的和都是奇数,因此第一个最大值是 2。
- 为了让偶数和子数组尽可能多,可以划分为 (5,5)∣(5,2,2,7),两段的和都是偶数,因此第二个最大值也是 2。
第五个询问要求划分成五个子数组。
- 划分为 (5)∣(5)∣(5)∣(2,2)∣(7),可以得到 4 个奇数和子数组。
- 划分为 (5,5)∣(5)∣(2)∣(2)∣(7),可以得到 3 个偶数和子数组。