← 返回题目列表

Codeforces · 1175/E

E. 最小段盖

中文机器翻译题面 查看原题

给定 $$$n$$$ 间隔,格式为 $$$[l; r]$$$ 在数轴上。

您还会收到 $$$m$$$ 形式的查询 $$$[x; y]$$$。您必须采取的最小间隔数是多少,以便从 $$$x$$$ 到 $$$y$$$ 的每个点(不一定是整数)至少被其中一个点覆盖?

如果您无法选择间隔来覆盖从 $$$x$$$ 到 $$$y$$$ 的每个点,则为该查询打印 -1。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — 分别是间隔数和查询数。

接下来的 $$$n$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \le l_i < r_i \le 5 \cdot 10^5$$$) — 给定的间隔。

接下来的 $$$m$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$0 \le x_i < y_i \le 5 \cdot 10^5$$$) — 查询。

输出

打印 $$$m$$$ 整数。第 $$$i$$$ 个数字应该是第 $$$i$$$ 查询的答案:要么是您必须采用的最小间隔数,以便从 $$$x_i$$$ 到 $$$y_i$$$ 的每个点(不一定是整数)至少被其中之一覆盖,要么是 -1(如果您无法选择间隔)以便覆盖从 $$$x_i$$$ 到 $$$y_i$$$ 的每个点。

示例

输入 #1

2 3
1 3
2 4
1 3
1 4
3 4

输出 #1

1
2
1

输入 #2

3 4
1 3
1 3
4 5
1 2
1 3
1 4
1 5

输出 #2

1
1
-1
-1

注意

在第一个示例中,有三个查询:

1.查询$$$[1; 3]$$$可以被区间$$$[1覆盖; 3]$$$;
2.查询$$$[1; 4]$$$ 可以被区间 $$$[1; 覆盖; 3]$$$ 和 $$$[2; 4]$$$。没有办法覆盖$$$[1; 4]$$$ 单个间隔;
3.查询$$$[3; 4]$$$可以被区间$$$[2覆盖; 4]$$$。除了给定的查询之外,涵盖其他点并不重要。

在第二个示例中,有四个查询:

1.查询$$$[1; 2]$$$可以被区间$$$[1覆盖; 3]$$$。请注意,您可以选择两个给定间隔中的任何一个 $$$[1; 3]$$$;
2.查询$$$[1; 3]$$$可以被区间$$$[1覆盖; 3]$$$;
3.查询$$$[1; 4]$$$不能被任何一组区间覆盖;
4.查询$$$[1; 5]$$$ 不能被任何一组区间覆盖。请注意间隔 $$$[1; 3]$$$ 和 $$$[4; 5]$$$ 一起不包括 $$$[1; 5]$$$ 因为即使是非整数点也应该被覆盖。例如,这里的 $$$3.5$$$ 不包括在内。