No.3313 Matryoshka
問題文最終更新日: 2025-10-24 12:35:34
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
Cafe1942