会議室一つの一日の予約 n 件と質問 q 個が与えられる。 時刻は 0 以上の整数である。 一行目に n と q が与えられる。 続く n 行に予約が一行に一つずつ "s e" の形で与えられる。 この予約は時刻 s から e の直前まで会議室を使う。 だから時刻 s には使用中で、時刻 e にはこの予約では使用中ではない。 予約は開始時刻の早い順に与えられ、互いに重ならない。 ただし、前の予約が終わる時刻に次の予約がすぐ始まることはある。 このような予約は接しているという。 最後の行に、質問する時刻 t が q 個空白で区切って与えられる。 質問ごとに一行に答えを出力せよ。 時刻 t に会議室を使う予約があれば "busy X" を出力する。 X は、その予約と、その後に接して続く予約がすべて終わって会議室が初めて空く時刻である。 時刻 t に使う予約がなければ "free Y" を出力する。 Y は、t より後に始まる予約のうちいちばん早いものの開始時刻である。 t より後に始まる予約がなければ "free none" を出力する。 予約も質問も多いので、質問ごとに予約を最初から見ていかず、半分に分けて探すこと。
入力
1 ≤ n ≤ 10,000、1 ≤ q ≤ 10,000、0 ≤ s < e ≤ 1,000,000,000、前の予約の e ≤ 次の予約の s、0 ≤ t ≤ 1,000,000,000
出力
質問ごとに一行：busy X、free Y、free none のいずれか
例 1 · stdin
3 6
9 10
10 12
14 16
9 11 12 13 16 3
stdout
busy 12
busy 12
free 14
free 14
free none
free 9
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
整列された配列から探す道具は言語ごとに違います。 Python bisect.bisect_right(S, t)、C++ std::upper_bound は t より大きい最初の位置を返すので、そのすぐ前が「開始時刻が t 以下の最後の予約」です。 Java Arrays.binarySearch、C# Array.BinarySearch は同じ値を見つければその位置を、見つからなければ負の数 -(挿入位置) - 1 を返します（C# は ~pos で挿入位置を取り出します）。 同じ値が複数あるとどの位置を返すかは約束されていませんが、この問題は開始時刻がすべて違うので使えます。 JS・TS・Craykon にはこうした関数がなく、C の bsearch は同じ値しか探さないので、自分で書きます。 lo、hi を「S[0..lo) は t 以下、S[hi..n) は t より大きい」として狭めると、終わったとき lo - 1 が答えです。 Craykon と JS の / は小数まで割るので、真ん中は 数学.商(lo + hi, 2) や >> 1 で求めます。 一つ目の落とし穴は境界です。 bisect_left（同じ値の前の位置）を使うと、t が予約の開始時刻と同じときにその予約を見落とします。 予約は e の直前までなので、t == e ならその予約では使用中ではなく、t < E[i] です。 二つ目の落とし穴は、最初の予約より早い t です。 見つけた番号は -1 ですが、Python では E[-1] はエラーではなく最後の予約なので、間違って busy と出ます。 Java・C#・Craykon は範囲外の読み込みエラーで止まり、JS・TS は undefined になって比較がいつも偽になり、C・C++ は未定義動作なので、先に i >= 0 を確かめます。 三つ目に、接した予約を質問ごとにたどると鎖が長いときに遅いので、後ろから「ここから続いて初めて空く時刻」を一度埋めておきます。
Pythonmain.py · 25 行
import sysfrom bisect import bisect_rightdata = sys.stdin.read().split()n, q = int(data[0]), int(data[1])S = [int(x) for x in data[2:2 + 2 * n:2]]E = [int(x) for x in data[3:3 + 2 * n:2]]queries = data[2 + 2 * n:]# block_end[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다)block_end = E[:]for i in range(n - 2, -1, -1): if E[i] == S[i + 1]: block_end[i] = block_end[i + 1]out = []for t in map(int, queries): i = bisect_right(S, t) - 1 # 시작 시각이 t 이하인 마지막 예약(없으면 -1) if i >= 0 and t < E[i]: # i가 -1이면 E[-1]이 마지막 예약이 되니 먼저 확인한다 out.append(f"busy {block_end[i]}") elif i + 1 < n: out.append(f"free {S[i + 1]}") else: out.append("free none")print("\n".join(out))
JavaScriptmain.js · 31 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q] = data;const S = [], E = [];for (let i = 0; i < n; i++) { S.push(data[2 + 2 * i]); E.push(data[3 + 2 * i]);}// blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다)const blockEnd = E.slice();for (let i = n - 2; i >= 0; i--) if (E[i] === S[i + 1]) blockEnd[i] = blockEnd[i + 1];// 시작 시각이 t 이하인 마지막 예약의 번호(없으면 -1)function lastStartAtMost(t) { let lo = 0, hi = n; // 답은 [lo, hi) 바로 앞: S[0..lo)는 t 이하, S[hi..n)은 t 초과 while (lo < hi) { const mid = (lo + hi) >> 1; if (S[mid] <= t) lo = mid + 1; else hi = mid; } return lo - 1;}const out = [];for (let j = 0; j < q; j++) { const t = data[2 + 2 * n + j]; const i = lastStartAtMost(t); if (i >= 0 && t < E[i]) out.push(`busy ${blockEnd[i]}`); else if (i + 1 < n) out.push(`free ${S[i + 1]}`); else out.push("free none");}console.log(out.join("\n"));
TypeScriptmain.ts · 32 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q] = data;const S: number[] = [], E: number[] = [];for (let i = 0; i < n; i++) { S.push(data[2 + 2 * i]); E.push(data[3 + 2 * i]);}// blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다)const blockEnd: number[] = E.slice();for (let i = n - 2; i >= 0; i--) if (E[i] === S[i + 1]) blockEnd[i] = blockEnd[i + 1];// 시작 시각이 t 이하인 마지막 예약의 번호(없으면 -1)function lastStartAtMost(t: number): number { let lo = 0, hi = n; // S[0..lo)는 t 이하, S[hi..n)은 t 초과 while (lo < hi) { const mid: number = (lo + hi) >> 1; if (S[mid] <= t) lo = mid + 1; else hi = mid; } return lo - 1;}const out: string[] = [];for (let j = 0; j < q; j++) { const t: number = data[2 + 2 * n + j]; const i: number = lastStartAtMost(t); if (i >= 0 && t < E[i]) out.push(`busy ${blockEnd[i]}`); else if (i + 1 < n) out.push(`free ${S[i + 1]}`); else out.push("free none");}console.log(out.join("\n"));
JavaMain.java · 46 行
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int n; static int[] S, E; // 시작 시각이 t 이하인 마지막 예약의 번호(없으면 -1) static int lastStartAtMost(int t) { int lo = 0, hi = n; // S[0..lo)는 t 이하, S[hi..n)은 t 초과 while (lo < hi) { int mid = (lo + hi) >>> 1; if (S[mid] <= t) lo = mid + 1; else hi = mid; } return lo - 1; } public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); S = new int[n]; E = new int[n]; for (int i = 0; i < n; i++) { st = new StringTokenizer(in.readLine()); S[i] = Integer.parseInt(st.nextToken()); E[i] = Integer.parseInt(st.nextToken()); } // blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다) int[] blockEnd = E.clone(); for (int i = n - 2; i >= 0; i--) if (E[i] == S[i + 1]) blockEnd[i] = blockEnd[i + 1]; st = new StringTokenizer(in.readLine()); StringBuilder out = new StringBuilder(); for (int j = 0; j < q; j++) { int t = Integer.parseInt(st.nextToken()); int i = lastStartAtMost(t); if (i >= 0 && t < E[i]) out.append("busy ").append(blockEnd[i]).append('\n'); else if (i + 1 < n) out.append("free ").append(S[i + 1]).append('\n'); else out.append("free none\n"); } System.out.print(out); }}
C#Main.cs · 35 行
using System;using System.Text;class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]), q = int.Parse(first[1]); int[] S = new int[n], E = new int[n]; for (int i = 0; i < n; i++) { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); S[i] = int.Parse(p[0]); E[i] = int.Parse(p[1]); } // blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다) int[] blockEnd = (int[])E.Clone(); for (int i = n - 2; i >= 0; i--) if (E[i] == S[i + 1]) blockEnd[i] = blockEnd[i + 1]; string[] qs = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); var sb = new StringBuilder(); for (int j = 0; j < q; j++) { int t = int.Parse(qs[j]); // Array.BinarySearch는 같은 값이 없으면 ~(t보다 큰 첫 자리)를 돌려준다. // 시작 시각은 모두 다르니, 찾으면 그 자리, 못 찾으면 그 앞 자리가 "t 이하인 마지막"이다 int pos = Array.BinarySearch(S, t); int i = pos >= 0 ? pos : ~pos - 1; if (i >= 0 && t < E[i]) sb.Append("busy ").Append(blockEnd[i]).Append('\n'); else if (i + 1 < n) sb.Append("free ").Append(S[i + 1]).Append('\n'); else sb.Append("free none\n"); } Console.Write(sb); }}
C++main.cpp · 27 行
#include <algorithm>#include <iostream>#include <string>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<int> S(n), E(n); for (int i = 0; i < n; i++) std::cin >> S[i] >> E[i]; // blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다) std::vector<int> blockEnd = E; for (int i = n - 2; i >= 0; i--) if (E[i] == S[i + 1]) blockEnd[i] = blockEnd[i + 1]; std::string out; for (int j = 0; j < q; j++) { int t; std::cin >> t; // upper_bound는 t보다 큰 첫 자리. 그 바로 앞이 시작 시각이 t 이하인 마지막 예약이다 int i = int(std::upper_bound(S.begin(), S.end(), t) - S.begin()) - 1; if (i >= 0 && t < E[i]) out += "busy " + std::to_string(blockEnd[i]) + "\n"; else if (i + 1 < n) out += "free " + std::to_string(S[i + 1]) + "\n"; else out += "free none\n"; } std::cout << out;}
Cmain.c · 33 行
#include <stdio.h>static int S[10000], E[10000], blockEnd[10000];static int n;/* 시작 시각이 t 이하인 마지막 예약의 번호(없으면 -1) */int last_start_at_most(int t) { int lo = 0, hi = n; /* S[0..lo)는 t 이하, S[hi..n)은 t 초과 */ while (lo < hi) { int mid = lo + (hi - lo) / 2; if (S[mid] <= t) lo = mid + 1; else hi = mid; } return lo - 1;}int main(void) { int q, t; scanf("%d %d", &n, &q); for (int i = 0; i < n; i++) scanf("%d %d", &S[i], &E[i]); /* blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다) */ for (int i = n - 1; i >= 0; i--) { blockEnd[i] = (i + 1 < n && E[i] == S[i + 1]) ? blockEnd[i + 1] : E[i]; } for (int j = 0; j < q; j++) { scanf("%d", &t); int i = last_start_at_most(t); if (i >= 0 && t < E[i]) printf("busy %d\n", blockEnd[i]); else if (i + 1 < n) printf("free %d\n", S[i + 1]); else puts("free none"); } return 0;}
Craykonmain.cray · 58 行
첫줄 = コンソール.数読み();n = 첫줄[0];q = 첫줄[1];S = [];E = [];繰り返す (i = 0; i < n; i++){ p = コンソール.数読み(); S.追加(p[0]); E.追加(p[1]);}// blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다)blockEnd = E.部分リスト(0, n);繰り返す (i = n - 2; i >= 0; i--){ もし (E[i] == S[i + 1]) { blockEnd[i] = blockEnd[i + 1]; }}// 시작 시각이 t 이하인 마지막 예약의 번호(없으면 -1)마지막시작(t){ lo = 0; hi = n; // S[0..lo)는 t 이하, S[hi..n)은 t 초과 間 (lo < hi) { mid = 数学.商(lo + hi, 2); // /는 소수까지 나누니 몫을 쓴다 もし (S[mid] <= t) { lo = mid + 1; } でなければ { hi = mid; } } 返す lo - 1;}qs = コンソール.数読み();それぞれ (t の中 qs){ i = 마지막시작(t); もし (i >= 0 && t < E[i]) { コンソール.書く("busy " + blockEnd[i]); } でなければ もし (i + 1 < n) { コンソール.書く("free " + S[i + 1]); } でなければ { コンソール.書く("free none"); }}