B - How are you? Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Indeed 社には N 人の社員がいます。社員 i (1 ≦ i ≦ N) は時刻 S_i に出社し、時刻 T_i に退社します。各社員は、自分がオフィスにいる間に出社してきた社員に対して "How are you?" と聞きます。すなわち、S_i < S_j < T_i を満たすとき、社員 i は社員 j に対して "How are you?" と聞きます。

あなたは、それぞれの社員が何人に対して "How are you?" と聞くかを計算することにしました。

入力

入力は以下の形式で標準入力から与えられる。

N
S_1 T_1
S_2 T_2
:
S_N T_N
  • 1 行目には、社員の人数を表す整数 N (1 ≦ N ≦ 10^5) が与えられる。
  • 2 行目からの N 行には、社員の出社時刻と退社時刻の情報が与えられる。このうち i 行目には、2 つの整数 S_i, T_i (1 ≦ S_i < T_i ≦ N*2) が空白区切りで与えられる。これは、社員 i が時刻 S_i に出社し、時刻 T_i に退社することを表す。ただし、S_i = S_j または S_i = T_j を満たすような i,j (1 ≦ i < j ≦ N) は存在しないことが保証される。(16:18削除)
  • 与えられる出社時刻と退社時刻は全て相異なる。つまり、S_1,…,S_N,T_1,…,T_N は全て異なる。(16:18追加)

部分点

この問題には部分点が設定されている。

  • N ≦ 2000 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 70 点が与えられる。

出力

出力は N 行からなる。このうち i 行目には、社員 i が "How are you?" と聞く社員の人数を表す 1 つの整数を出力せよ。出力の末尾にも改行を入れること。

入力例1

4
1 6
2 4
3 7
5 8

出力例1

3
1
1
0

この入力例では、

  • 社員 1 は、社員 2 と 社員 3 と社員 4 に対して "How are you?" と聞きます。
  • 社員 2 は、社員 3 に対して "How are you?" と聞きます。
  • 社員 3 は、社員 4 に対して "How are you?" と聞きます。
  • 社員 4 は、誰にも "How are you?" と聞きません。

入力例2

7
5 12
10 11
1 2
6 13
4 7
3 8
9 14

出力例2

3
0
0
2
2
3
1