{"problem":{"name":"C. Stairs and Elevators","description":{"content":"In the year of $30XX$ participants of some world programming championship live in a single large hotel. The hotel has $n$ floors. Each floor has $m$ sections with a single corridor connecting all of t","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF967C"},"statements":[{"statement_type":"Markdown","content":"In the year of $30XX$ participants of some world programming championship live in a single large hotel. The hotel has $n$ floors. Each floor has $m$ sections with a single corridor connecting all of them. The sections are enumerated from $1$ to $m$ along the corridor, and all sections with equal numbers on different floors are located exactly one above the other. Thus, the hotel can be represented as a rectangle of height $n$ and width $m$. We can denote sections with pairs of integers $(i, j)$, where $i$ is the floor, and $j$ is the section number on the floor.\n\nThe guests can walk along the corridor on each floor, use stairs and elevators. Each stairs or elevator occupies all sections $(1, x)$, $(2, x)$, $\\ldots$, $(n, x)$ for some $x$ between $1$ and $m$. All sections not occupied with stairs or elevators contain guest rooms. It takes one time unit to move between neighboring sections on the same floor or to move one floor up or down using stairs. It takes one time unit to move up to $v$ floors in any direction using an elevator. You can assume you don't have to wait for an elevator, and the time needed to enter or exit an elevator is negligible.\n\nYou are to process $q$ queries. Each query is a question \"what is the minimum time needed to go from a room in section $(x_1, y_1)$ to a room in section $(x_2, y_2)$?\"\n\n## Input\n\nThe first line contains five integers $n, m, c_l, c_e, v$ ($2 \\leq n, m \\leq 10^8$, $0 \\leq c_l, c_e \\leq 10^5$, $1 \\leq c_l + c_e \\leq m - 1$, $1 \\leq v \\leq n - 1$) — the number of floors and section on each floor, the number of stairs, the number of elevators and the maximum speed of an elevator, respectively.\n\nThe second line contains $c_l$ integers $l_1, \\ldots, l_{c_l}$ in increasing order ($1 \\leq l_i \\leq m$), denoting the positions of the stairs. If $c_l = 0$, the second line is empty.\n\nThe third line contains $c_e$ integers $e_1, \\ldots, e_{c_e}$ in increasing order, denoting the elevators positions in the same format. It is guaranteed that all integers $l_i$ and $e_i$ are distinct.\n\nThe fourth line contains a single integer $q$ ($1 \\leq q \\leq 10^5$) — the number of queries.\n\nThe next $q$ lines describe queries. Each of these lines contains four integers $x_1, y_1, x_2, y_2$ ($1 \\leq x_1, x_2 \\leq n$, $1 \\leq y_1, y_2 \\leq m$) — the coordinates of starting and finishing sections for the query. It is guaranteed that the starting and finishing sections are distinct. It is also guaranteed that these sections contain guest rooms, i. e. $y_1$ and $y_2$ are not among $l_i$ and $e_i$.\n\n## Output\n\nPrint $q$ integers, one per line — the answers for the queries.\n\n[samples]\n\n## Note\n\nIn the first query the optimal way is to go to the elevator in the 5-th section in four time units, use it to go to the fifth floor in two time units and go to the destination in one more time unit.\n\nIn the second query it is still optimal to use the elevator, but in the third query it is better to use the stairs in the section 2.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"在公元 $30 X X$ 年，某世界编程竞赛的参赛者们居住在一个大型酒店中。该酒店有 $n$ 层，每层有 $m$ 个区域，由一条走廊连接所有区域。区域沿走廊从 $1$ 到 $m$ 编号，不同楼层上编号相同的区域恰好上下对齐。因此，酒店可以表示为一个高度为 $n$、宽度为 $m$ 的矩形。我们可以用整数对 $(i, j)$ 表示区域，其中 $i$ 是楼层，$j$ 是该楼层的区域编号。\n\n客人可以在每层的走廊上行走，使用楼梯或电梯。每个楼梯或电梯占据所有区域 $(1, x)$, $(2, x)$, $dots.h$, $(n, x)$，其中 $x$ 在 $1$ 到 $m$ 之间。未被楼梯或电梯占据的区域均为客房。在同层相邻区域间移动或使用楼梯上下一层需要消耗一个时间单位。使用电梯可以在一个时间单位内上下最多 $v$ 层。你可以假设无需等待电梯，且进出电梯的时间可忽略不计。\n\n你需要处理 $q$ 个查询。每个查询问题是：“从区域 $(x_1, y_1)$ 的房间到区域 $(x_2, y_2)$ 的房间所需的最短时间是多少？”\n\n第一行包含五个整数 $n, m, c_l, c_e, v$（$2 lt.eq n, m lt.eq 10^8$，$0 lt.eq c_l, c_e lt.eq 10^5$，$1 lt.eq c_l + c_e lt.eq m -1$，$1 lt.eq v lt.eq n -1$）——分别表示楼层数、每层区域数、楼梯数量、电梯数量和电梯的最大速度。\n\n第二行包含 $c_l$ 个按递增顺序排列的整数 $l_1, dots.h, l_(c_l)$（$1 lt.eq l_i lt.eq m$），表示楼梯的位置。如果 $c_l = 0$，则第二行为空。\n\n第三行包含 $c_e$ 个按递增顺序排列的整数 $e_1, dots.h, e_(c_e)$，表示电梯的位置，格式相同。保证所有 $l_i$ 和 $e_i$ 互不相同。\n\n第四行包含一个整数 $q$（$1 lt.eq q lt.eq 10^5$）——查询数量。\n\n接下来的 $q$ 行描述查询。每行包含四个整数 $x_1, y_1, x_2, y_2$（$1 lt.eq x_1, x_2 lt.eq n$，$1 lt.eq y_1, y_2 lt.eq m$）——表示查询的起点和终点区域坐标。保证起点和终点区域不同，且均为客房，即 $y_1$ 和 $y_2$ 不在 $l_i$ 和 $e_i$ 中。\n\n请输出 $q$ 个整数，每行一个——对应每个查询的答案。\n\n在第一个查询中，最优方案是用四个时间单位走到第 5 个区域的电梯，用两个时间单位乘电梯到达第五层，再用一个时间单位走到目的地。\n\n在第二个查询中，仍最优使用电梯；但在第三个查询中，使用第 2 个区域的楼梯更优。\n\n## Input\n\n第一行包含五个整数 $n, m, c_l, c_e, v$（$2 lt.eq n, m lt.eq 10^8$，$0 lt.eq c_l, c_e lt.eq 10^5$，$1 lt.eq c_l + c_e lt.eq m -1$，$1 lt.eq v lt.eq n -1$）——分别表示楼层数、每层区域数、楼梯数量、电梯数量和电梯的最大速度。第二行包含 $c_l$ 个按递增顺序排列的整数 $l_1, dots.h, l_(c_l)$（$1 lt.eq l_i lt.eq m$），表示楼梯的位置。如果 $c_l = 0$，则第二行为空。第三行包含 $c_e$ 个按递增顺序排列的整数 $e_1, dots.h, e_(c_e)$，表示电梯的位置，格式相同。保证所有 $l_i$ 和 $e_i$ 互不相同。第四行包含一个整数 $q$（$1 lt.eq q lt.eq 10^5$）——查询数量。接下来的 $q$ 行描述查询。每行包含四个整数 $x_1, y_1, x_2, y_2$（$1 lt.eq x_1, x_2 lt.eq n$，$1 lt.eq y_1, y_2 lt.eq m$）——表示查询的起点和终点区域坐标。保证起点和终点区域不同，且均为客房，即 $y_1$ 和 $y_2$ 不在 $l_i$ 和 $e_i$ 中。\n\n## Output\n\n请输出 $q$ 个整数，每行一个——对应每个查询的答案。\n\n[samples]\n\n## Note\n\n在第一个查询中，最优方案是用四个时间单位走到第 5 个区域的电梯，用两个时间单位乘电梯到达第五层，再用一个时间单位走到目的地。在第二个查询中，仍最优使用电梯；但在第三个查询中，使用第 2 个区域的楼梯更优。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ be the number of floors and sections per floor, respectively.  \nLet $ c_l, c_e \\in \\mathbb{Z}_{\\geq 0} $ be the number of stairs and elevators, respectively.  \nLet $ v \\in \\mathbb{Z}^+ $ be the elevator speed (maximum floors traversed per time unit).  \n\nLet $ L = \\{l_1, l_2, \\dots, l_{c_l}\\} \\subseteq \\{1, \\dots, m\\} $ be the set of stair positions, sorted increasingly.  \nLet $ E = \\{e_1, e_2, \\dots, e_{c_e}\\} \\subseteq \\{1, \\dots, m\\} $ be the set of elevator positions, sorted increasingly, with $ L \\cap E = \\emptyset $.  \n\nFor a query, let $ (x_1, y_1), (x_2, y_2) \\in \\{1, \\dots, n\\} \\times \\{1, \\dots, m\\} $ be the start and end room coordinates, with $ y_1, y_2 \\notin L \\cup E $.  \n\n**Constraints**  \n1. $ 2 \\leq n, m \\leq 10^8 $  \n2. $ 0 \\leq c_l, c_e \\leq 10^5 $, $ c_l + c_e \\leq m - 1 $  \n3. $ 1 \\leq v \\leq n - 1 $  \n4. $ 1 \\leq q \\leq 10^5 $  \n5. All $ l_i, e_i $ are distinct and lie in $ [1, m] $.  \n6. For each query: $ (x_1, y_1) \\neq (x_2, y_2) $, and $ y_1, y_2 \\notin L \\cup E $.  \n\n**Objective**  \nFor each query, compute the minimum time to travel from $ (x_1, y_1) $ to $ (x_2, y_2) $, where movement is allowed as follows:  \n- Horizontal movement on the same floor: 1 time unit per section.  \n- Vertical movement via stairs: 1 time unit per floor.  \n- Vertical movement via elevators: $ \\left\\lceil \\frac{|x_2 - x_1|}{v} \\right\\rceil $ time units for vertical displacement of $ |x_2 - x_1| $ floors.  \n\nThe path may use at most one vertical transport (stair or elevator), accessed at some column $ z \\in L \\cup E $, with total time:  \n$$\n|y_1 - z| + \\text{vertical\\_time}(x_1, x_2, z) + |z - y_2|\n$$  \nwhere  \n$$\n\\text{vertical\\_time}(x_1, x_2, z) = \n\\begin{cases} \n|x_2 - x_1| & \\text{if } z \\in L \\\\\n\\left\\lceil \\frac{|x_2 - x_1|}{v} \\right\\rceil & \\text{if } z \\in E \n\\end{cases}\n$$  \n\nThe minimum time is:  \n$$\n\\min_{z \\in L \\cup E} \\left( |y_1 - z| + |z - y_2| + \\text{vertical\\_time}(x_1, x_2, z) \\right)\n$$  \nAdditionally, the direct horizontal path (without vertical transport) is allowed if $ x_1 = x_2 $:  \n$$\n|x_1 - x_2| + |y_1 - y_2| \\quad \\text{(which reduces to } |y_1 - y_2| \\text{ if } x_1 = x_2\\text{)}\n$$  \nThus, the final answer for each query is:  \n$$\n\\min\\left( |y_1 - y_2| + |x_1 - x_2|, \\quad \\min_{z \\in L \\cup E} \\left( |y_1 - z| + |z - y_2| + \\text{vertical\\_time}(x_1, x_2, z) \\right) \\right)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF967C","tags":["binary search"],"sample_group":[["5 6 1 1 3\n2\n5\n3\n1 1 5 6\n1 3 5 4\n3 3 5 3","7\n5\n4"]],"created_at":"2026-03-03 11:00:39"}}