問題一覧 > 通常問題

No.3313 Matryoshka

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 21
作問者 : Cafe1942 / テスター : 👑 loop0919 sclara
お気に入りにしたユーザー ProblemId : 12759 / 自分の提出
問題文最終更新日: 2025-10-24 12:35:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 486 オムニバス (順位表) の他の問題:

Problem Statement

You are given $N$ intervals $(L_i,R_i)$ $(1 \leq i \leq N)$.

Find the number of pairs of integers $(i,j)$ that satisfy all of the following conditions.

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

Constraints

  • $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$ are all distinct
  • All input values are integers

Input

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

Output

Print a newline at the end.

Sample

Sample 1
Input
4
1 8
2 6
4 7
3 5
Output
4

The pairs $(i,j)$ satisfying the conditions are the following 4 pairs: $(1,2),(1,3),(1,4),(2,4)$.

Sample 2
Input
2
2 7
3 5
Output
1
Sample 3
Input
2
3 5
2 7
Output
0

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