DMOPC '21 Contest 8 P6 - Castle Building

View as PDF

Submit solution


Points: 40 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem type

Billy is playing with his newly bought Lego set containing N blocks with distinct heights from 1 to 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 such that there is some index i (1 \le i \le N) where the heights are strictly increasing from 1 to i and strictly decreasing from i to N. Formally, 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 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. Furthermore, Billy revises his interpretation of the instructions Q times, where he assumes that the number at index q_i is actually v_i.

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

Constraints

1 \le N \le 2 \times 10^5

0 \le Q \le 2 \times 10^5

0 \le a_i \le N

1 \le q_i \le N

0 \le v_i \le N

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

Subtask 1 [30%]

Q = 0

Subtask 2 [40%]

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

q_i \ne \left\lfloor\frac{N+1}{2}\right\rfloor

Subtask 3 [30%]

No additional constraints.

Input Specification

The first line contains 2 integers N and Q.

The next line contains N integers, the initial instructions a_1, a_2, \dots, a_N.

Each of the next Q lines contains the description of a revision, 2 integers q_i and v_i.

Output Specification

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

Sample Input

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

Sample Output

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.