Desktop Rearrangement Codeforces Solution | Codeforces Problem Solution 2022

Desktop Rearrangement Codeforces Solution | Codeforces Problem Solution 2022

F. Desktop Rearrangement

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Your friend Ivan asked you to help him rearrange his desktop. The desktop can be represented as a rectangle matrix of size 𝑛×𝑚$n\times m$ consisting of characters '.' (empty cell of the desktop) and '*' (an icon).

The desktop is called good if all its icons are occupying some prefix of full columns and, possibly, the prefix of the next column (and there are no icons outside this figure). In other words, some amount of first columns will be filled with icons and, possibly, some amount of first cells of the next (after the last full column) column will be also filled with icons (and all the icons on the desktop belong to this figure). This is pretty much the same as the real life icons arrangement.

Solution Click Below:-  CLICK HERE

In one move, you can take one icon and move it to any empty cell in the desktop.

Ivan loves to add some icons to his desktop and remove them from it, so he is asking you to answer 𝑞$q$ queries: what is the minimum number of moves required to make the desktop good after adding/removing one icon?

Note that queries are permanent and change the state of the desktop.

Input

The first line of the input contains three integers 𝑛$n$, 𝑚$m$ and 𝑞$q$ (1≤𝑛,𝑚≤1000;1≤𝑞≤2⋅105$1\le n,m\le 1000;1\le q\le 2\cdot {10}^5$) — the number of rows in the desktop, the number of columns in the desktop and the number of queries, respectively.

Number Transformation Codeforces Solution

Remove Directed Edges Codeforces Solution

Desktop Rearrangement Codeforces Solution

Breaking the Wall Codeforces Solution

A-B-C Sort Codeforces Solution

Infinite Replacement Codeforces Solution 

The next 𝑛$n$ lines contain the description of the desktop. The 𝑖$i$-th of them contains 𝑚$m$ characters '.' and '*' — the description of the 𝑖$i$-th row of the desktop.

The next 𝑞$q$ lines describe queries. The 𝑖$i$-th of them contains two integers 𝑥𝑖$x_i$ and 𝑦𝑖$y_i$ (1≤𝑥𝑖≤𝑛;1≤𝑦𝑖≤𝑚$1\le x_i\le n;1\le y_i\le m$) — the position of the cell which changes its state (if this cell contained the icon before, then this icon is removed, otherwise an icon appears in this cell).

Output

Print 𝑞$q$ integers. The 𝑖$i$-th of them should be the minimum number of moves required to make the desktop good after applying the first 𝑖$i$ queries.

Join Now for Solution:-