YZOJ P3706 [APIO2018]新家

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 \))。

  • 输出格式

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

YZOJ P3392 越野赛车问题

YZOJ P3392 越野赛车问题

时间限制:1000MS      内存限制:262144KB

难度: \(6.0\)

  • 问题描述

某山上一共有 \(n\) 个广场,编号依次为 \(1\) 到 \(n\),这些广场之间通过 \(n-1\) 条双向车道直接或间接地连接在一起。对于每条车道 \(i\),可以用四个正整数 \(u_i, v_i, l_i, r_i\) 描述,表示车道连接广场 \(u_i\) 和 \(v_i\),其速度承受区间为 \([l_i, r_i]\),即汽车必须以不小于 \(l_i\) 且不大于 \(r_i\) 的速度经过车道 \(i\) 。

现计划进行 \(m\) 次训练,每次选择某山上的一条简单路径,然后在这条路径上行驶,且每次训练时的车速都是固定的。现在有在 m 次训练中分别计划使用的车速,要求一条合法的路径(车速在所有车道的速度承受区间的交集内),使得路径上经过的车道数最大

  • 数据输入

输入文件的第一行包含两个正整数 \(n, m\),表示广场数和训练次数。接下来 \(n-1\) 行,每行四个正整数 \(u_i, v_i, l_i, r_i ( \leq n)\),描述所有车道。最后 \(m\) 行,每行一个正整数 \(v (\leq n)\) ,表示每次训练是的车速。

  • 结果输出

输出 \(m\) 行,输出每次训练时的行驶路径经过的最大车道数。

  • 样例输入

  • 样例输出