Trains of line A and line B arrive at a station.
The timetable of line A lists the arrival times a_1 < a_2 < … < a_n of its n trains, and the timetable of line B lists the arrival times b_1 < b_2 < … < b_m of its m trains, in seconds.
You are given q questions. The questions are independent of each other.
A question "k d" asks for the k-th train to arrive, counting both lines together, on a day when every train of line B arrives d seconds later than its timetable and line A runs on its timetable.
If two trains arrive at the same time, the train of line A counts as arriving first.
For each question print on one line the line of that train (A or B), which train it is in that line's timetable, and the time it actually arrives that day, separated by single spaces.
In example 1, when d is 5 the trains of line B arrive at 10, 20, 30 and 45 seconds. So the order of arrival is train 1 of A (10), train 1 of B (10), train 2 of A (20), train 2 of B (20), train 3 of A (30), train 3 of B (30), train 4 of B (45).
Input
The first line gives n, m and q separated by single spaces. The second line gives a_1, …, a_n and the third line gives b_1, …, b_m, separated by single spaces. Each of the next q lines gives k and d separated by one space. 1 ≤ n, m ≤ 9,000, 1 ≤ q ≤ 9,000, 0 ≤ a_i, b_i ≤ 2 × 10^9, 1 ≤ k ≤ n + m, 0 ≤ d ≤ 2 × 10^9 (all integers, given as plain digits without commas)
Output
For each question one line with the line (A or B), which train it is in that line, and the time it actually arrives that day
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
If i of the first k trains to arrive belong to line A, then k-i belong to line B. This i is found by binary search. For a[mid] of A (counting from 0) to be among the first k, at most k-mid-1 trains of B may arrive before it, which is the same as b[k - mid - 1] + d >= a[mid]. As mid grows this condition changes from true to false only once. Narrowing with lo = mid + 1 when it is true and hi = mid when it is false fixes i in about 14 rounds. The k-th train is whichever arrives later of the i-th of A and the (k-i)-th of B. The middle is (lo + hi) // 2 in Python, (lo + hi) / 2 in Java, C#, C and C++, Math.floor((lo + hi) / 2) in JavaScript and TypeScript, and Mathf.Quot(lo + hi, 2) in Craykon. Python bisect and C++ std::lower_bound are tools for finding one value in one list, so they cannot be used as they are for this condition that looks at two lists together; the loop is written by hand. Trap one: counting through the two timetables from the front up to the k-th train for every question counts about 160 million times on the largest input. Because d differs from question to question, you cannot reuse an order merged once either. A Python solution written this way did not finish in time. To be honest, a C solution written the same way finished within 0.4 seconds on this computer. Binary search is really needed only in the slow languages. Trap two: at the same time, A comes first. So the condition and the final comparison must be >=. Writing both with > counts B as first: the second question "2 5" of example 1 gives A 1 10 instead of B 1 10, and the third gives B 2 20 instead of A 2 20. Trap three: the range of i is not 0 to n but max(0, k - m) to min(k, n). With the range 0 to n, k - mid - 1 becomes negative or reaches m or more. Python reads a negative index as a position counted from the end, so it silently prints A 2 20 for the first question of example 1 (the answer is B 1 5), and for the fifth question "7 5" it stops with IndexError while reading b[5]. Java and C# stop with an exception in both cases, and in C and C++ what happens is not defined. Trap four: the time to print is not the timetable time but the time the train actually arrives that day. For line B you must add d. Without it the second question of example 1 gives B 1 5 instead of B 1 10. Trap five: the times and d each go up to 2 × 10^9 and fit in a 32-bit int, but their sum grows up to 4 × 10^9 and overflows. Java, C#, C and C++ must keep the times and d in long/long long. Keeping them in Java int turns 4000000000 into -294967296 for the second question of example 2, which gives A 1 2000000000 instead of B 2 4000000000. Python integers have no size limit, and numbers in JavaScript, TypeScript and Craykon are exact up to 2^53, so they are right as they are.
Pythonmain.py · 33 lines
import sysdef main(): data = sys.stdin.buffer.read().split() n, m, q = int(data[0]), int(data[1]), int(data[2]) a = [int(x) for x in data[3:3 + n]] b = [int(x) for x in data[3 + n:3 + n + m]] out = [] pos = 3 + n + m for _ in range(q): k, d = int(data[pos]), int(data[pos + 1]) pos += 2 # 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. lo = max(0, k - m) hi = min(k, n) while lo < hi: mid = (lo + hi) // 2 # A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if b[k - mid - 1] + d >= a[mid]: lo = mid + 1 else: hi = mid i, j = lo, k - lo # k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if i == 0 or (j > 0 and b[j - 1] + d >= a[i - 1]): out.append("B %d %d" % (j, b[j - 1] + d)) else: out.append("A %d %d" % (i, a[i - 1])) print("\n".join(out))main()
JavaScriptmain.js · 27 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const m = data[1];const q = data[2];const a = data.slice(3, 3 + n);const b = data.slice(3 + n, 3 + n + m);const out = [];for (let x = 0; x < q; x++) { const k = data[3 + n + m + 2 * x]; const d = data[4 + n + m + 2 * x]; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. let lo = Math.max(0, k - m); let hi = Math.min(k, n); while (lo < hi) { const mid = Math.floor((lo + hi) / 2); // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } const i = lo; const j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i === 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) out.push("B " + j + " " + (b[j - 1] + d)); else out.push("A " + i + " " + a[i - 1]);}console.log(out.join("\n"));
TypeScriptmain.ts · 28 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const m = data[1];const q = data[2];const a: number[] = data.slice(3, 3 + n);const b: number[] = data.slice(3 + n, 3 + n + m);const out: string[] = [];for (let x = 0; x < q; x++) { const k = data[3 + n + m + 2 * x]; const d = data[4 + n + m + 2 * x]; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. let lo = Math.max(0, k - m); let hi = Math.min(k, n); while (lo < hi) { const mid = Math.floor((lo + hi) / 2); // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } const i = lo; const j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i === 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) out.push("B " + j + " " + (b[j - 1] + d)); else out.push("A " + i + " " + a[i - 1]);}console.log(out.join("\n"));
JavaMain.java · 42 lines
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); long[] a = new long[n]; long[] b = new long[m]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken()); st = new StringTokenizer(in.readLine()); for (int i = 0; i < m; i++) b[i] = Long.parseLong(st.nextToken()); StringBuilder out = new StringBuilder(); for (int x = 0; x < q; x++) { st = new StringTokenizer(in.readLine()); int k = Integer.parseInt(st.nextToken()); long d = Long.parseLong(st.nextToken()); // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. int lo = Math.max(0, k - m); int hi = Math.min(k, n); while (lo < hi) { int mid = (lo + hi) / 2; // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) { out.append("B ").append(j).append(' ').append(b[j - 1] + d).append('\n'); } else { out.append("A ").append(i).append(' ').append(a[i - 1]).append('\n'); } } System.out.print(out); }}
C#Main.cs · 38 lines
using System;using System.Text;class Program{ static void Main() { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(p[0]), m = int.Parse(p[1]), q = int.Parse(p[2]); long[] a = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); long[] b = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); var sb = new StringBuilder(); for (int x = 0; x < q; x++) { p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int k = int.Parse(p[0]); long d = long.Parse(p[1]); // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. int lo = Math.Max(0, k - m); int hi = Math.Min(k, n); while (lo < hi) { int mid = (lo + hi) / 2; // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) sb.Append("B ").Append(j).Append(' ').Append(b[j - 1] + d).Append('\n'); else sb.Append("A ").Append(i).Append(' ').Append(a[i - 1]).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 34 lines
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; vector<long long> a(n), b(m); for (auto& v : a) cin >> v; for (auto& v : b) cin >> v; while (q--) { int k; long long d; cin >> k >> d; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. int lo = max(0, k - m); int hi = min(k, n); while (lo < hi) { int mid = (lo + hi) / 2; // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) cout << "B " << j << ' ' << b[j - 1] + d << '\n'; else cout << "A " << i << ' ' << a[i - 1] << '\n'; } return 0;}
Cmain.c · 30 lines
#include <stdio.h>static long long a[9000], b[9000];int main(void) { int n, m, q; if (scanf("%d %d %d", &n, &m, &q) != 3) return 0; for (int i = 0; i < n; i++) if (scanf("%lld", &a[i]) != 1) return 0; for (int i = 0; i < m; i++) if (scanf("%lld", &b[i]) != 1) return 0; for (int x = 0; x < q; x++) { int k; long long d; if (scanf("%d %lld", &k, &d) != 2) return 0; /* 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. */ int lo = k - m > 0 ? k - m : 0; int hi = k < n ? k : n; while (lo < hi) { int mid = (lo + hi) / 2; /* A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 */ if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; /* k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 */ if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) printf("B %d %lld\n", j, b[j - 1] + d); else printf("A %d %lld\n", i, a[i - 1]); } return 0;}
Craykonmain.cray · 40 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1];q = 첫줄[2];a = Console.ReadNumbers();b = Console.ReadNumbers();for (x = 0; x < q; x++){ 줄 = Console.ReadNumbers(); k = 줄[0]; d = 줄[1]; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. lo = Mathf.Max(0, k - m); hi = Mathf.Min(k, n); while (lo < hi) { mid = Mathf.Quot(lo + hi, 2); // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) { lo = mid + 1; } else { hi = mid; } } i = lo; j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i == 0 || j > 0 && b[j - 1] + d >= a[i - 1]) { Console.WriteLine("B " + j + " " + (b[j - 1] + d)); } else { Console.WriteLine("A " + i + " " + a[i - 1]); }}