codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1101E.md (2614B)


      1 Source: https://codeforces.com/problemset/problem/1101/E
      2 
      3 E. Polycarp's New Job
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 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).
     24 
     25 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.
     26 
     27 Now you are asked to perform the queries of two types:
     28 
     29 1. $+~x~y$ — Polycarp earns a bill of size $x \times y$;
     30 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$.
     31 
     32 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.
     33 
     34 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.
     35 
     36 Input
     37 
     38 The first line contains a single integer $n$ ($2 \le n \le 5 \cdot 10^5$) — the number of queries.
     39 
     40 Each of the next $n$ lines contains a query of one of these two types:
     41 
     42 1. $+~x~y$ ($1 \le x, y \le 10^9$) — Polycarp earns a bill of size $x \times y$;
     43 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$.
     44 
     45 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.
     46 
     47 Output
     48 
     49 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.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 9
     57 + 3 2
     58 + 2 3
     59 ? 1 20
     60 ? 3 3
     61 ? 2 3
     62 + 1 5
     63 ? 10 10
     64 ? 1 5
     65 + 1 1
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 NO
     72 YES
     73 YES
     74 YES
     75 NO
     76 ```
     77 
     78 Note
     79 
     80 The queries of type $2$ of the example:
     81 
     82 1. Neither bill fits;
     83 2. Both bills fit (just checking that you got that bills can overlap);
     84 3. Both bills fit (both bills are actually the same);
     85 4. All bills fit (too much of free space in a wallet is not a problem);
     86 5. Only bill $1 \times 5$ fit (all the others don't, thus it's "NO").