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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
첫줄 = 控制台.读数字();n = 첫줄[0];q = 첫줄[1];xs = [];hs = [];循环 (i = 0; i < n; i++){ 줄 = 控制台.读数字(); xs.添加(줄[0]); hs.添加(줄[1]);}// d 이하인 마지막 표지의 번호 (없으면 -1)마지막표지(d){ lo = 0; hi = n; // xs[lo..hi) 가운데 d보다 큰 첫 칸을 찾는다 当 (lo < hi) { mid = 数学.商(lo + hi, 2); 如果 (xs[mid] <= d) { lo = mid + 1; } 否则 { hi = mid; } } 返回 lo - 1;}질문 = 控制台.读数字();遍历 (d 在 질문){ i = 마지막표지(d); 如果 (i < 0) { 控制台.输出(hs[0]); } 否则 如果 (i == n - 1) { 控制台.输出(hs[n - 1]); } 否则 { // 수학.몫은 0 쪽으로 버리므로, 실수로 나눈 뒤 수학.내림으로 내린다 控制台.输出(hs[i] + 数学.向下取整((d - xs[i]) * (hs[i + 1] - hs[i]) / (xs[i + 1] - xs[i]))); }}