Polycarp's New Job

题意翻译

题意简述 维护一个初始为空的点集，支持两种操作： $+\ x\ y$：向点集中加入$(x,y)$ $?\ h\ w$：查询是否对于点集中的所有点都满足$x \leq h \&\& y \leq w$或者$x \leq w \&\& y \leq h$ 输入格式 第一行一个整数$n(1 \leq n \leq 5 \times 10^5)$表示操作数 接下来$n$行每行一个操作，格式如上 数据满足$1 \leq x,y,h,w \leq 10^9$，保证至少有一个$?$操作且第一个操作一定是$+$操作 输出格式 对于每一次询问操作输出一行，如果满足条件输出```YES```，否则输出```NO```

题目描述

Polycarp has recently got himself a new job. He now earns so much that his old wallet can't even store all the money he has. Berland bills somehow come in lots of different sizes. However, all of them are shaped as rectangles (possibly squares). All wallets are also produced in form of rectangles (possibly squares). A bill $ x \times y $ fits into some wallet $ h \times w $ if either $ x \le h $ and $ y \le w $ or $ y \le h $ and $ x \le w $ . Bills can overlap with each other in a wallet and an infinite amount of bills can fit into a wallet. That implies that all the bills Polycarp currently have fit into a wallet if every single one of them fits into it independently of the others. Now you are asked to perform the queries of two types: 1. $ +~x~y $ — Polycarp earns a bill of size $ x \times y $ ; 2. $ ?~h~w $ — Polycarp wants to check if all the bills he has earned to this moment fit into a wallet of size $ h \times w $ . It is guaranteed that there is at least one query of type $ 1 $ before the first query of type $ 2 $ and that there is at least one query of type $ 2 $ in the input data. For each query of type $ 2 $ print "YES" if all the bills he has earned to this moment fit into a wallet of given size. Print "NO" otherwise.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2 \le n \le 5 \cdot 10^5 $ ) — the number of queries. Each of the next $ n $ lines contains a query of one of these two types: 1. $ +~x~y $ ( $ 1 \le x, y \le 10^9 $ ) — Polycarp earns a bill of size $ x \times y $ ; 2. $ ?~h~w $ ( $ 1 \le h, w \le 10^9 $ ) — Polycarp wants to check if all the bills he has earned to this moment fit into a wallet of size $ h \times w $ . It is guaranteed that there is at least one query of type $ 1 $ before the first query of type $ 2 $ and that there is at least one query of type $ 2 $ in the input data.

输出格式

For each query of type $ 2 $ print "YES" if all the bills he has earned to this moment fit into a wallet of given size. Print "NO" otherwise.

输入输出样例

输入样例 #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

说明

The queries of type $ 2 $ of the example: 1. Neither bill fits; 2. Both bills fit (just checking that you got that bills can overlap); 3. Both bills fit (both bills are actually the same); 4. All bills fit (too much of free space in a wallet is not a problem); 5. Only bill $ 1 \times 5 $ fit (all the others don't, thus it's "NO").

题意翻译

题意简述 维护一个初始为空的点集，支持两种操作： $+\ x\ y$：向点集中加入$(x,y)$ $?\ h\ w$：查询是否对于点集中的所有点都满足$x \leq h \&\& y \leq w$或者$x \leq w \&\& y \leq h$ 输入格式 第一行一个整数$n(1 \leq n \leq 5 \times 10^5)$表示操作数 接下来$n$行每行一个操作，格式如上 数据满足$1 \leq x,y,h,w \leq 10^9$，保证至少有一个$?$操作且第一个操作一定是$+$操作 输出格式 对于每一次询问操作输出一行，如果满足条件输出```YES```，否则输出```NO```