← 返回题目列表

Codeforces · 1710/B

B. 雨

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

您是一块收割田的所有者,该田地可以建模为一条无限线,其位置由整数标识。

接下来 $$$n$$$ 天将会下雨。在第 $$$i$$$ 天,降雨将集中在位置 $$$x_i$$$,强度为 $$$p_i$$$。由于这些降雨,部分降雨量将会累积;令 $$$a_j$$$ 为整数位置 $$$j$$$ 处累积的降雨量。最初 $$$a_j$$$ 为 $$$0$$$,第 $$$i$$$ 天下雨后,$$$\max(0,p_i-|x_i-j|)$$$ 会增加 $$$。

如果在任何时刻,某个位置 $$$j$$$ 的累积降雨量为 $$$a_j>m$$$,洪水就会袭击你的田地。

你可以使用魔法咒语准确地消除一天的雨,即设置$$$p_i=0$$$。对于从$$$1$$$到$$$n$$$的每个$$$i$$$,检查在消除第$$$i$$$天的降雨的情况下是否没有洪水。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq m \leq 10^9$$$) — 下雨天数和不发生洪水的最大累积降雨量。

然后是 $$$n$$$ 行。这些行中的第 $$$i$$$ 包含两个整数 $$$x_i$$$ 和 $$$p_i$$$ ($$$1 \leq x_i,p_i \leq 10^9$$$) — 第 $$$i$$$ 天的降雨位置和强度。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个二进制字符串 $$$s$$$ 长度为 $$$n$$$。如果清除第$$$i$$$天的降雨后没有发生洪水,则$$$s$$$的第$$$i$$$字符为1;如果清除第$$$i$$$天的降雨后仍然发生洪水,则$$$i$$$的第$$$i$$$字符为0。

示例

输入 #1

4
3 6
1 5
5 5
3 4
2 3
1 3
5 2
2 5
1 6
10 6
6 12
4 5
1 6
12 5
5 5
9 7
8 3

输出 #1

001
11
00
100110

注意

在第一个测试用例中,如果我们不使用该咒语,累计降雨量分布将是这样的:

如果我们消除第三天的降雨,就可以避免洪水,累积降雨量分布如下:

在第二个测试用例中,由于最初不会发生洪水,因此我们可以消除任何一天的降雨。

在第三个测试用例中,没有办法避免洪水。