{"problem":{"name":"[POI 2022/2023 R1] poc","description":{"content":"小 A 和小 B 在记录过往的车辆的类型！ 已知类型分别有 $1 \\sim k$ 个，每种车辆必然属于其中之一。 小 A 按顺序细心地记录了所有的车辆的类型，但是贪玩的小 B 只按顺序记录了一部分车辆。 小 A 记录的内容长度为 $n$，小 B 记录的长度为 $m$。 称在小 A 记录中的第 $i$ 辆车“可能被 B 记录到”当且仅当在小 A 的记录中存在一个包含 $i$ 的子序列与小 B","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9806"},"statements":[{"statement_type":"Markdown","content":"小 A 和小 B 在记录过往的车辆的类型！\n\n已知类型分别有 $1 \\sim k$ 个，每种车辆必然属于其中之一。\n\n小 A 按顺序细心地记录了所有的车辆的类型，但是贪玩的小 B 只按顺序记录了一部分车辆。\n\n小 A 记录的内容长度为 $n$，小 B 记录的长度为 $m$。\n\n称在小 A 记录中的第 $i$ 辆车“可能被 B 记录到”当且仅当在小 A 的记录中存在一个包含 $i$ 的子序列与小 B 所记录的完全相同。\n\n保证小 B 记录的序列一定是小 A 记录的子序列，问哪些车辆是可能会被小 B 记录到，哪些没有。\n\n## Input\n\n第一行三个整数 $n,m,k \\ (1 \\leq n,m,k \\leq 3 \\times 10^5)$。\n\n第二行一个长度为 $n$ 的序列，表示小 A 记录的序列。\n\n第三行一个长度为 $m$ 的序列，表示小 B 记录的序列。\n\n上述序列中的元素均满足 $1\\leq$ 序列元素 $\\leq k$。\n\n## Output\n\n对于每个小 A 记录到的车辆，请确定它能否被记录到，能输出 $1$，不能输出 $0$。\n\n[samples]\n\n## Background\n\n题目译自 [POI2022~2023R1 poc](https://sio2.mimuw.edu.pl/c/oi30-1/p/poc/)。\n\n## Note\n\n对于样例，存在如下的子序列：\n\n$(1,2,4,5)$，$(1,2,4,9)$，$(1,2,7,9)$，$(1,6,7,9)$，$(4,6,7,9)$。\n\n注意到 $3$ 和 $8$ 一直都没被取到，故不能被小 B 记录到。\n\n子任务分配如下：\n\n| 子任务编号 | 特殊性质 | 分值 |\n| :-----------: | :-----------: | :-----------: |\n| $1$ | $n,m \\leq 100$ | $15$ |\n| $2$ | $n,m \\leq 2000$ | $20$ |\n| $3$ | 每种类型的车辆最多被小 A 记录一次 | $15$ |\n| $4$ | 无附加限制 | $50$ |\n\n时间限制：Subtask1 1s，Subtask2 10s，Subtask3 和 Subtask4 6s。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9806","tags":["POI（波兰）","2022","2023"],"sample_group":[["9 4 3\n1 3 2 1 2 3 1 3 2\n1 3 1 2\n","1 1 0 1 1 1 1 0 1"]],"created_at":"2026-03-03 11:09:25"}}