P11353 [NOISG 2024 Finals] Field

Stuart the Snail 住在一片田野上，这片田野可以被描述为一个无限的二维平面。在田野的每个整数坐标点上都有可以吃的植物，而 Stuart 的家位于原点 $(0, 0)$。 下雨了，Stuart 能够轻松地在田野上移动。每小时他可以选择一个相邻的植物坐标移动过去并吃掉它。具体来说，如果他当前在 $(x, y)$，他可以移动到 $(x+1, y)$、$(x, y+1)$、$(x-1, y)$ 或 $(x, y-1)$。他可以在雨停前继续移动，也可以选择停止并停留在某个植物上，包括留在原地。 然而，田野中有 $n$ 个深水坑，每个水坑覆盖一个矩形区域，Stuart 无法安全地通过。水坑 $i$ 的覆盖范围是满足 $a_i \leq x \leq b_i$ 且 $c_i \leq y \leq d_i$ 的所有整数坐标点。注意，水坑可能存在重叠。 你需要回答 $q$ 个查询，每个查询的类型由 $t$ 指定： - 如果 $t = 1$，查询 Stuart 从原点移动到 $(x_j, y_j)$ 所需的最短时间（以小时为单位）。如果无法到达目的地，输出 $-1$。 - 如果 $t = 2$，假设雨将持续 $m_j$ 小时，计算 Stuart 在最多 $m_j$ 小时内可以到达的不同位置数量。

- 第一行包含三个整数 $n$、$t$ 和 $q$，分别表示水坑数量、查询类型和查询数量。 - 接下来的 $n$ 行中，每行包含四个整数 $a_i$、$b_i$、$c_i$ 和 $d_i$，表示水坑 $i$ 的范围。 - 如果 $t = 1$，接下来的 $q$ 行每行包含两个整数 $x_j$ 和 $y_j$，表示查询的目标坐标。 - 如果 $t = 2$，接下来的 $q$ 行每行包含一个整数 $m_j$，表示雨的持续时间。

- 对于每个查询，输出一个整数作为答案： - 如果 $t = 1$，输出 Stuart 到达目标位置的最短时间；如果无法到达，输出 $-1$。 - 如果 $t = 2$，输出 Stuart 在最多 $m_j$ 小时内可以到达的不同位置数量。

【样例解释】 对于样例 #1： - Stuart 可以在 $3$ 小时内到达 $(3, 3)$。 - Stuart 无法到达 $(2, -3)$，因为目标位置被水坑覆盖。 对于样例 #2： - Stuart 在 $1$ 小时内可以到达 $4$ 个不同的位置。 - 在 $2$ 小时内，可以到达 $8$ 个位置。 【数据范围】 - $1 \leq n \leq 400$ - $1 \leq t \leq 2$ - $1 \leq q \leq 200,000$ - $-10^9 \leq a_i \leq b_i \leq 10^9$ - $-10^9 \leq c_i \leq d_i \leq 10^9$ - 原点 $(0, 0)$ 不被任何水坑覆盖。 - 如果 $t = 1$，则 $-10^9 \leq x_j, y_j \leq 10^9$。 - 如果 $t = 2$，则 $1 \leq m_j \leq 10^9$。 | 子任务编号 | 分值 | $t=$ | $n\le$ | $q\le$ | $a_i,b_i,c_i,d_i,x_i,y_i$ | | :--------: | :--: | :--: | :----: | :-------: | :----------------------------------------------------------: | | $0$ | $0$ | $/$ | $/$ | $/$ | $/$ | | $1$ | $5$ | $1$ | $100$ | $200,000$ | $-400\le a_i,b_i,c_i,d_i,x_i,y_i\le400$ | | $2$ | $17$ | $1$ | $100$ | $200,000$ | $a_i\equiv c_i \equiv 0,b_i\equiv d_i \equiv -1 \pmod{10^7}$ | | $3$ | $8$ | $1$ | $100$ | $200,000$ | $/$ | | $4$ | $8$ | $2$ | $100$ | $400$ | $-400\le a_i,b_i,c_i,d_i,x_i,y_i\le400$ | | $5$ | $21$ | $2$ | $100$ | $400$ | $a_i\equiv c_i \equiv 0,b_i\equiv d_i \equiv -1 \pmod{10^7}$ | | $6$ | $10$ | $2$ | $100$ | $400$ | $/$ | | $7$ | $13$ | $2$ | $100$ | $400$ | $/$ | | $8$ | $14$ | $2$ | $100$ | $200,000$ | $/$ | | $9$ | $4$ | $2$ | $400$ | $200,000$ | $/$ |