Along a seaside trail there are n height markers.
The i-th marker stands at distance x_i from the start of the trail, and the height there is h_i.
Heights are measured with sea level as 0, so they can be negative.
The markers are given from the one nearest the start, and no two markers stand at the same place.
Between two neighbouring markers the trail is taken to run straight.
That is, at distance d between a marker (x0, h0) and the next marker (x1, h1), the height is h0 + (d - x0) × (h1 - h0) ÷ (x1 - x0).
Before the first marker the height is taken to be the first marker's height, and after the last marker the last marker's height.
Given q distances d, find for each the largest integer that does not exceed the height at that distance.
If the height is 68.5 the answer is 68, and if it is -0.25 the answer is -1, not 0.
In the example, distance 17 lies between (10, 100) and (20, 55), so the height is 100 + 7 × (-45) ÷ 10 = 68.5 and the answer is 68.
Distance 33 lies between (20, 55) and (40, -30), so the height is 55 + 13 × (-85) ÷ 20 = -0.25 and the answer is -1.
Input
The first line has n and q separated by a space. Each of the next n lines has one marker in the form "x h". The last line has the q distances d separated by single spaces. All numbers are integers. 1 ≤ n ≤ 10,000, 1 ≤ q ≤ 10,000, 0 ≤ x_1 < x_2 < … < x_n ≤ 1,000,000,000, -1,000,000 ≤ h_i ≤ 1,000,000, 0 ≤ d ≤ 1,000,000,000
Output
For each distance d, in the order given, print the answer on its own line. Write numbers as plain digits without commas
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
First find, by binary search, which two markers d lies between: the index of 'the last marker whose x is at most d'. In Python that is bisect_right(xs, d) - 1, and in C++ one step before std::upper_bound. Java's Arrays.binarySearch returns -(insertion point) - 1 when the value is not found, so turn it into -p - 2; C#'s Array.BinarySearch returns the bitwise complement of the insertion point, so turn it into ~p - 1. In JS, TS, C and Craykon write it by hand with lo and hi. Trap one: on a downhill stretch the number being divided is negative. Integer / in C, C++, Java and C# does not round down but cuts toward zero, so -315 / 10 is -31 (the answer needs -32). The example's distance 17 comes out as 69 and distance 33 as 0. Python's // rounds down, so it is right as written; Java has Math.floorDiv, JS and TS use Math.floor(a / b), and in C, C++ and C# subtract 1 from the quotient when the remainder is negative. Craykon's Mathf.Quot also cuts toward zero, so use Mathf.Floor(a / b). Rewriting the height as the weighted average (h0 × (x1 - d) + h1 × (d - x0)) ÷ (x1 - x0) does not help when heights are negative (distance 46 in the example: -447 ÷ 15 is -29.8, so the answer is -30, but cutting gives -29). Trap two: the product of a distance difference and a height difference grows to 2 quadrillion. Java and C# int silently give a wrong number, and in C and C++ it is undefined behaviour, so multiply as long / long long. JS, TS and Craykon numbers are exact up to 2^53 (about 9 quadrillion), so they just work. Trap three: dividing first and multiplying afterwards, for fear of overflow, throws away the fractional part of the slope. Multiply, then divide. Trap four: before the first marker the index is -1. In Python xs[-1] gives the last marker with no error, so that case must be handled separately. Trap five: if the binary search range leaves out the last marker, then even beyond the last marker the height keeps climbing or falling along the previous stretch's slope.
Pythonmain.py · 22 lines
import sysfrom bisect import bisect_rightdef main(): data = sys.stdin.read().split() n, q = int(data[0]), int(data[1]) xs = [int(v) for v in data[2:2 + 2 * n:2]] hs = [int(v) for v in data[3:3 + 2 * n:2]] out = [] for v in data[2 + 2 * n:2 + 2 * n + q]: d = int(v) i = bisect_right(xs, d) - 1 # d 이하인 마지막 표지 (없으면 -1) if i < 0: out.append(hs[0]) # 첫 표지보다 앞 elif i == n - 1: out.append(hs[n - 1]) # 마지막 표지이거나 그 뒤 else: # //는 음수에서도 내림이다: -85 // 10 == -9 out.append(hs[i] + (d - xs[i]) * (hs[i + 1] - hs[i]) // (xs[i + 1] - xs[i])) print("\n".join(map(str, out)))main()
JavaScriptmain.js · 34 lines
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const n = data[0];const q = data[1];const xs = [];const hs = [];for (let i = 0; i < n; i++) { xs.push(data[2 + 2 * i]); hs.push(data[3 + 2 * i]);}// d 이하인 마지막 표지의 번호 (없으면 -1)function lastAtOrBefore(d) { let lo = 0; let hi = n; // xs[lo..hi) 가운데 d보다 큰 첫 칸을 찾는다 while (lo < hi) { const mid = (lo + hi) >> 1; if (xs[mid] <= d) lo = mid + 1; else hi = mid; } return lo - 1;}const out = [];for (let k = 0; k < q; k++) { const d = data[2 + 2 * n + k]; const i = lastAtOrBefore(d); if (i < 0) out.push(hs[0]); else if (i === n - 1) out.push(hs[n - 1]); else { // 곱이 2^53보다 작아 정확하고, Math.floor는 음수에서도 내림이다 out.push(hs[i] + Math.floor(((d - xs[i]) * (hs[i + 1] - hs[i])) / (xs[i + 1] - xs[i]))); }}console.log(out.join("\n"));
TypeScriptmain.ts · 35 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const n: number = data[0];const q: number = data[1];const xs: number[] = [];const hs: number[] = [];for (let i = 0; i < n; i++) { xs.push(data[2 + 2 * i]); hs.push(data[3 + 2 * i]);}// d 이하인 마지막 표지의 번호 (없으면 -1)function lastAtOrBefore(d: number): number { let lo = 0; let hi = n; // xs[lo..hi) 가운데 d보다 큰 첫 칸을 찾는다 while (lo < hi) { const mid = (lo + hi) >> 1; if (xs[mid] <= d) lo = mid + 1; else hi = mid; } return lo - 1;}const out: number[] = [];for (let k = 0; k < q; k++) { const d = data[2 + 2 * n + k]; const i = lastAtOrBefore(d); if (i < 0) out.push(hs[0]); else if (i === n - 1) out.push(hs[n - 1]); else { // 곱이 2^53보다 작아 정확하고, Math.floor는 음수에서도 내림이다 out.push(hs[i] + Math.floor(((d - xs[i]) * (hs[i + 1] - hs[i])) / (xs[i + 1] - xs[i]))); }}console.log(out.join("\n"));
JavaMain.java · 40 lines
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.StreamTokenizer;import java.util.Arrays;public class Main { public static void main(String[] args) throws Exception { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; in.nextToken(); int q = (int) in.nval; int[] xs = new int[n]; long[] hs = new long[n]; for (int i = 0; i < n; i++) { in.nextToken(); xs[i] = (int) in.nval; in.nextToken(); hs[i] = (long) in.nval; } StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) { in.nextToken(); int d = (int) in.nval; // 찾으면 그 번호, 못 찾으면 -(끼울 자리) - 1 을 돌려준다 int p = Arrays.binarySearch(xs, d); int i = p >= 0 ? p : -p - 2; // d 이하인 마지막 표지 (없으면 -1) long ans; if (i < 0) ans = hs[0]; else if (i == n - 1) ans = hs[n - 1]; else { // long으로 곱하고, 음수에서도 내림인 floorDiv를 쓴다 (/ 는 0 쪽으로 버린다) long num = (long) (d - xs[i]) * (hs[i + 1] - hs[i]); ans = hs[i] + Math.floorDiv(num, (long) (xs[i + 1] - xs[i])); } out.append(ans).append('\n'); } System.out.print(out); }}
C#Main.cs · 40 lines
using System;using System.Text;class Program{ // C#의 / 는 0 쪽으로 버리므로 내림 나눗셈을 직접 만든다 (b > 0) static long FloorDiv(long a, long b) { long quot = a / b; if (a % b < 0) quot--; return quot; } static void Main() { string[] data = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), q = int.Parse(data[1]); int[] xs = new int[n]; long[] hs = new long[n]; for (int i = 0; i < n; i++) { xs[i] = int.Parse(data[2 + 2 * i]); hs[i] = long.Parse(data[3 + 2 * i]); } var sb = new StringBuilder(); for (int k = 0; k < q; k++) { int d = int.Parse(data[2 + 2 * n + k]); // 찾으면 그 번호, 못 찾으면 끼울 자리의 비트를 뒤집은 수(~자리)를 돌려준다 int p = Array.BinarySearch(xs, d); int i = p >= 0 ? p : ~p - 1; // d 이하인 마지막 표지 (없으면 -1) long ans; if (i < 0) ans = hs[0]; else if (i == n - 1) ans = hs[n - 1]; else ans = hs[i] + FloorDiv((long)(d - xs[i]) * (hs[i + 1] - hs[i]), xs[i + 1] - xs[i]); sb.Append(ans).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 31 lines
#include <algorithm>#include <iostream>#include <vector>// C++의 / 는 0 쪽으로 버리므로 내림 나눗셈을 직접 만든다 (b > 0)long long floorDiv(long long a, long long b) { long long quot = a / b; if (a % b < 0) quot--; return quot;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<int> xs(n); std::vector<long long> hs(n); for (int i = 0; i < n; i++) std::cin >> xs[i] >> hs[i]; for (int k = 0; k < q; k++) { int d; std::cin >> d; // upper_bound: d보다 큰 첫 칸 → 그 앞 칸이 d 이하인 마지막 표지 (없으면 -1) int i = static_cast<int>(std::upper_bound(xs.begin(), xs.end(), d) - xs.begin()) - 1; long long ans; if (i < 0) ans = hs[0]; else if (i == n - 1) ans = hs[n - 1]; else ans = hs[i] + floorDiv(static_cast<long long>(d - xs[i]) * (hs[i + 1] - hs[i]), xs[i + 1] - xs[i]); std::cout << ans << '\n'; }}
Cmain.c · 34 lines
#include <stdio.h>int xs[10000];long long hs[10000];/* C의 / 는 0 쪽으로 버리므로 내림 나눗셈을 직접 만든다 (b > 0) */long long floor_div(long long a, long long b) { long long quot = a / b; if (a % b < 0) quot--; return quot;}int main(void) { int n, q; scanf("%d %d", &n, &q); for (int i = 0; i < n; i++) scanf("%d %lld", &xs[i], &hs[i]); for (int k = 0; k < q; k++) { int d; scanf("%d", &d); int lo = 0, hi = n; /* xs[lo..hi) 가운데 d보다 큰 첫 칸을 찾는다 */ while (lo < hi) { int mid = (lo + hi) / 2; if (xs[mid] <= d) lo = mid + 1; else hi = mid; } int i = lo - 1; /* d 이하인 마지막 표지 (없으면 -1) */ long long ans; if (i < 0) ans = hs[0]; else if (i == n - 1) ans = hs[n - 1]; else ans = hs[i] + floor_div((long long)(d - xs[i]) * (hs[i + 1] - hs[i]), xs[i + 1] - xs[i]); printf("%lld\n", ans); } return 0;}
Craykonmain.cray · 50 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];q = 첫줄[1];xs = [];hs = [];for (i = 0; i < n; i++){ 줄 = Console.ReadNumbers(); xs.Add(줄[0]); hs.Add(줄[1]);}// d 이하인 마지막 표지의 번호 (없으면 -1)마지막표지(d){ lo = 0; hi = n; // xs[lo..hi) 가운데 d보다 큰 첫 칸을 찾는다 while (lo < hi) { mid = Mathf.Quot(lo + hi, 2); if (xs[mid] <= d) { lo = mid + 1; } else { hi = mid; } } return lo - 1;}질문 = Console.ReadNumbers();foreach (d in 질문){ i = 마지막표지(d); if (i < 0) { Console.WriteLine(hs[0]); } else if (i == n - 1) { Console.WriteLine(hs[n - 1]); } else { // 수학.몫은 0 쪽으로 버리므로, 실수로 나눈 뒤 수학.내림으로 내린다 Console.WriteLine(hs[i] + Mathf.Floor((d - xs[i]) * (hs[i + 1] - hs[i]) / (xs[i + 1] - xs[i]))); }}