There are m + 1 stations in a line, and trains of leg i (1 ≤ i ≤ m) go only from the i-th station to the (i + 1)-th station.
To reach the last station you must ride exactly one train on each leg, in order from leg 1 to leg m.
Each leg has a timetable, and each train is written as a departure time and a travel time.
A train reaches the next station at its departure time plus its travel time.
Within one leg all departure times are different, but some trains are fast, so a train that leaves later may arrive earlier.
If you are at a station at time x, you can board a train there whose departure time is x or later (a train leaving at the very time you arrive can be boarded).
Answer q questions.
A question "A t" asks for the earliest time you can reach the last station if you are at the first station at time t.
A question "B d" asks how late the departure time of the train you ride on leg 1 can be if you must reach the last station at time d or earlier.
Print the answer to each question on its own line.
Print -1 if, for a question A, there is no way to reach the last station, or, for a question B, there is no way to reach the last station at time d or earlier.
Input
The first line gives m and q separated by a space. Then, for each leg starting with leg 1, three lines follow: the number of trains c, the c departure times (in increasing order, separated by single spaces), and the c travel times (in the same order as the departure times). Each of the next q lines gives one question, "A t" or "B d". 1 ≤ m ≤ 10, 1 ≤ c, the sum of c over all legs ≤ 10,000, 1 ≤ q ≤ 5,000, 0 ≤ departure time ≤ 2,000,000,000, 1 ≤ travel time ≤ 1,000,000,000, 0 ≤ t, d ≤ 3,000,000,000
Output
q lines. For a question A the earliest time of reaching the last station, for a question B the latest departure time of the leg 1 train, or -1 if it cannot be done. Write numbers as plain digits without commas
Example 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
stdout
45
65
-1
20
30
-1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
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
Binary search finds 'the position where the condition turns true', so the list has to grow in one direction only. The departure times are sorted, but the arrival times are jumbled because of overtaking. So accumulate the minimum from the back to get 'the earliest arrival if you ride train j or a later one': that list only grows, so you can binary search it, and the answer to question A is read straight from it. Question A needs 'the first position with departure ≥ current time' (lower bound) and question B needs 'the last position with accumulated arrival ≤ deadline' (just before the upper bound). The tools differ by language: Python bisect_left / bisect_right and C++ std::lower_bound / std::upper_bound fit exactly. Java Arrays.binarySearch and C# Array.BinarySearch return the insertion position turned negative when the value is missing (Java -(position) - 1, C# ~position), and when the value occurs several times they do not promise which one you get, so for a list with runs of equal values, like the accumulated arrivals, writing your own is safer. C bsearch finds only an equal value and returns NULL otherwise, so it cannot be used here. JS, TS and Craykon have none, so you write it yourself (in Craykon the middle is Mathf.Quot(lo + hi, 2)). Trap one: riding the first train you can board is wrong. An express that leaves later can arrive earlier. Trap two: binary searching the arrival times without accumulating gives a wrong position with no error. Trap three: the boundaries. You can board a train that leaves at the very time you arrive (>=), and arriving exactly at the deadline is fine (<=). Swapping lower bound and upper bound is wrong in exactly these cases. Trap four: a departure time of 2 billion fits a 32-bit int, but 3 billion after adding the travel time overflows. Java and C# give a negative number with no error and in C and C++ it is undefined behaviour, so read into long / long long. The t and d of the questions also go up to 3 billion, so an int cannot even read them. Python, JS, TS and Craykon just work.
Pythonmain.py · 50 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
첫줄 = Console.ReadNumbers();m = 첫줄[0];q = 첫줄[1];deps = []; // deps[i][j]: i번 구간 j번째 열차의 출발 시각(커지는 차례)best = []; // best[i][j]: j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각for (i = 0; i < m; i++){ c = Console.ReadNumbers()[0]; dep = Console.ReadNumbers(); arr = Console.ReadNumbers(); for (j = 0; j < c; j++) { arr[j] = dep[j] + arr[j]; } // 뒤에서부터 최솟값을 누적하면 커지기만 하는 목록이 되어 이분 탐색을 할 수 있다 for (j = c - 2; j >= 0; j--) { arr[j] = Mathf.Min(arr[j], arr[j + 1]); } deps.Add(dep); best.Add(arr);}for (k = 0; k < q; k++){ t = Console.ReadLine().Trim().Split(); x = t[1].ToNumber(); if (t[0] == "A") { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (i = 0; i < m; i++) { j = 첫자리이상(deps[i], x); if (j == deps[i].Count) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (i = m - 1; i >= 0; i--) { j = 첫자리초과(best[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } Console.WriteLine(x);}// a[j] >= x인 첫 자리(없으면 a.개수)첫자리이상(a, x){ lo = 0; hi = a.Count; while (lo < hi) { mid = Mathf.Quot(lo + hi, 2); if (a[mid] < x) { lo = mid + 1; } else { hi = mid; } } return lo;}// a[j] > x인 첫 자리(없으면 a.개수)첫자리초과(a, x){ lo = 0; hi = a.Count; while (lo < hi) { mid = Mathf.Quot(lo + hi, 2); if (a[mid] <= x) { lo = mid + 1; } else { hi = mid; } } return lo;}