YZOJ P3706 [APIO2018]新家
时间限制：5000MS 内存限制：1048576KB
难度：\(7.0\)
-
题目描述
五福街是一条笔直的道路，这条道路可以看成一个数轴，街上每个建筑物的坐标都可以用一个整数来表示。
小明是一位时光旅行者，他知道在这条街上，在过去现在和未来共有 \(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 \le n, q \le 3 \times 10^5 , 1 \le k \le n\)）
接下来 \(n\) 行，每行包含四个整数 \(x_i , t_i , a_i\) 和 \(b_i\) 用于描述一家商店，意义如题面所述 （\(1 \le x_i , a_i , b_i \le 10^8 , 1 \le t_i \le k, a_i \le b_i\)）。
接下来 \(q\) 行，每行包含两个整数 \(l_i\) 和 \(y_i\) ，表示一组（坐标，时间）查询 （\(1 \le l_i , y_i \leq 10^8 \)）。
-
输出格式