けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

平面走査

Educational Codeforces Round 73 F. Choose a Square (R2500)

「区間」と「二次元平面上の点」とはしばしば互いに行き来することで問題が解けたりする!!! 問題へのリンク 問題概要 二次元平面上の 点が与えられる (いずれも 座標が 0 以上の格子点)。各点にはスコア が与えられる。 対角線のうちの一つが 上にあるよ…

AtCoder ABC 106 D - AtCoder Express 2 (400 点)

いろんな方法が考えられそう。 せっかくなので、敢えて、N が大きくても OK な方法でやってみる。hama_du さんの記事を参照。 問題概要 (ABC 106 D) M 個の区間 [l_i, r_i] が与えられる。以下の Q 個のクエリに答えよ: 区間 [p, q] に完全に含まれる区間が…