https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0360?year=2017
解法
https://onlinejudge.u-aizu.ac.jp/solutions/problem/0360/review/3136426/hamayanhamayan/C++14
この問題では半開区間で区間が表現されているが、閉区間に直して解くことにする。
区間についてはここが詳しい
N個すべての区間について[a,b]と重なるかどうかを判定する。
重なるかの判定がすこしやりにくいので、重なっていないかを判定することにする。
区間[a,b]と区間[s,f]が重なっていないのは、b<sまたはf<aを満たす場合である。
b<sとなるのは[a,b],[s,f]の順で区間が並んでいる状態である。
f<aとなるのは[s,f],[a,b]の順で区間が並んでいる状態である。
重なっていないならば、continueをして次の区間を見る。
重なっていれば1と出力して終了。
なお、この問題はimos法を用いても解ける。
imos法の練習問題としても良いだろう。
int a, b, N; //--------------------------------------------------------------------------------------------------- void _main() { cin >> a >> b >> N; b--; rep(i, 0, N) { int s, f; cin >> s >> f; f--; if (b < s) continue; if (f < a) continue; printf("1\n"); return; } printf("0\n"); return; }