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