問題文
确实有 我们有 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