← 返回题目列表

AtCoder · indeednow_2015_finalb_b

B. 你好吗?

中文机器翻译题面 查看原题

問題文

确实有 我们有 N 名员工。员工 i (1 ≦ i ≦ N) 是时间 我去 S_i 上班,时间是 我将于 T_i 离开公司。每个员工在办公室的时候都会问走进办公室的员工:“你好吗?”也就是说,S_i < S_j < T_i 当员工 i 是一名员工 问“你好吗?”至 j 。

您决定计算每个员工询问“你好吗?”的人数。


入力

输入将以以下形式从标准输入给出。

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 代表询问“你好吗?”的员工数量 打印 1 整数。还在输出末尾添加换行符。


入力例1

4
1 6
2 4
3 7
5 8

出力例1

3
1
1
0

在此输入示例中,

  • 社員 1 是一名员工 2 和员工 3 和员工 4 。
  • 社員 2 是一名员工 3 。
  • 社員 3 是一名员工 4 。
  • 社員 4 从不问任何人“你好吗?”

入力例2

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

出力例2

3
0
0
2
2
3
1