{"problem":{"name":"A. New Building for SIS","description":{"content":"You are looking at the floor plan of the Summer Informatics School's new building. You were tasked with SIS logistics, so you really care about travel time between different locations: it is important","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1020A"},"statements":[{"statement_type":"Markdown","content":"You are looking at the floor plan of the Summer Informatics School's new building. You were tasked with SIS logistics, so you really care about travel time between different locations: it is important to know how long it would take to get from the lecture room to the canteen, or from the gym to the server room.\n\nThe building consists of _n_ towers, _h_ floors each, where the towers are labeled from 1 to _n_, the floors are labeled from 1 to _h_. There is a passage between any two adjacent towers (two towers _i_ and _i_ + 1 for all _i_: 1 ≤ _i_ ≤ _n_ - 1) on every floor _x_, where _a_ ≤ _x_ ≤ _b_. It takes exactly one minute to walk between any two adjacent floors of a tower, as well as between any two adjacent towers, provided that there is a passage on that floor. It is not permitted to leave the building.\n\n<center>![image](https://espresso.codeforces.com/71bee3824e804a2c4c354c10dc0bf8fe060716dc.png)The picture illustrates the first example.\n\n</center>You have given _k_ pairs of locations (_t__a_, _f__a_), (_t__b_, _f__b_): floor _f__a_ of tower _t__a_ and floor _f__b_ of tower _t__b_. For each pair you need to determine the minimum walking time between these locations.\n\n## Input\n\nThe first line of the input contains following integers:\n\n*   _n_: the number of towers in the building (1 ≤ _n_ ≤ 108),\n*   _h_: the number of floors in each tower (1 ≤ _h_ ≤ 108),\n*   _a_ and _b_: the lowest and highest floor where it's possible to move between adjacent towers (1 ≤ _a_ ≤ _b_ ≤ _h_),\n*   _k_: total number of queries (1 ≤ _k_ ≤ 104).\n\nNext _k_ lines contain description of the queries. Each description consists of four integers _t__a_, _f__a_, _t__b_, _f__b_ (1 ≤ _t__a_, _t__b_ ≤ _n_, 1 ≤ _f__a_, _f__b_ ≤ _h_). This corresponds to a query to find the minimum travel time between _f__a_\\-th floor of the _t__a_\\-th tower and _f__b_\\-th floor of the _t__b_\\-th tower.\n\n## Output\n\nFor each query print a single integer: the minimum walking time between the locations in minutes.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你正在查看夏季信息学学校新大楼的平面图。你负责 SIS 的后勤工作，因此非常关心不同地点之间的通行时间：知道从教室到食堂，或从体育馆到服务器机房需要多长时间非常重要。\n\n该大楼由 #cf_span[n] 座塔楼组成，每座塔楼有 #cf_span[h] 层，塔楼编号从 #cf_span[1] 到 #cf_span[n]，楼层编号从 #cf_span[1] 到 #cf_span[h]。在每一层 #cf_span[x]（其中 #cf_span[a ≤ x ≤ b]）上，任意两座相邻塔楼（即对所有 #cf_span[i]：#cf_span[1 ≤ i ≤ n - 1]，塔楼 #cf_span[i] 和 #cf_span[i + 1]）之间都有通道。在一座塔楼内上下相邻楼层，或在有通道的楼层上在相邻塔楼间移动，均恰好需要一分钟。不允许离开大楼。\n\n#cf_span(class=[tex-font-size-small], body=[该图说明了第一个示例。])\n\n你获得了 #cf_span[k] 对位置 #cf_span[(ta, fa)] 和 #cf_span[(tb, fb)]：塔楼 #cf_span[ta] 的第 #cf_span[fa] 层和塔楼 #cf_span[tb] 的第 #cf_span[fb] 层。对于每一对位置，你需要确定这两点之间的最短步行时间。\n\n输入的第一行包含以下整数：\n\n接下来的 #cf_span[k] 行包含每个查询的描述。每个描述由四个整数 #cf_span[ta], #cf_span[fa], #cf_span[tb], #cf_span[fb] 组成（#cf_span[1 ≤ ta, tb ≤ n], #cf_span[1 ≤ fa, fb ≤ h]），表示查询从塔楼 #cf_span[ta] 的第 #cf_span[fa] 层到塔楼 #cf_span[tb] 的第 #cf_span[fb] 层的最短通行时间。\n\n对于每个查询，输出一个整数：两点之间的最短步行时间（单位：分钟）。\n\n## Input\n\n输入的第一行包含以下整数：#cf_span[n]（大楼中的塔楼数量，#cf_span[1 ≤ n ≤ 10^8]）、#cf_span[h]（每座塔楼的楼层数，#cf_span[1 ≤ h ≤ 10^8]）、#cf_span[a] 和 #cf_span[b]（允许在相邻塔楼间通行的最低和最高楼层，#cf_span[1 ≤ a ≤ b ≤ h]）、#cf_span[k]（查询总数，#cf_span[1 ≤ k ≤ 10^4]）。接下来的 #cf_span[k] 行包含每个查询的描述。每个描述由四个整数 #cf_span[ta], #cf_span[fa], #cf_span[tb], #cf_span[fb]（#cf_span[1 ≤ ta, tb ≤ n], #cf_span[1 ≤ fa, fb ≤ h]）组成，表示查询从塔楼 #cf_span[ta] 的第 #cf_span[fa] 层到塔楼 #cf_span[tb] 的第 #cf_span[fb] 层的最短通行时间。\n\n## Output\n\n对于每个查询，输出一个整数：两点之间的最短步行时间（单位：分钟）。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, h, a, b, k \\in \\mathbb{Z}^+ $ be given constants:  \n- $ n $: number of towers, labeled $ 1 $ to $ n $.  \n- $ h $: number of floors per tower, labeled $ 1 $ to $ h $.  \n- $ [a, b] \\subseteq [1, h] $: the range of floors on which horizontal passages between adjacent towers exist.  \n\nLet $ Q = \\{(t_a, f_a, t_b, f_b)_i \\mid i \\in \\{1, \\dots, k\\}\\} $ be the set of $ k $ queries, where each query specifies:  \n- Start: floor $ f_a $ of tower $ t_a $,  \n- End: floor $ f_b $ of tower $ t_b $.  \n\n**Constraints**  \n1. $ 1 \\leq t_a, t_b \\leq n $  \n2. $ 1 \\leq f_a, f_b \\leq h $  \n3. $ 1 \\leq a \\leq b \\leq h $  \n4. Movement is allowed:  \n   - Vertically within a tower: 1 minute per floor change.  \n   - Horizontally between adjacent towers $ i $ and $ i+1 $: 1 minute, **only if** the current floor $ x \\in [a, b] $.  \n   - No movement outside the building.  \n\n**Objective**  \nFor each query $ (t_a, f_a, t_b, f_b) \\in Q $, compute the minimum travel time $ T $ in minutes from $ (t_a, f_a) $ to $ (t_b, f_b) $, where:  \n$$\nT = \\min_{\\substack{x \\in [a,b] \\cup \\{f_a, f_b\\} \\\\ \\text{if } t_a \\ne t_b}} \\left( |f_a - x| + |t_a - t_b| + |x - f_b| \\right)\n$$\nif $ t_a \\ne t_b $, and  \n$$\nT = |f_a - f_b|\n$$\nif $ t_a = t_b $.  \n\nEquivalently, the solution is:  \n$$\nT = |f_a - f_b| + |t_a - t_b| \\quad \\text{if } \\min(f_a, f_b) \\geq a \\text{ and } \\max(f_a, f_b) \\leq b\n$$\notherwise,  \n$$\nT = |f_a - f_b| + |t_a - t_b| + 2 \\cdot \\min\\left( \\max(a - \\min(f_a, f_b), 0), \\max(\\max(f_a, f_b) - b, 0) \\right)\n$$  \nBut more cleanly:  \nLet $ \\Delta_t = |t_a - t_b| $, $ \\Delta_f = |f_a - f_b| $.  \nThen:  \n$$\nT = \\Delta_f + \\Delta_t + 2 \\cdot \\max\\left(0, a - \\min(f_a, f_b), \\max(f_a, f_b) - b \\right)\n$$  \n**Wait — correction:** The correct minimal path is:  \n\nIf $ t_a = t_b $:  \n$$\nT = |f_a - f_b|\n$$\n\nIf $ t_a \\ne t_b $:  \n$$\nT = \\min_{x \\in \\{a, b, f_a, f_b\\} \\cap [a,b]} \\left( |f_a - x| + |t_a - t_b| + |x - f_b| \\right)\n$$  \nBut since $ |f_a - x| + |x - f_b| \\geq |f_a - f_b| $, and equality holds when $ x \\in [\\min(f_a,f_b), \\max(f_a,f_b)] $, we can write:  \n\nDefine $ L = \\min(f_a, f_b) $, $ R = \\max(f_a, f_b) $.  \nThen:  \n- If $ [L, R] \\cap [a, b] \\ne \\emptyset $, then $ T = |f_a - f_b| + |t_a - t_b| $  \n- Else, let $ d = \\min(|L - b|, |R - a|) $, then $ T = |f_a - f_b| + |t_a - t_b| + 2d $\n\nThus, formally:  \n\nLet $ \\Delta_t = |t_a - t_b| $, $ \\Delta_f = |f_a - f_b| $,  \n$ L = \\min(f_a, f_b) $, $ R = \\max(f_a, f_b) $.  \n\nThen:  \n$$\nT = \n\\begin{cases}\n\\Delta_f & \\text{if } t_a = t_b \\\\\n\\Delta_f + \\Delta_t & \\text{if } [L, R] \\cap [a, b] \\ne \\emptyset \\\\\n\\Delta_f + \\Delta_t + 2 \\cdot \\min(b - L, R - a) & \\text{otherwise}\n\\end{cases}\n$$\n\nBut note: if $ R < a $, then $ \\min(b - L, R - a) = R - a $ is negative — so we must take **positive** detour:  \n\nActually, the detour cost is:  \n- If $ R < a $: must go up to $ a $, so detour = $ (a - L) + (a - R) = 2a - L - R $  \n- If $ L > b $: must go down to $ b $, so detour = $ (L - b) + (R - b) = L + R - 2b $  \n\nSo:  \n$$\n\\text{detour} = \n\\begin{cases}\n2(a - R) & \\text{if } R < a \\\\\n2(L - b) & \\text{if } L > b \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$\n\nThus:  \n\n$$\nT = |f_a - f_b| + |t_a - t_b| + \n\\begin{cases}\n2(a - \\max(f_a, f_b)) & \\text{if } \\max(f_a, f_b) < a \\\\\n2(\\min(f_a, f_b) - b) & \\text{if } \\min(f_a, f_b) > b \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$\n\n**Final Formal Objective**  \nFor each query $ (t_a, f_a, t_b, f_b) $:  \nLet $ \\Delta_t = |t_a - t_b| $, $ \\Delta_f = |f_a - f_b| $,  \n$ L = \\min(f_a, f_b) $, $ R = \\max(f_a, f_b) $.  \n\nThen:  \n$$\nT = \\Delta_f + \\Delta_t + \n\\begin{cases}\n2(a - R) & \\text{if } R < a \\\\\n2(L - b) & \\text{if } L > b \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1020A","tags":["math"],"sample_group":[["3 6 2 3 3\n1 2 1 3\n1 4 3 4\n1 2 2 3","1\n4\n2"]],"created_at":"2026-03-03 11:00:39"}}