#2775. 「BalticOI 2018」火星人的 DNA

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Mingqi_H

题目描述

题目译自 BalticOI 2018 Day1「Martian DNA

给定一个字符集大小 |\Sigma| = K 的长度为 N 的字符串和 R 个要求,每个要求为使子串中的字符 B 至少出现 Q 次。求出满足所有要求的最短子串长度。

输入格式

第一行包括三个整数 N,\, K,\, R ,分别表示字符串的长度、字符集的大小和要求个数,保证 1\leqslant R\leqslant K\leqslant N
第二行包含 N 个用空格隔开的整数,表示这个字符串。字符从 0 开始编号,每个字符集中的字符至少出现一次。
接下来的 R 行,每行两个整数 B Q ,表示一组要求,满足 0\leqslant B < K,\, 1\leqslant Q\leqslant N ,同一个字符不会被重复要求两次。

输出格式

输出一个整数,满足所有要求的最短子串长度。特别地,如果不存在这样的子串,输出 "impossible"。

样例

样例输入 1

5 2 2
0 1 1 0 1
0 1
1 1

样例输出 1

2

样例 1 解释

有三个长度为 2 的子串含有字符 0 1 各一个,分别为 0 11 00 1,但是不存在长度为 1 的子串满足要求,因此满足要求的最短子串的长度为 2

样例输入 2

13 4 3
1 1 3 2 0 1 2 0 0 0 0 3 1
0 2
2 1
1 2

样例输出 2

7

样例 2 解释

最短的满足要求的子串为 1 3 2 0 1 2 0

样例输入 3

5 3 1
1 2 0 1 2
0 2

样例输出 3

impossible

样例 3 解释

在这个字符串中,0 的数量不足。

数据范围与提示

子任务 分值 限制
1 16 1\leqslant N\leqslant 100,\, R\leqslant 10
2 24 1\leqslant N\leqslant 4\, 000,\, R\leqslant 10
3 28 1\leqslant N\leqslant 200\, 000,\, R\leqslant 10
4 32 1\leqslant N\leqslant 200\, 000

请注意在 LibreOJ 上共有 5 个子任务,其中第一个子任务为样例。