【ABC207】 C - Many Segments

問題リンク

解法

$ O(N\log N) $ の解法です。 O(N²)でも間に合うのですが、制約を勘違いしていたので、O(NlogN)の解法を考えました。

まず、開区間のまま考えるとややこしいので全て閉区間に変換することを考えます。
$ l_i≠l_j, r_i=l_j $ の時、 $ [l_i, r_i) $ と $ [l_j, r_j] $ の二つの区間は共通部分を持たないので、端点は大雑把に見ても問題ありません。
開区間の端点に適当に小数を足し引きするのでも問題ありませんが、今回は全ての区間の端点を2倍して、開区間の端点に1を足し引きすることによって全て整数で表せるようにしました。

実装

区間の端点を全て含む配列を準備し、ソートしておきます。
今いくつの区間内にいるかを保持する変数を用意します。
それから、配列の要素を一つずつ取り出し、始点である場合はカウントを一つ増やし、その時点で幾つの区間と重なっているかを答えに加算します。 終点である場合は、カウントを一つ減らします。

int main(){
    ll N;
    cin >> N;
    vector<ll> t(N), l(N), r(N);
    REP (i, N) cin >> t[i] >> l[i] >> r[i];

    vector<pair<ll, ll>> vec;
    REP (i, N) {
        l[i] *= 2;
        r[i] *= 2;
        if (t[i] == 2) r[i]--;
        else if (t[i] == 3) l[i]++;
        else if (t[i] == 4) {
            r[i]--;
            l[i]++;
        }
        vec.push_back({l[i], 0});
        vec.push_back({r[i], 1});
    }

    sort(all(vec));
    ll ans = 0;
    ll cnt = 0;
    REP (i, N * 2) {
        if (vec[i].second) {
            cnt--;
        } else {
            ans += cnt;
            cnt++;
        }
    }

    c(ans)

    return 0;
}

感想

最初、整数で考えてしまい5分ぐらい無駄にしてしまいました。ちゃんと問題は隅々まで読まないとだめですね。 またインクリメントすべきところをデクリメントしてしまい1WAでした。今回みたいな早解き回だと特にミスが痛いので、確認してから提出するように心がけます。