Takahashi on Grid

题目描述

平面上有无限多个格子。 对于每一对整数 $(x,y)$，都有对应的格子，我们称之为格子 $(x,y)$。 每个格子要么是空格子，要么是墙格子。
给出两个长度为 $N$ 的正整数序列：$L=(L _ 1,L _ 2,\dotsc,L _ N)$ 和 $U=(U _ 1,U _ 2,\dotsc,U _ N)$。 其中，$L _ i$ 和 $U _ i$ 满足 $1\leq L _ i\leq U _ i\leq10 ^ 9$ 对于 $i=1,2,\ldots,N$.
所有格子 $(x,y)\ (1\leq x\leq N,L _ x\leq y\leq U _ x)$ 都是空格子，其他格子都是墙格子。 当 Takahashi 位于空格子 $(x,y)$ 时，他可以执行下列操作之一。

如果格子 $(x+1,y)$ 是空格子，则移动到格子 $(x+1,y)$。 如果格子 $(x-1,y)$ 是空格子，则移动到格子 $(x-1,y)$。 如果格子 $(x,y+1)$ 是空格子，则移动到格子 $(x,y+1)$。 如果格子 $(x,y-1)$ 是空格子，则移动到格子 $(x,y-1)$。

保证通过重复这些操作他可以在任意两个空格子之间移动。 回答 $Q$ 个如下格式的查询。 对于第 $i$ 个查询 $(1\leq i\leq Q)$，给定四元组整数 $(s _ {x,i},s _ {y,i},t _ {x,i},t _ {y,i})$。求 Takahashi 从格子 $(s _ {x,i},s _ {y,i})$ 移动到格子 $(t _ {x,i},t _ {y,i})$ 所需的最少操作次数。 对于每个查询，保证给定的两格都是空格子。

输入格式

输入按标准输入给出，格式如下： $N$ $L _ 1$ $U _ 1$ $L _ 2$ $U _ 2$ $\vdots$ $L _ N$ $U _ N$ $Q$ $s _ {x,1}$ $s _ {y,1}$ $t _ {x,1}$ $t _ {y,1}$ $s _ {x,2}$ $s _ {y,2}$ $t _ {x,2}$ $t _ {y,2}$ $\vdots$ $s _ {x,Q}$ $s _ {y,Q}$ $t _ {x,Q}$ $t _ {y,Q}$

输出格式

输出 $Q$ 行。 第 $i$ 行 $(1\leq i\leq Q)$ 应包含第 $i$ 个查询的答案。

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

10
3
14

12
1 1000000000
1000000000 1000000000
1 1000000000
1 1
1 1000000000
1000000000 1000000000
1 1000000000
1 1
1 1000000000
1000000000 1000000000
1 1000000000
1 1
1
1 1 12 1

6000000005

10
1694 7483
3396 5566
2567 6970
1255 3799
2657 3195
3158 8007
3368 8266
1447 6359
5365 8614
3141 7245
15
3 3911 6 4694
7 5850 10 4641
1 5586 6 4808
2 3401 8 2676
3 3023 6 6923
8 4082 3 6531
6 3216 7 6282
8 5121 8 3459
8 4388 1 6339
6 6001 3 6771
10 5873 8 5780
1 6512 6 6832
8 5345 7 4975
10 4010 8 2355
7 5837 9 6279

2218
1212
4009
1077
3903
4228
3067
1662
4344
6385
95
6959
371
4367
444

提示

$1\leq N\leq2\times10 ^ 5$ $1\leq L _ i\leq U _ i\leq10 ^ 9\ (1\leq i\leq N)$ $\lbrack L _ i,U _ i\rbrack\cap\lbrack L _ {i+1},U _ {i+1}\rbrack\neq\emptyset\ (1\leq i\lt N)$ $1\leq Q\leq2\times10 ^ 5$ $1\leq s _ {x,i}\leq N$ 且 $L _ {s _ {x,i}}\leq s _ {y,i}\leq U _ {s _ {x,i}}\ (1\leq i\leq Q)$ $1\leq t _ {x,i}\leq N$ 且 $L _ {t _ {x,i}}\leq t _ {y,i}\leq U _ {t _ {x,i}}\ (1\leq i\leq Q)$ 所有输入值都是整数。给定的格子如下所示。 例如对于第一个查询，Takahashi 可以按如下方式从格子 $(1,4)$ 移动到格子 $(6,3)$，共十步，如下图所示。 不可能在九步或更少步数内从格子 $(1,4)$ 移动到格子 $(6,3)$，因此输出 $10$.
注意输出值可能不适合 32 位整数。

标签: AtCoder|abc365F

来源

AtCoder|abc365F