/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 333 点
問題文
高橋君が所属するプログラミングサークルには N 人のメンバーがいます。各メンバーにはレーティングがあり、メンバー i のレーティングは S_i です。
サークルでは近々チーム分けを行うことになり、青木君がメンバー間の関係を調査しています。各メンバーは自分のレーティングがどのくらいかを自己評価しており、メンバー i の自己評価値は C_i です。しかし、自己評価値は必ずしも実際のレーティングと一致するとは限りません。
青木君は、あるメンバーが別のメンバーを「見下している」ペアがどれだけ存在するかを知りたいと考えています。メンバー i がメンバー j を「見下している」とは、以下の条件を すべて 満たすことを指します：
- i \neq j
- メンバー i の自己評価値がメンバー j のレーティングよりも真に大きい（すなわち C_i > S_j）
- メンバー i のレーティングがメンバー j のレーティング以下である（すなわち S_i \leq S_j）
つまり、実力では相手以下であるにもかかわらず、自己評価では相手の実力を超えていると過信している状況です。
「見下している」関係にある順序付きペア (i, j) の総数を求めてください。ここで、メンバー i がメンバー j を見下しているとき (i, j) を 1 つのペアとして数えます。メンバー i がメンバー j を見下しているかどうかと、メンバー j がメンバー i を見下しているかどうかは独立に判定され、(i, j) と (j, i) は区別して数えます。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq S_i \leq 10^9
- 1 \leq C_i \leq 10^9
- 入力はすべて整数である
入力
N S_1 C_1 S_2 C_2 \vdots S_N C_N
1 行目には、メンバーの人数を表す整数 N が与えられる。続く N 行のうち i 行目には、メンバー i のレーティング S_i と自己評価値 C_i が、スペース区切りで与えられる。
出力
「見下している」関係にある順序付きペア (i, j) の総数を 1 行で出力せよ。
入力例 1
4 10 15 12 11 8 20 15 15
出力例 1
4
入力例 2
3 10 5 20 10 30 30
出力例 2
0
入力例 3
10 100 150 120 130 120 200 80 90 200 250 150 150 90 300 300 100 200 199 50 1000
出力例 3
21
入力例 4
30 500 700 300 450 800 600 1000 1200 750 1000 200 900 600 601 900 950 100 1000 400 399 850 2000 650 700 700 650 950 1100 250 260 550 100 150 10000 1000 1000 350 800 450 460 50 51 999 1500 1 1000000000 1000000000 1 720 721 720 1000 880 879 330 1000 660 500 110 111
出力例 4
158
入力例 5
2 1 1000000000 999999999 1
出力例 5
1
Score : 333 pts
Problem Statement
The programming circle that Takahashi belongs to has N members. Each member has a rating, and the rating of member i is S_i.
The circle will soon be dividing into teams, and Aoki is investigating the relationships between members. Each member has a self-assessed value of their own rating, and the self-assessed value of member i is C_i. However, the self-assessed value does not necessarily match the actual rating.
Aoki wants to know how many pairs exist where one member "looks down on" another member. Member i "looks down on" member j if all of the following conditions are satisfied:
- i \neq j
- Member i's self-assessed value is strictly greater than member j's rating (i.e., C_i > S_j)
- Member i's rating is less than or equal to member j's rating (i.e., S_i \leq S_j)
In other words, this is a situation where member i is overconfident, believing their self-assessed ability exceeds the other's actual ability, despite their own actual ability being no greater than the other's.
Find the total number of ordered pairs (i, j) that are in a "looking down on" relationship. Here, when member i looks down on member j, we count (i, j) as one pair. Whether member i looks down on member j and whether member j looks down on member i are determined independently, and (i, j) and (j, i) are counted separately.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq S_i \leq 10^9
- 1 \leq C_i \leq 10^9
- All inputs are integers
Input
N S_1 C_1 S_2 C_2 \vdots S_N C_N
The first line contains an integer N representing the number of members. The i-th of the following N lines contains member i's rating S_i and self-assessed value C_i, separated by a space.
Output
Output the total number of ordered pairs (i, j) in a "looking down on" relationship, on a single line.
Sample Input 1
4 10 15 12 11 8 20 15 15
Sample Output 1
4
Sample Input 2
3 10 5 20 10 30 30
Sample Output 2
0
Sample Input 3
10 100 150 120 130 120 200 80 90 200 250 150 150 90 300 300 100 200 199 50 1000
Sample Output 3
21
Sample Input 4
30 500 700 300 450 800 600 1000 1200 750 1000 200 900 600 601 900 950 100 1000 400 399 850 2000 650 700 700 650 950 1100 250 260 550 100 150 10000 1000 1000 350 800 450 460 50 51 999 1500 1 1000000000 1000000000 1 720 721 720 1000 880 879 330 1000 660 500 110 111
Sample Output 4
158
Sample Input 5
2 1 1000000000 999999999 1
Sample Output 5
1