Many Segments [AtCoder Beginner Contest 207 C]

https://atcoder.jp/contests/abc207/tasks/abc207_c

解説

https://atcoder.jp/contests/abc207/submissions/23803776

区間をすべて[l,r)の半開区間に変換して比較をしよう。

[l,r] -> [l,r + 0.5)
[l,r) -> [l,r)
(l,r] -> [l + 0.5, r + 0.5)
(l,r) -> [l + 0.5, r)

という風に中間をうまく利用することで区間を変換していく。
だが、これだと小数が入ってしまうので、すべての座標を2倍にして考えることにする。
今回考慮されるのは包含関係であり、すべての座標を2倍にしても包含関係には影響しない。
なので、以下のように変換する

[l,r] -> [2l,2r + 1)
[l,r) -> [2l,2r)
(l,r] -> [2l + 1, 2r + 1)
(l,r) -> [2l + 1, 2r)

これですべて同じ様式の区間になったので、全ての(i,j)の組について包含関係を判定して、包含しているならカウントしていけばいい。
[a,b)と[c,d)を合成した区間は[max(a,c), min(b,d))となるので、このルールで合成して、要素が存在する、つまり、max(a,c)＜min(b,d)であるかを判定すればいい。

int N, A[2010], B[2010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int t, l, r; cin >> t >> l >> r;
        if (t == 1) A[i] = l * 2, B[i] = r * 2 + 1;
        else if (t == 2) A[i] = l * 2, B[i] = r * 2;
        else if (t == 3) A[i] = l * 2 + 1, B[i] = r * 2 + 1;
        else A[i] = l * 2 + 1, B[i] = r * 2;
    }

    int ans = 0;
    rep(i, 0, N) rep(j, i + 1, N) {
        int AA = max(A[i], A[j]);
        int BB = min(B[i], B[j]);
        if (AA < BB) ans++;
    }
    cout << ans << endl;
}