本番中は解けませんでした、残念。
問題概要
Hyunukさんは新年のカンファレンスを開きたい。
ここで、会場Aと会場B、二つの会場候補が存在する。
カンファレンスではN個の会議が行われるが、会場Aで行われる場合と会場Bで行われる場合とで開始時刻と終了時刻が異なる（たまたま一致することもある）。
ここで、講義iが閉区間[sa[i], ea[i]]で行われる時（時刻sa[i]に開始してeaに終わるとき）、講義jの閉区間[sa[j], ea[j]]とオーバーラップがあると講義に両方参加することができない。
形式的にはsa[i] <= ea[j]かつ、sa[j] <= ea[i]ならばオーバーラップがあるとみなす。
ここで、ある講義のサブセットを選ぶとする。
一方の会場ではそのサブセットの講義全てに参加できるが、もう一方の会場では講義全てに参加できない（オーバーラップがある）とき、その講義のセットをvenus-sensitive（意訳：会場依存がある）講義サブセットと呼ぶ。
会場依存があるように講義サブセットを選ぶことが可能なとき、NOと出力し、そうでない場合YESと出力せよ。
方針概要
あるペアiとjについてに会場依存性があるなら、会場依存性があるサブセットを構成することができる。（というか(i, j)がそのようなサブセットである。）
そして、講義の重なりがあるかどうかは純粋に講義iと講義jの時刻関係で決まり他の講義は関係がない。
そのため、逆にそのようなペアが存在しない場合、会場依存性があるサブセットを構成することが出来ない。
よって全てのペアについて、「Aで重なっていれば、Bでも重なっている」「Aで重なっていなければ、Bでも重なっていない」を確認できる時YESを出力し、そうでなければNOを出力すれば良い。
ただし、愚直に全てのペアについて確認するとO(N^2)ほどかかり、N = 10^5なので間に合わない。そこで二分探索木等を使ってオーダーを落としていく必要がある。
詳細方針
会場依存があるように講義サブセットを選ぶことが可能かどうか確認するためには、全ペアについて「会場Aでオーバーラップがしているペアなら会場Bでもオーバーラップしている」と「BでオーバーラップがしているペアならAでもオーバーラップしている」を 別々に両方判定すれば良い。
まず「会場Aにオーバーラップでしているペアなら会場Bでもオーバーラップしている」を判定することにする。これができるなら、AとBをスワップすることで、「会場Bでオーバーラップがしているペアなら会場Aでもオーバーラップしている」を判定できる。
ここでイベントソートを使って、Aでのオーバーラップを管理し、さらにそれらがBでも重なっているか判定する。
管理部
一つセット(時系列管理セットと呼ぶ)を持ち、会場Aにおけるすべてのイベント（講義の開始と終了）を時系列順にならべ、講義が開始したら時系列管理セットにその講義を追加し、終了したら時系列管理セットから除去する。
時系列管理セットから講義iを除去した時点において、時系列管理セットに存在していた講義すべてがiと会場Aにてオーバーラップする講義の全集合である。
またこの計算はO(N)でできる。(ソートを除く)
判定部
会場Bでの開始時刻セットと終了時刻セットを用意する。(二分探索木など、orderedである必要がある。)
時系列管理セットに講義iを追加する時、講義iのBの開始時刻と終了時刻をそれぞれのセットに追加する。
時系列管理セットに講義iを除去する時、講義iのBの開始時刻と終了時刻をそれぞれのセットから除去する。
このようなことをしたとき、除去された講義iのBにおける開始時刻が他の講義全ての終了時刻より早く、かつ講義iのBにおける終了時刻が他の講義の開始時刻より遅ければ、
「会場Aにおいて講義iとオーバーラップしている他の講義全てが会場Bでもオーバーラップしている」と判定される。
ただし逆に「会場Bにおいて講義iとオーバーラップしている他の講義全てが会場Aでもオーバーラップしている」かはわからないことに注意。
ここで除去された講義iのBにおける開始時刻が他の講義全ての終了時刻より早いかどうかは終了時刻セットの最小値と比較すればよくO(logN)で計算できる。
講義iの終了時刻も同様に最大値と比較すれば良い。
講義iを[0. N)について計算すると計算の総量はO(NlogN)ということになり、間に合う。
実装
時系列管理セットを説明の便宜上導入したが、実はBの開始時刻セットとBの終了時刻セットがあれば十分であるので、実装には含めていない。
開始時刻や終了時刻は同時である場合があるので、multisetが欲しい。RustなのでBTreeMapを使い、valueでその時刻に何個存在するかカウントすることにした。
use std::collections::*; fn main() { let n = read::<usize>(); let mut events = vec![]; let mut events_swapped = vec![]; for _ in 0..n { let v = read_vec::<i64>(); events.push((v[0], v[1], v[2], v[3])); events_swapped.push((v[2], v[3], v[0], v[1])); } if solve(&events) && solve(&events_swapped) { println!("YES"); } else { println!("NO"); } } // 「会場Aで重なり存在するペアであればBでも重なりが存在する」が真ならtrue、偽ならfalse fn solve(events: &Vec<(i64, i64, i64, i64)>) -> bool { let mut events_a_decoded = vec![]; // 会場Aで発生するイベントをソート。 // ここで、同時刻で講義の終わりと始まりが起きた時はオーバーラップがあったとみなすため、始まりを先に来るようにする。 for (i, &(sa, ea, _, _)) in events.iter().enumerate() { events_a_decoded.push((sa, 0, i)); events_a_decoded.push((ea, 1, i)); } events_a_decoded.sort(); // イベントソート // multisetがないので、BTreeMapを使う。カウントがゼロになったら消去。 let mut b_starts = BTreeMap::new(); // Aで開催中の講義のBにおける開始時刻を管理 let mut b_ends = BTreeMap::new(); // Aで開催中の講義のBにおける終了時刻を管理 for (_, is_start, i) in events_a_decoded { if is_start == 0 { *b_starts.entry(events[i].2).or_insert(0) += 1; *b_ends.entry(events[i].3).or_insert(0) += 1; } else { // 除去される講義iの開始時刻より早く終わる講義が存在するということは、会場AではオーバーラップするのにBではオーバーラップしない組み合わせが存在するということ。 // なので偽を返す if events[i].2 > *b_ends.iter().next().unwrap().0 { return false; } // 除去される講義iの終了時刻より遅くに開始する講義が存在するということは、会場AではオーバーラップするのにBではオーバーラップしない組み合わせが存在するということ。 // なので偽を返す if events[i].3 < *b_starts.iter().rev().next().unwrap().0 { return false; } // event[i]開始および終了時刻でのイベントカウントを一つ減らす。ゼロになったらセットから消す。 *b_starts.get_mut(&events[i].2).unwrap() -= 1; if b_starts[&events[i].2] == 0 { b_starts.remove(&events[i].2); } *b_ends.get_mut(&events[i].3).unwrap() -= 1; if b_ends[&events[i].3] == 0 { b_ends.remove(&events[i].3); } } } true } // 入力受け取る用の関数達 fn read<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() }
