問題一覧 > 通常問題

No.3313 Matryoshka

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 16
作問者 : Cafe1942 / テスター : 👑 loop0919 sclara
ProblemId : 12759 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-10-24 12:35:34
コンテストの他の問題:

問題文

$N$ 個の区間 $(L_i,R_i)$ $(1 \leq i \leq N)$が与えられます。

次の条件をすべて満たす整数の組 $(i,j)$ は何組あるか求めてください。

  • $1 \leq i < j \leq N$
  • $L_i < L_j < R_j < R_i$

制約

  • $2 \leq N \leq 5 \times 10^{5}$
  • $1 \leq L_i < R_i \leq 10^6$ $(1 \leq i \leq N)$
  • $L_1 ,R_1 ,L_2 ,R_2 , \dots ,L_N ,R_N$ は全て相異
  • 入力はすべて整数

入力

$N$
$L_1$ $R_1$  
$L_2$ $R_2$  
$\vdots$
$L_N$ $R_N$

出力

最後に改行してください。

サンプル

サンプル1
入力
4
1 8
2 6
4 7
3 5
出力
4

条件を満たす $(i,j)$ の組は、 $(1,2),(1,3),(1,4),(2,4)$ の4組です。

サンプル2
入力
2
2 7
3 5
出力
1
サンプル3
入力
2
3 5
2 7
出力
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。