← 返回题目列表

Codeforces · 2002/E

E. 宇宙射线

中文机器翻译题面 查看原题

给定一个整数数组$$$s_1, s_2, \ldots, s_l$$$,每一秒,宇宙射线都会导致所有$$$s_i$$$同时被删除,使得$$$i=1$$$或$$$s_i\neq s_{i-1}$$$被同时删除,剩下的部分将被连接在一起以形成新的数组$$$s_1、s_2、\ldots、s_{l'}$$$。

将数组的强度定义为变空所需的秒数。

给您一个以 $$$n$$$ 对的形式压缩的整数数组,这些对从左到右描述该数组。每对 $$$(a_i,b_i)$$$ 代表 $$$a_i$$$ 的 $$$b_i$$$ 副本,即 $$$\underbrace{b_i,b_i,\cdots,b_i}_{a_i\textrm{ times}}$$$。

对于每个 $$$i=1,2,\dots,n$$$,请找出前 $$$i$$$ 对描述的序列的强度。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\le t\le10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le3\cdot10^5$$$) — 序列 $$$a$$$ 的长度。

接下来的 $$$n$$$ 行包含两个整数,每个 $$$a_i$$$, $$$b_i$$$ ($$$1\le a_i\le10^9,0\le b_i\le n$$$) - 描述序列的对。

保证所有$$$n$$$的总和不超过$$$3\cdot10^5$$$。

保证对于所有 $$$1\le i<n$$$,$$$b_i\neq b_{i+1}$$$ 成立。

输出

对于每个测试用例,打印一行包含 $$$n$$$ 整数 - 每个前缀对的答案。

示例

输入 #1

4
4
2 0
1 1
3 0
5 1
6
4 6
1 3
4 6
4 0
7 6
6 3
7
9 0
7 1
5 0
7 1
9 0
1 1
2 0
10
10 7
4 9
2 2
7 9
2 8
8 5
11 7
15 5
12 7
4 0

输出 #1

2 2 4 5 
4 4 7 7 10 10 
9 9 9 9 9 9 10 
10 10 10 10 10 10 12 15 15 15

注意

在第一个测试用例中,对于长度 $$$4$$$ 的前缀,更改将为 $$$[0,0,1,0,0,0,1,1,1,1,1]\rightarrow[0,0,0,1,1,1,1]\rightarrow[0,0,1,1,1]\rightarrow[0,1,1]\rightarrow[1]\rightarrow[]$$$,因此数组在 $$$5$$$ 秒后变空。

在第二个测试用例中,对于长度 $$$4$$$ 的前缀,更改将为$$$[6,6,6,6,3,6,6,6,6,0,0,0,0]\rightarrow[6,6,6,6,6,6,0,0,0]\rightarrow[6,6,6,6,6,0,0]\rightarrow[6,6,6,6,0]\rightarrow[6,6,6]\rightarrow[6,6]\rightarrow[6]\rightarrow[]$$$,所以$$$7$$$ 秒后数组变空。