#2585. 「APIO2018」新家

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

题目描述

五福街是一条笔直的道路,这条道路可以看成一个数轴,街上每个建筑物的坐标都可以用一个整数来表示。小明是一位时光旅行者,他知道在这条街上,在过去现在和未来共有 n 个商店出现。第 i 个商店可以使用四个整数 x_i, t_i, a_i, b_i 描述,它们分别表示:商店的坐标、商店的类型、商店开业的年份、商店关闭的年份。

小明希望通过时光旅行,选择一个合适的时间,住在五福街上的某个地方。他给出了一份他可能选择的列表,上面包括了 q 个询问,每个询问用二元组(坐标,时间)表示。第 i 对二元组用两个整数 l_i, y_i 描述,分别表示选择的地点 l_i 和年份 y_i

现在,他想计算出在这些时间和地点居住的生活质量。他定义居住的不方便指数为:在居住的年份,离居住点最远的商店类型到居住点的距离。类型 t 的商店到居住点的距离定义为:在指定的年份,类型 t 的所有营业的商店中,到居住点距离最近的一家到居住点的距离。我们说编号为 i 的商店在第 y 年在营业当且仅当 a_i \leq y \leq b_i 。注意,在某些年份中,可能在五福街上并非所有 k 种类型的商店都有至少一家在营业。在这种情况下,不方便指数定义为 −1。你的任务是帮助小明求出每对(坐标,时间)二元组居住的不方便指数。

输入格式

第一行包含三个整数 n k q ,分别表示商店的数量、商店类型的数量和(坐标,时间)二元组的数量。 (1\leq n,q\leq 3\times 10^5,1\leq k \leq n)
接下来 n 行,每行包含四个整数 x_i, t_i, a_i , 和 b_i 用于描述一家商店,意义如题面所述 (1\leq x_i,a_i,b_i \leq 10^9,1\leq t_i \leq k,a_i \leq b_i)
接下来 q 行,每行包含两个整数 l_i , 和 y_i ,表示一组(坐标,时间)查询 (1\leq l_i,y_i \leq 10^8)

输出格式

对于每组询问输出一个整数,包含 q 个整数,依次表示对于 q 组(坐标,时间)询问求出的结果。

样例

样例输入1

4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

样例输出1

4
2
-1
-1

样例输入2

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

样例输出2

0
0
-1

样例输入3

1 1 1
100000000 1 1 1
1 1

样例输出3

99999999

样例解释

在第一个样例中,有 4 家商店,共 2 种类型,还有 4 个询问。

  • 对于第一个询问:小明在第 3 年住在坐标为 5 的地方。这一年中,编号为 1 和 2 的商店在营业,到编号为 1 的商店的距离为 2 ,到编号为 2 的商店距离为 4 ,所以最大距离为4。

  • 对于第二个询问:小明在第 6 年住在坐标为 5 的地方。这一年中,编号为 1 和 3 的商店在营业,到编号为 1 的商店的距离为 2 ,到编号为 3 的商店距离为 2 ,所以最大距离为2。

  • 对于第三个询问:小明在第 9 年住在坐标为 5 的地方。这一年中,编号为 1 和 4 的商店在营业,它们的类型都为 1,没有类型为 2 的商店在营业,所以答案为 −1 。

  • 同样的情况出现在第四个询问中。

在第二个样例中,有 2 家商店,共 1 种类型,还有三个询问。 两家商店的类型都是 1 。在所有的询问中,小明均住在坐标为 1 的地方。 在前两个询问中,至少有一个商店在营业,所以答案为 0 ,在第三个询问中,两个商店都不在营业,所以答案为 −1 。

在第三个样例中,有 1 家商店和 1 个询问,两者之间的距离是 99999999 。

数据范围与提示

子任务 1(5 分): n,q\leq 400

子任务 2(7 分): n,q\leq 6\times 10^4,k\leq 400

子任务 3(10 分): n,q\leq 3\times 10^5 ,对于所有的商店 a_i=1,b_i=10^8

子任务 4(23 分): n,q\leq 3\times 10^5 ,对于所有的商店 a_i=1

子任务 5(35 分): n,q\leq 6\times 10^4

子任务 6(20 分): n,q\leq 3\times 10^5