すべての区間の組について共通部分を持つかどうか調べると \(O(N^2)\) 時間かかり，実行時間制限に間に合いません．適切なアルゴリズムを用いて高速化する必要があります．

ここで，共通部分を持つ区間の組を数える代わりに，共通部分を持たない区間の組の個数 \(x\) を求めて \(N(N-1)/2\) から引くことで答えを求めることにします（これは，「余事象を考える」という典型的な考え方です）．

区間 \(i\) の左にあって区間 \(i\) と共通部分を持たない区間は， \(r_j < l_i\) を満たす区間 \(j\) です．よって，各 \(i=1,2,\dots,N\) について， \(r_j < l_i\) なる \(j\) の個数を求めると，その総和が求める \(x\) です．

これは，尺取り法というテクニックによって高速に計算することができます． まず，数列 \(L,R\) を，それぞれ \((l_1,l_2,\dots,l_N),(r_1,r_2,\dots,r_N)\) を昇順に並べ替えたものとします． \(i=1,2,\dots,N\) の順番に，\(R_j < L_i\) を満たす \(j\) の個数 \(c_i\) を求めましょう．\(R\) が昇順に並んでいることから，\(R_j < L_i\) を満たす \(j\) は \(1,2,\dots,c_i\) です． よって，次のようなアルゴリズムが考えられます．

1. \(i=1,2,\dots,N\) の順番に，次の操作を行う．
   1. \(c \leftarrow 1\) とする．
   2. \(R_c < L_i\) である間， \(c \leftarrow c + 1\) とする．
   3. \(c_i \leftarrow c-1\) とする．

このアルゴリズムは，各 \(i\) についてステップ 1.2 が最大で \(N-1\) 回実行されるため，依然として全体で \(O(N^2)\) 時間かかってしまいます．高速化にはさらなる考察が必要です．

ここで，重要な性質として， \(L\) が昇順に並んでいることから \(c_i\leq c_{i+1}\) が各 \(i=1,2,\dots,N-1\) について成り立ちます なぜならば， \(R_{c_i} < L_i \leq L_{i+1}\) より， \(R\) の少なくとも \(c_i\) 個は \(L_{i+1}\) より小さいからです．

よって， \(c_{i+1}\) を求めるときに， \(R_1,R_2,\dots,\) と \(1\) から順番に調べるのではなく， \(R_{c_i},R_{c_i+1},\dots\) というように，探索を \(c_i\) からはじめても良いです．つまり，先程のアルゴリズムを次のように変更することができます．

1. \(c \leftarrow 1\) とする．
2. \(i=1,2,\dots,N\) の順番に，次の操作を行う．
   1. \(R_c < L_i\) である間， \(c \leftarrow c + 1\) とする．
   2. \(c_i \leftarrow c-1\) とする．

このアルゴリズムの計算量を調べましょう．ステップ 2.1 が実行されるたびに， \(c\) は \(1\) 増えます．また， \(c\) はたかだか \(N\) です．よって，ステップ 2.1 はプログラム全体でたかだか \(N-1\) 回しか実行されません．よって，このアルゴリズムの時間計算量は（ソートを除いて）\(O(N)\) であり，高速に動作します．

実装例 (Python)

N = int(input())
l = [0] * N
r = [0] * N
for i in range(N):
    l[i], r[i] = map(int, input().split())
l.sort()
r.sort()

ans = N * (N - 1) // 2
j = 0
for i in range(N):
    while r[j] < l[i]:
        j += 1
    ans -= j
print(ans)