← 返回题目列表

Codeforces · 1810/D

D. 爬树

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

蜗牛正在爬树。树高为 $$$h$$$ 米,蜗牛从位置 $$$0$$$ 开始。

每只蜗牛都有两个属性 $$$a$$$ 和 $$$b$$$ ($$$a > b$$$)。从第$$$1$$$天开始,一只蜗牛这样爬树:白天,他爬$$$a$$$米;白天,他爬$$$a$$$米;白天,他爬$$$a$$$米。晚上,蜗牛休息,他从 $$$b$$$ 米处滑下来。如果在第$$$n$$$天,蜗牛第一次到达位置$$$h$$$(即树顶),他就爬完了,我们就说蜗牛爬树的时间为$$$n$$$天。请注意,在攀爬的最后一天,蜗牛不一定会爬上 $$$a$$$ 米,以防它到顶峰的距离小于 $$$a$$$。

不幸的是,你一开始并不知道确切的树高 $$$h$$$,但你知道 $$$h$$$ 是一个正整数。有两种 $$$q$$$ 事件。

- $$$1$$$ 类型的事件:属性为 $$$a$$$、$$$b$$$ 的蜗牛来了,并声称他花了 $$$n$$$ 天爬树。如果此消息与先前采用的信息相矛盾(即不存在所有先前采用的语句和此语句均正确的树),请忽略它。否则,采纳吧。
- $$$2$$$ 类型的事件:属性为 $$$a$$$、$$$b$$$ 的蜗牛来问你,如果他爬上树,他会花多少天。你只能根据目前所掌握的信息给出答案。如果您无法准确确定答案,请报告。

你需要按顺序处理所有事件。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是他们的描述。

每个测试用例的第一行包含一个整数 $$$q$$$ ($$$1\le q \le 2\cdot 10^5$$$) — 事件数。

对于以下 $$$q$$$ 行,每行的第一个整数是 $$$1$$$ 或 $$$2$$$,表示事件类型。

如果事件类型为 $$$1$$$,则后面跟随三个整数 $$$a$$$、$$$b$$$ 和 $$$n$$$ ($$$1\le a,b,n \le 10^9$$$, $$$a>b$$$)。

如果事件类型为 $$$2$$$,则后面跟着两个整数 $$$a$$$ 和 $$$b$$$ ($$$1\le a,b \le 10^9$$$, $$$a>b$$$)。

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

输出

对于每个测试用例,在一行中输出 $$$q$$$ 个整数,每个事件按顺序输出一个整数。具体来说,

- 对于$$$1$$$类型的每个事件,如果采用该消息,则输出$$$1$$$;如果忽略,则输出$$$0$$$;
- 对于 $$$2$$$ 类型的每个事件,输出一个整数,表示蜗牛将度过的天数。如果无法确定,则输出$$$-1$$$。

示例

输入 #1

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

输出 #1

1 2 5
1 -1 1
1 0 1
1 0 -1 0 0 0 1 8 0
1 0 0 1 0 0 0 0 1

注意

在第一个测试用例中,我们可以通过第一条消息确定 $$$h=7$$$,因此我们知道第二只蜗牛和第三只蜗牛分别需要花费 $$$2$$$ 和 $$$5$$$ 天才能到达顶部。

让我们展示第二只蜗牛是如何攀爬的:

- 在$$$1$$$第一天的白天:爬升$$$4$$$米,目前位于$$$4$$$位置。
- 在$$$1$$$第一天的晚上:滑下$$$1$$$米,现在位于$$$3$$$位置。
- 在第 $$$2$$$ 天的白天:爬升 $$$4$$$ 米,目前位于 $$$7$$$ 位置(到达顶部)。

在第三个测试用例中,第二只蜗牛的消息与第一只蜗牛的消息相矛盾,因为第二只蜗牛说他花了$$$3$$$天,并且他在前$$$3$$$天内最多可以爬$$$1+1+2=4$$$米。然而,第一只蜗牛只需要 $$$1$$$ 天即可爬升 $$$4$$$ 米。