有 m + 1 个车站排成一列，第 i 段（1 ≤ i ≤ m）的列车只从第 i 个车站开到第 i + 1 个车站。 要到终点站，必须从第 1 段到第 m 段，每一段依次恰好乘坐一趟列车。 每一段都有时刻表，每趟列车用出发时刻和行驶时间表示。 列车在出发时刻加上行驶时间的时刻到达下一站。 同一段内出发时刻各不相同，但有的列车很快，所以后出发的列车可能先到。 如果在时刻 x 位于某个车站，就可以在该站乘坐出发时刻不早于 x 的列车（与到达时刻相同时刻出发的列车也能乘坐）。 回答 q 个问题。 问题 "A t" 问：在时刻 t 位于第一个车站时，最早什么时刻能到终点站。 问题 "B d" 问：要在时刻 d 或之前到达终点站，在第 1 段乘坐的列车的出发时刻最晚可以是多少。 每个问题的答案输出一行。 问题 A 中无法到达终点站，或问题 B 中无法在时刻 d 或之前到达终点站时，输出 -1。
输入
第一行给出用空格隔开的 m 和 q。 接着从第 1 段开始，每段给出三行：列车数 c、c 个出发时刻（从小到大，用一个空格隔开）、c 个行驶时间（与出发时刻顺序相同）。 接下来 q 行每行一个问题 "A t" 或 "B d"。 1 ≤ m ≤ 10，1 ≤ c，所有段的 c 之和 ≤ 10,000，1 ≤ q ≤ 5,000，0 ≤ 出发时刻 ≤ 2,000,000,000，1 ≤ 行驶时间 ≤ 1,000,000,000，0 ≤ t, d ≤ 3,000,000,000
输出
q 行。 问题 A 输出到达终点站的最早时刻，问题 B 输出第 1 段列车的最晚出发时刻，无法到达则输出 -1。 数只写数字，不带逗号
样例 1 · stdin
2 6
3
10 20 30
50 15 20
3
35 50 60
10 20 5
A 5
A 25
A 31
B 45
B 65
B 44
import sysfrom bisect import bisect_left, bisect_rightdef main(): data = sys.stdin.buffer.read().split() m, q = int(data[0]), int(data[1]) pos = 2 deps = [] # deps[i][j]: i번 구간 j번째 열차의 출발 시각(커지는 차례) best = [] # best[i][j]: j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for _ in range(m): c = int(data[pos]) pos += 1 dep = [int(x) for x in data[pos : pos + c]] pos += c arr = [dep[j] + int(data[pos + j]) for j in range(c)] pos += c # 뒤에서부터 최솟값을 누적하면 커지기만 하는 목록이 되어 이분 탐색을 할 수 있다 for j in range(c - 2, -1, -1): if arr[j + 1] < arr[j]: arr[j] = arr[j + 1] deps.append(dep) best.append(arr) out = [] for _ in range(q): kind = data[pos] x = int(data[pos + 1]) pos += 2 if kind == b"A": # 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for i in range(m): j = bisect_left(deps[i], x) if j == len(deps[i]): x = -1 break x = best[i][j] else: # 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for i in range(m - 1, -1, -1): j = bisect_right(best[i], x) - 1 if j < 0: x = -1 break x = deps[i][j] out.append(x) print("\n".join(map(str, out)))main()
JavaScriptmain.js · 70 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [m, q] = lines[0].trim().split(/\s+/).map(Number);const deps = []; // deps[i][j]: i번 구간 j번째 열차의 출발 시각(커지는 차례)const best = []; // best[i][j]: j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각let row = 1;for (let i = 0; i < m; i++) { const c = Number(lines[row].trim()); const dep = lines[row + 1].trim().split(/\s+/).map(Number); const dur = lines[row + 2].trim().split(/\s+/).map(Number); row += 3; const arr = dep.map((t, j) => t + dur[j]); // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (let j = c - 2; j >= 0; j--) arr[j] = Math.min(arr[j], arr[j + 1]); deps.push(dep); best.push(arr);}// a[j] >= x인 첫 자리(없으면 a.length)function lowerBound(a, x) { let lo = 0; let hi = a.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo;}// a[j] > x인 첫 자리(없으면 a.length)function upperBound(a, x) { let lo = 0; let hi = a.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo;}const out = [];for (let k = 0; k < q; k++) { const [kind, value] = lines[row + k].trim().split(/\s+/); let x = Number(value); if (kind === "A") { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (let i = 0; i < m; i++) { const j = lowerBound(deps[i], x); if (j === deps[i].length) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (let i = m - 1; i >= 0; i--) { const j = upperBound(best[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } out.push(x);}console.log(out.join("\n"));
TypeScriptmain.ts · 72 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [m, q] = lines[0].trim().split(/\s+/).map(Number);const deps: number[][] = []; // deps[i][j]: i번 구간 j번째 열차의 출발 시각(커지는 차례)const best: number[][] = []; // best[i][j]: j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각let row = 1;for (let i = 0; i < m; i++) { const c = Number(lines[row].trim()); const dep: number[] = lines[row + 1].trim().split(/\s+/).map(Number); const dur: number[] = lines[row + 2].trim().split(/\s+/).map(Number); row += 3; const arr: number[] = dep.map((t, j) => t + dur[j]); // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (let j = c - 2; j >= 0; j--) arr[j] = Math.min(arr[j], arr[j + 1]); deps.push(dep); best.push(arr);}// a[j] >= x인 첫 자리(없으면 a.length)function lowerBound(a: number[], x: number): number { let lo = 0; let hi = a.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo;}// a[j] > x인 첫 자리(없으면 a.length)function upperBound(a: number[], x: number): number { let lo = 0; let hi = a.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo;}const out: number[] = [];for (let k = 0; k < q; k++) { const [kind, value] = lines[row + k].trim().split(/\s+/); let x = Number(value); if (kind === "A") { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (let i = 0; i < m; i++) { const j = lowerBound(deps[i], x); if (j === deps[i].length) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (let i = m - 1; i >= 0; i--) { const j = upperBound(best[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } out.push(x);}console.log(out.join("\n"));
JavaMain.java · 80 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { // a[j] >= x인 첫 자리(없으면 a.length) static int lowerBound(long[] a, long x) { int lo = 0, hi = a.length; while (lo < hi) { int mid = (lo + hi) >>> 1; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo; } // a[j] > x인 첫 자리(없으면 a.length) static int upperBound(long[] a, long x) { int lo = 0, hi = a.length; while (lo < hi) { int mid = (lo + hi) >>> 1; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int m = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); // 도착 시각은 30억까지 가므로 long이어야 한다 long[][] deps = new long[m][]; // 출발 시각(커지는 차례) long[][] best = new long[m][]; // j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for (int i = 0; i < m; i++) { int c = Integer.parseInt(br.readLine().trim()); deps[i] = new long[c]; best[i] = new long[c]; st = new StringTokenizer(br.readLine()); for (int j = 0; j < c; j++) deps[i][j] = Long.parseLong(st.nextToken()); st = new StringTokenizer(br.readLine()); for (int j = 0; j < c; j++) best[i][j] = deps[i][j] + Long.parseLong(st.nextToken()); // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (int j = c - 2; j >= 0; j--) best[i][j] = Math.min(best[i][j], best[i][j + 1]); } StringBuilder sb = new StringBuilder(); for (int k = 0; k < q; k++) { st = new StringTokenizer(br.readLine()); String kind = st.nextToken(); long x = Long.parseLong(st.nextToken()); if (kind.equals("A")) { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (int i = 0; i < m; i++) { int j = lowerBound(deps[i], x); if (j == deps[i].length) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (int i = m - 1; i >= 0; i--) { int j = upperBound(best[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } sb.append(x).append('\n'); } System.out.print(sb); }}
C#Main.cs · 94 行
using System;using System.Text;class Program{ // a[j] >= x인 첫 자리(없으면 a.Length) static int LowerBound(long[] a, long x) { int lo = 0, hi = a.Length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo; } // a[j] > x인 첫 자리(없으면 a.Length) static int UpperBound(long[] a, long x) { int lo = 0, hi = a.Length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo; } static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int m = int.Parse(first[0]); int q = int.Parse(first[1]); // 도착 시각은 30억까지 가므로 long이어야 한다 long[][] deps = new long[m][]; // 출발 시각(커지는 차례) long[][] best = new long[m][]; // j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for (int i = 0; i < m; i++) { int c = int.Parse(Console.ReadLine()); string[] d = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); string[] u = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); deps[i] = new long[c]; best[i] = new long[c]; for (int j = 0; j < c; j++) { deps[i][j] = long.Parse(d[j]); best[i][j] = deps[i][j] + long.Parse(u[j]); } // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (int j = c - 2; j >= 0; j--) best[i][j] = Math.Min(best[i][j], best[i][j + 1]); } var sb = new StringBuilder(); for (int k = 0; k < q; k++) { string[] t = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long x = long.Parse(t[1]); if (t[0] == "A") { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (int i = 0; i < m; i++) { int j = LowerBound(deps[i], x); if (j == deps[i].Length) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (int i = m - 1; i >= 0; i--) { int j = UpperBound(best[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } sb.Append(x).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 58 行
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m, q; cin >> m >> q; // 도착 시각은 30억까지 가므로 long long이어야 한다 vector<vector<long long>> deps(m); // 출발 시각(커지는 차례) vector<vector<long long>> best(m); // j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for (int i = 0; i < m; i++) { int c; cin >> c; deps[i].resize(c); best[i].resize(c); for (auto& t : deps[i]) cin >> t; for (int j = 0; j < c; j++) { long long dur; cin >> dur; best[i][j] = deps[i][j] + dur; } // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (int j = c - 2; j >= 0; j--) best[i][j] = min(best[i][j], best[i][j + 1]); } for (int k = 0; k < q; k++) { char kind; long long x; cin >> kind >> x; if (kind == 'A') { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차 → lower_bound for (int i = 0; i < m; i++) { auto it = lower_bound(deps[i].begin(), deps[i].end(), x); if (it == deps[i].end()) { x = -1; break; } x = best[i][it - deps[i].begin()]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차 → upper_bound의 바로 앞 for (int i = m - 1; i >= 0; i--) { auto it = upper_bound(best[i].begin(), best[i].end(), x); if (it == best[i].begin()) { x = -1; break; } x = deps[i][it - best[i].begin() - 1]; } } cout << x << '\n'; } return 0;}
Cmain.c · 85 行
#include <stdio.h>#include <stdlib.h>// a[j] >= x인 첫 자리(없으면 n)static int lower_bound(const long long *a, int n, long long x) { int lo = 0, hi = n; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo;}// a[j] > x인 첫 자리(없으면 n)static int upper_bound(const long long *a, int n, long long x) { int lo = 0, hi = n; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo;}int main(void) { int m, q; if (scanf("%d %d", &m, &q) != 2) return 1; // 도착 시각은 30억까지 가므로 long long이어야 한다 int cnt[10]; long long *deps[10]; // 출발 시각(커지는 차례) long long *best[10]; // j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for (int i = 0; i < m; i++) { int c; scanf("%d", &c); cnt[i] = c; deps[i] = malloc(sizeof(long long) * c); best[i] = malloc(sizeof(long long) * c); for (int j = 0; j < c; j++) scanf("%lld", &deps[i][j]); for (int j = 0; j < c; j++) { long long dur; scanf("%lld", &dur); best[i][j] = deps[i][j] + dur; } // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (int j = c - 2; j >= 0; j--) { if (best[i][j + 1] < best[i][j]) best[i][j] = best[i][j + 1]; } } for (int k = 0; k < q; k++) { char kind; long long x; scanf(" %c %lld", &kind, &x); if (kind == 'A') { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (int i = 0; i < m; i++) { int j = lower_bound(deps[i], cnt[i], x); if (j == cnt[i]) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (int i = m - 1; i >= 0; i--) { int j = upper_bound(best[i], cnt[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } printf("%lld\n", x); } for (int i = 0; i < m; i++) { free(deps[i]); free(best[i]); } return 0;}
Craykonmain.cray · 98 行
첫줄 = 控制台.读数字();m = 첫줄[0];q = 첫줄[1];deps = []; // deps[i][j]: i번 구간 j번째 열차의 출발 시각(커지는 차례)best = []; // best[i][j]: j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각循环 (i = 0; i < m; i++){ c = 控制台.读数字()[0]; dep = 控制台.读数字(); arr = 控制台.读数字(); 循环 (j = 0; j < c; j++) { arr[j] = dep[j] + arr[j]; } // 뒤에서부터 최솟값을 누적하면 커지기만 하는 목록이 되어 이분 탐색을 할 수 있다 循环 (j = c - 2; j >= 0; j--) { arr[j] = 数学.较小值(arr[j], arr[j + 1]); } deps.添加(dep); best.添加(arr);}循环 (k = 0; k < q; k++){ t = 控制台.读行().去空白().分割(); x = t[1].转数字(); 如果 (t[0] == "A") { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 循环 (i = 0; i < m; i++) { j = 첫자리이상(deps[i], x); 如果 (j == deps[i].数量) { x = -1; 跳出; } x = best[i][j]; } } 否则 { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 循环 (i = m - 1; i >= 0; i--) { j = 첫자리초과(best[i], x) - 1; 如果 (j < 0) { x = -1; 跳出; } x = deps[i][j]; } } 控制台.输出(x);}// a[j] >= x인 첫 자리(없으면 a.개수)첫자리이상(a, x){ lo = 0; hi = a.数量; 当 (lo < hi) { mid = 数学.商(lo + hi, 2); 如果 (a[mid] < x) { lo = mid + 1; } 否则 { hi = mid; } } 返回 lo;}// a[j] > x인 첫 자리(없으면 a.개수)첫자리초과(a, x){ lo = 0; hi = a.数量; 当 (lo < hi) { mid = 数学.商(lo + hi, 2); 如果 (a[mid] <= x) { lo = mid + 1; } 否则 { hi = mid; } } 返回 lo;}