← 返回题目列表

Codeforces · 1101/E

E. 坡旅甲的新工作

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

波利卡普最近给自己找到了一份新工作。他现在赚的钱太多了,他的旧钱包甚至都装不下所有的钱了。

Berland 钞票不知何故有多种不同尺寸。然而,它们的形状都是矩形(可能是正方形)。所有钱包也以矩形(可能是正方形)的形式生产。

如果 $$$x \le h$$$ 和 $$$y \le w$$$ 或 $$$y \le h$$$ 和 $$$x \le w$$$ ,则一张钞票 $$$x \times y$$$ 适合某个钱包 $$$h \times w$$$。钱包中的钞票可以相互重叠,并且钱包中可以容纳无限数量的钞票。这意味着波利卡普当前拥有的所有钞票都可以装进钱包,前提是每张钞票都独立于其他钞票放入钱包中。

现在要求您执行两种类型的查询:

1. $$$+~x~y$$$ — Polycarp 赚取一张 $$$x \times y$$$ 的钞票;
2. $$$?~h~w$$$ — Polycarp 想要检查他目前赚到的所有账单是否能装进大小为 $$$h \times w$$$ 的钱包。

保证在第一个 $$$2$$$ 类型的查询之前至少有一个 $$$1$$$ 类型的查询,并且输入数据中至少有一个 $$$2$$$ 类型的查询。

对于 $$$2$$$ 类型的每个查询,如果他目前赚取的所有账单都适合给定大小的钱包,则打印“YES”。否则打印“NO”。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — 查询数。

接下来的 $$$n$$$ 行中的每一行都包含以下两种类型之一的查询:

1. $$$+~x~y$$$ ($$$1 \le x, y \le 10^9$$$) — Polycarp 赚取一张 $$$x \times y$$$ 的钞票;
2. $$$?~h~w$$$ ($$$1 \le h, w \le 10^9$$$) — Polycarp 想要检查他目前赚到的所有账单是否都适合 $$$h \times w$$$ 大小的钱包。

保证在第一个 $$$2$$$ 类型的查询之前至少有一个 $$$1$$$ 类型的查询,并且输入数据中至少有一个 $$$2$$$ 类型的查询。

输出

对于 $$$2$$$ 类型的每个查询,如果他目前赚取的所有账单都适合给定大小的钱包,则打印“YES”。否则打印“NO”。

示例

输入 #1

9
+ 3 2
+ 2 3
? 1 20
? 3 3
? 2 3
+ 1 5
? 10 10
? 1 5
+ 1 1

输出 #1

NO
YES
YES
YES
NO

注意

示例中$$$2$$$类型的查询:

1. 两项法案都不适合;
2. 两张钞票都适合(只需检查钞票是否可以重叠);
3. 两张钞票都适合(两张钞票实际上是一样的);
4. 所有钞票都适合(钱包里太多可用空间不是问题);
5. 仅账单 $$$1 \times 5$$$ 适合(所有其他不适合,因此为“NO”)。