P4560 [IOI 2014] Wall

The original problem was interactive, but here please submit a complete program.

You are given a sequence of length $n$ with all initial values equal to $0$. You need to support the following two operations: - Add $L, R, h$: For all elements in $[L, R]$ that are less than $h$, set them to $h$. Do not change elements whose height is greater than $h$. - Remove $L, R, h$: For all elements in $[L, R]$ that are greater than $h$, set them to $h$. Do not change elements whose height is less than $h$. You need to output the sequence after performing $k$ operations.

The first line contains two positive integers $n, k$, representing the number of elements in the sequence and the number of operations. Note: indices are numbered from $0$ to $n - 1$. Each of the next $k$ lines contains $4$ integers $t, L, R, h$. If $t = 1$, it denotes an Add operation; if $t = 2$, it denotes a Remove operation. The meanings of $L, R, h$ are as described above.

Output $n$ lines. The integer on the $i$-th line is the value of the element with index $i - 1$ after all $k$ operations.

- Subtask #1 (8 points): $1 \leq n \leq 10\,000$, $1 \leq k \leq 5\,000$. - Subtask #2 (24 points): $1 \leq n \leq 100\,000$, $1 \leq k \leq 500\,000$, all Add operations appear before all Remove operations. - Subtask #3 (29 points): $1 \leq n \leq 100\,000$, $1 \leq k \leq 500\,000$. - Subtask #4 (39 points): $1 \leq n \leq 2\,000\,000$, $1 \leq k \leq 500\,000$. Constraints: For all operations, the height $h$ satisfies $0 \leq h \leq 100\,000$. Translated by ChatGPT 5