P9806 [POI 2022/2023 R1] poc

This problem is translated from [POI2022~2023R1 poc](https://sio2.mimuw.edu.pl/c/oi30-1/p/poc/).

Little A and Little B are recording the types of vehicles that passed by. There are $1 \sim k$ types in total, and every vehicle must belong to exactly one of them. Little A carefully recorded the types of all vehicles in order, while playful Little B only recorded some of the vehicles in order. The length of Little A’s record is $n$, and the length of Little B’s record is $m$. We say that the $i$-th vehicle in Little A’s record “may have been recorded by B” if and only if there exists a subsequence of Little A’s record that contains position $i$ and is exactly the same as the sequence recorded by Little B. It is guaranteed that Little B’s sequence is a subsequence of Little A’s sequence. Determine which vehicles may have been recorded by Little B and which may not.

The first line contains three integers $n, m, k \ (1 \leq n, m, k \leq 3 \times 10^5)$. The second line contains a sequence of length $n$, representing the sequence recorded by Little A. The third line contains a sequence of length $m$, representing the sequence recorded by Little B. All elements in the sequences satisfy $1 \leq$ sequence element $\leq k$.

For each vehicle recorded by Little A, determine whether it can be recorded by Little B. Output $1$ if it can, and $0$ otherwise.

For the sample, the following subsequences exist: $(1,2,4,5)$, $(1,2,4,9)$, $(1,2,7,9)$, $(1,6,7,9)$, $(4,6,7,9)$. Note that $3$ and $8$ are never chosen, so they cannot be recorded by Little B. The subtasks are as follows: | Subtask ID | Special Property | Score | | :-----------: | :-----------: | :-----------: | | $1$ | $n, m \leq 100$ | $15$ | | $2$ | $n, m \leq 2000$ | $20$ | | $3$ | Each vehicle type is recorded by Little A at most once | $15$ | | $4$ | No additional constraints | $50$ | Time limit: Subtask 1 1s, Subtask 2 10s, Subtask 3 and Subtask 4 6s. Translated by ChatGPT 5