DMOPC '21 Contest 8 P6 - Castle Building - Olympiads Online Judge

DMOPC '21 Contest 8 P6 - Castle Building

Points: 40 (partial)

Time limit: 3.0s

Memory limit: 256M

Author:

Problem type

Billy is playing with his newly bought Lego set containing $N$ $N$ blocks with distinct heights from $1$ $1$ to $N$ $N$ . He would like to build a castle with these blocks, which involves arranging the blocks in a row where the heights from left to right are $h_1, h_2, \dots, h_N$ $h_{1}, h_{2}, \dots, h_{N}$ such that there is some index $i$ $i$ $(1 \le i \le N)$ $(1 \leq i \leq N)$ where the heights are strictly increasing from $1$ $1$ to $i$ $i$ and strictly decreasing from $i$ $i$ to $N$ $N$ . Formally, $h_1 < h_2 < \dots < h_i > \dots > h_{N-1} > h_N$ $h_{1} < h_{2} < \dots < h_{i} > \dots > h_{N - 1} > h_{N}$ .

To help guide him, Billy found an old, worn out instruction manual from the bottom of his bed. The instructions give the required heights of each building block $a_1, a_2, \dots, a_N$ $a_{1}, a_{2}, \dots, a_{N}$ from left to right. However, some of these numbers are so smudged that he cannot determine what they are! These are denoted with $a_i = 0$ $a_{i} = 0$ . Furthermore, Billy revises his interpretation of the instructions $Q$ $Q$ times, where he assumes that the number at index $q_i$ $q_{i}$ is actually $v_i$ $v_{i}$ .

Perplexed, Billy runs to you for help. Initially and after each of the $Q$ $Q$ revisions, tell Billy if there exists a castle consistent with the instructions.

Constraints

$1 \le N \le 2 \times 10^5$ $1 \leq N \leq 2 \times 10^{5}$

$0 \le Q \le 2 \times 10^5$ $0 \leq Q \leq 2 \times 10^{5}$

$0 \le a_i \le N$ $0 \leq a_{i} \leq N$

$1 \le q_i \le N$ $1 \leq q_{i} \leq N$

$0 \le v_i \le N$ $0 \leq v_{i} \leq N$

Initially and after each of the $Q$ $Q$ revisions, the instructions contain no duplicates of positive values.

Subtask 1 [30%]

$Q = 0$ $Q = 0$

Subtask 2 [40%]

$a_{\left\lfloor\frac{N+1}{2}\right\rfloor} = N$ $a_{⌊ \frac{N + 1}{2} ⌋} = N$

$q_i \ne \left\lfloor\frac{N+1}{2}\right\rfloor$ $q_{i} \neq ⌊ \frac{N + 1}{2} ⌋$

Subtask 3 [30%]

No additional constraints.

Input Specification

The first line contains $2$ $2$ integers $N$ $N$ and $Q$ $Q$ .

The next line contains $N$ $N$ integers, the initial instructions $a_1, a_2, \dots, a_N$ $a_{1}, a_{2}, \dots, a_{N}$ .

Each of the next $Q$ $Q$ lines contains the description of a revision, $2$ $2$ integers $q_i$ $q_{i}$ and $v_i$ $v_{i}$ .

Output Specification

Initially and after each of the $Q$ $Q$ revisions, output YES if there exists a castle consistent with the instructions and NO otherwise.

Sample Input

Copy

9 3
1 0 0 5 0 0 8 0 2
5 9
7 0
5 0

Sample Output

Copy

YES
NO
YES
YES

Explanation

Initially, 1 3 4 5 7 9 8 6 2 is a possible castle.

After the first revision, the instructions are 1 0 0 5 9 0 8 0 2, which has no consistent castle.

After the second revision, the instructions are 1 0 0 5 9 0 0 0 2, and 1 3 4 5 9 8 7 6 2 is a possible castle.

After the third revision, the instructions are 1 0 0 5 0 0 0 0 2, which has a few possible castles.

Comments

There are no comments at the moment.