Rooks Defenders Codeforces Solution | Codeforces Problem Solution 2022

Rooks Defenders Codeforces Solution | Codeforces Problem Solution 2022

C. Rooks Defenders

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You have a square chessboard of size 𝑛×𝑛$n\times n$. Rows are numbered from top to bottom with numbers from 1$1$ to 𝑛$n$, and columns — from left to right with numbers from 1$1$ to 𝑛$n$. So, each cell is denoted with pair of integers (𝑥,𝑦)$(x,y)$ (1≤𝑥,𝑦≤𝑛$1\le x,y\le n$), where 𝑥$x$ is a row number and 𝑦$y$ is a column number.

Solution Click Below:-  CLICK HERE

You have to perform 𝑞$q$ queries of three types:

• Put a new rook in cell (𝑥,𝑦)$(x,y)$.
• Remove a rook from cell (𝑥,𝑦)$(x,y)$. It's guaranteed that the rook was put in this cell before.
• Check if each cell of subrectangle (𝑥1,𝑦1)−(𝑥2,𝑦2)$(x_1,y_1)-(x_2,y_2)$ of the board is attacked by at least one rook.

Subrectangle is a set of cells (𝑥,𝑦)$(x,y)$ such that for each cell two conditions are satisfied: 𝑥1≤𝑥≤𝑥2$x_1\le x\le x_2$ and 𝑦1≤𝑦≤𝑦2$y_1\le y\le y_2$.

AvtoBus Codeforces Solution

Stone Age Problem Codeforces Solution

Rooks Defenders Codeforces Solution

Toss a Coin to Your Graph... Codeforces Solution

Typical Party in Dorm Codeforces Solution

Formalism for Formalism Codeforces Solution 

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.

Input

The first line contains three integers 𝑛$n$ and 𝑞$q$ (1≤𝑛≤105$1\le n\le {10}^5$, 1≤𝑞≤2⋅105$1\le q\le 2\cdot {10}^5$) — the size of the chessboard and the number of queries, respectively.

Each of the following 𝑞$q$ lines contains description of a query. Description begins with integer 𝑡$t$ (𝑡∈{1,2,3}$t\in \{1,2,3\}$) which denotes type of a query:

• If 𝑡=1$t=1$, two integers 𝑥$x$ and 𝑦$y$ follows (1≤𝑥,𝑦≤𝑛$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.
• If 𝑡=2$t=2$, two integers 𝑥$x$ and 𝑦$y$ follows (1≤𝑥,𝑦≤𝑛$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.
• If 𝑡=3$t=3$, four integers 𝑥1,𝑦1,𝑥2$x_1,y_1,x_2$ and 𝑦2$y_2$ follows (1≤𝑥1≤𝑥2≤𝑛$1\le x_1\le x_2\le n$, 1≤𝑦1≤𝑦2≤𝑛$1\le y_1\le y_2\le n$) — subrectangle to check if each cell of it is attacked by at least one rook.

It's guaranteed that among 𝑞$q$ queries there is at least one query of the third type.

Output

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.

Otherwise print "No" (without quotes).

Join Now for Solution:-