#P18344. Odd and Even

Odd and Even

Odd and Even

题目描述

给定一个长度为 KK 的整数序列 A=(a1,a2,…,aK)A=(a_1,a_2,\ldots,a_K)。你可以把它划分成若干个非空的连续子数组,每个元素必须且只能属于其中一个子数组。

设划分后,元素和为奇数的子数组有 pp 个,元素和为偶数的子数组有 qq 个。

你需要回答 mm 个相互独立的询问。每个询问给定一个整数 rr,要求把整个序列恰好划分成 rr 个非空连续子数组,并分别求出:

  1. pp 能达到的最大值;
  2. qq 能达到的最大值。

两个最大值分别求取,允许使用不同的划分方案。 不要求输出的两个数之和等于 rr。

由于序列可能很长,输入使用游程编码描述 AA:给出 nn 对整数 (v1,l1),(v2,l2),…,(vn,ln)(v_1,l_1),(v_2,l_2),\ldots,(v_n,l_n)。从空序列开始,依次把 lil_i 个 viv_i 添加到序列末尾,即可得到 AA,因此

K=∑i=1nli.K=\sum_{i=1}^{n}l_i.

输入格式

每个输入文件只有一组测试数据。

第一行包含两个整数 n,mn,m,分别表示游程编码的长度和询问数量。

接下来 nn 行,第 ii 行包含两个整数 vi,liv_i,l_i,表示向序列末尾添加 lil_i 个值为 viv_i 的元素。保证相邻游程的值不同,即 vi≠vi+1v_i\ne v_{i+1}。

接下来 mm 行,每行包含一个整数 rir_i,表示这次询问要求划分成的子数组数量。

输出格式

对每个询问输出一行,包含两个用空格隔开的整数,依次表示恰好划分成 rir_i 个子数组时,奇数和子数组数量的最大值,以及偶数和子数组数量的最大值。

数据范围

  • 1≤n,m≤2×1051\le n,m\le2\times10^5;
  • 1≤vi,li≤1091\le v_i,l_i\le10^9;
  • 相邻游程满足 vi≠vi+1v_i\ne v_{i+1};
  • 1≤ri≤K1\le r_i\le K。

注意,展开长度 KK 可能达到 2×10142\times10^{14}。

样例输入 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).A=(5,5,5,2,2,7).

第二个询问要求划分成两个子数组。

  • 为了让奇数和子数组尽可能多,可以划分为 (5,5,5)∣(2,2,7)(5,5,5)\mid(2,2,7),两段的和都是奇数,因此第一个最大值是 22。
  • 为了让偶数和子数组尽可能多,可以划分为 (5,5)∣(5,2,2,7)(5,5)\mid(5,2,2,7),两段的和都是偶数,因此第二个最大值也是 22。

第五个询问要求划分成五个子数组。

  • 划分为 (5)∣(5)∣(5)∣(2,2)∣(7)(5)\mid(5)\mid(5)\mid(2,2)\mid(7),可以得到 44 个奇数和子数组。
  • 划分为 (5,5)∣(5)∣(2)∣(2)∣(7)(5,5)\mid(5)\mid(2)\mid(2)\mid(7),可以得到 33 个偶数和子数组。