codeforces-scrape

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

1679C.md (3427B)


      1 Source: https://codeforces.com/problemset/problem/1679/C
      2 
      3 C. Rooks Defenders
      4 
      5 time limit per test
      6 
      7 1 second
      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 You have a square chessboard of size $n \times n$. Rows are numbered from top to bottom with numbers from $1$ to $n$, and columns — from left to right with numbers from $1$ to $n$. So, each cell is denoted with pair of integers $(x, y)$ ($1 \le x, y \le n$), where $x$ is a row number and $y$ is a column number.
     22 
     23 You have to perform $q$ queries of three types:
     24 
     25 * Put a new rook in cell $(x, y)$.
     26 * Remove a rook from cell $(x, y)$. It's guaranteed that the rook was put in this cell before.
     27 * Check if each cell of subrectangle $(x_1, y_1) - (x_2, y_2)$ of the board is attacked by at least one rook.
     28 
     29 Subrectangle is a set of cells $(x, y)$ such that for each cell two conditions are satisfied: $x_1 \le x \le x_2$ and $y_1 \le y \le y_2$.
     30 
     31 Recall that cell $(a, b)$ is attacked by a rook placed in cell $(c, d)$ if either $a = c$ or $b = d$. In particular, the cell containing a rook is attacked by this rook.
     32 
     33 Input
     34 
     35 The first line contains two integers $n$ and $q$ ($1 \le n \le 10^5$, $1 \le q \le 2 \cdot 10^5$) — the size of the chessboard and the number of queries, respectively.
     36 
     37 Each of the following $q$ lines contains description of a query. Description begins with integer $t$ ($t \in \{1, 2, 3\}$) which denotes type of a query:
     38 
     39 * If $t = 1$, two integers $x$ and $y$ follows ($1 \le x, y \le n$) — coordinated of the cell where the new rook should be put in. It's guaranteed that there is no rook in the cell $(x, y)$ at the moment of the given query.
     40 * If $t = 2$, two integers $x$ and $y$ follows ($1 \le x, y \le n$) — coordinates of the cell to remove a rook from. It's guaranteed that there is a rook in the cell $(x, y)$ at the moment of the given query.
     41 * If $t = 3$, four integers $x_1, y_1, x_2$ and $y_2$ follows ($1 \le x_1 \le x_2 \le n$, $1 \le y_1 \le y_2 \le n$) — subrectangle to check if each cell of it is attacked by at least one rook.
     42 
     43 It's guaranteed that among $q$ queries there is at least one query of the third type.
     44 
     45 Output
     46 
     47 Print the answer for each query of the third type in a separate line. Print "Yes" (without quotes) if each cell of the subrectangle is attacked by at least one rook.
     48 
     49 Otherwise print "No" (without quotes).
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 8 10
     57 1 2 4
     58 3 6 2 7 2
     59 1 3 2
     60 3 6 2 7 2
     61 1 4 3
     62 3 2 6 4 8
     63 2 4 3
     64 3 2 6 4 8
     65 1 4 8
     66 3 2 6 4 8
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 No
     73 Yes
     74 Yes
     75 No
     76 Yes
     77 ```
     78 
     79 Note
     80 
     81 Consider example. After the first two queries the board will look like the following picture (the letter $R$ denotes cells in which rooks are located, the subrectangle of the query of the third type is highlighted in green):
     82 
     83  ![](https://espresso.codeforces.com/369760882705dbc8b072dafe06f2c13085b99b38.png) 
     84 
     85 Chessboard after performing the third and the fourth queries:
     86 
     87  ![](https://espresso.codeforces.com/d92eb2b5db0ac3bdfb8f3eb1fe8ef49bce3b3e22.png) 
     88 
     89 Chessboard after performing the fifth and the sixth queries:
     90 
     91  ![](https://espresso.codeforces.com/9496e220401fcae5654664d675b4ee1b45c70e19.png) 
     92 
     93 Chessboard after performing the seventh and the eighth queries:
     94 
     95  ![](https://espresso.codeforces.com/2851a8bb27fd61d462690852c862a361f0146d6f.png) 
     96 
     97 Chessboard after performing the last two queries:
     98 
     99  ![](https://espresso.codeforces.com/c1290cfed0db83ba2a3130f1b07e5ca217fbbdca.png)