CF978F Mentors

    • 46通过
    • 64提交
  • 题目来源 CodeForces 978F
  • 评测方式 RemoteJudge
  • 标签
  • 难度 普及/提高-
  • 时空限制 3000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    有 $n$ ($ 2 \le n \le 2 \cdot 10^5 $) 个程序员,编号从 $1$ 到 $n$。第 $i$ 个程序员有一个能力值 $r_i$ ($ 1 \le r_i \le 10^9 $)。

    他们当中有 $k$ ($ 0 \le k \le \min(2 \cdot 10^5, \frac{n \cdot (n - 1)}{2}) $) 对程序员 $x$ 和 $y$ ($1 \le x, y \le n$, $ x \not = y $) 会发生口角。$x$ 和 $y$ 是无序的,但是保证不会重复描述某两个人之间的口角。

    规定一个程序员 $a$ 可以成为另一个程序员 $b$ 的导师,仅当 $a$ 的能力值严格大于 $b$ 的能力值 ($ r_a > r_b $),且 $a$, $b$ 之间没有发生口角。

    现在请你求出,对于每一个程序员,他可以成为多少人的导师。

    由 @Tweetuzki 提供翻译

    题目描述

    In BerSoft $ n $ programmers work, the programmer $ i $ is characterized by a skill $ r_i $ .

    A programmer $ a $ can be a mentor of a programmer $ b $ if and only if the skill of the programmer $ a $ is strictly greater than the skill of the programmer $ b $ $ (r_a > r_b) $ and programmers $ a $ and $ b $ are not in a quarrel.

    You are given the skills of each programmers and a list of $ k $ pairs of the programmers, which are in a quarrel (pairs are unordered). For each programmer $ i $ , find the number of programmers, for which the programmer $ i $ can be a mentor.

    输入输出格式

    输入格式:

    The first line contains two integers $ n $ and $ k $ $ (2 \le n \le 2 \cdot 10^5 $ , $ 0 \le k \le \min(2 \cdot 10^5, \frac{n \cdot (n - 1)}{2})) $ — total number of programmers and number of pairs of programmers which are in a quarrel.

    The second line contains a sequence of integers $ r_1, r_2, \dots, r_n $ $ (1 \le r_i \le 10^{9}) $ , where $ r_i $ equals to the skill of the $ i $ -th programmer.

    Each of the following $ k $ lines contains two distinct integers $ x $ , $ y $ $ (1 \le x, y \le n $ , $ x \ne y) $ — pair of programmers in a quarrel. The pairs are unordered, it means that if $ x $ is in a quarrel with $ y $ then $ y $ is in a quarrel with $ x $ . Guaranteed, that for each pair $ (x, y) $ there are no other pairs $ (x, y) $ and $ (y, x) $ in the input.

    输出格式:

    Print $ n $ integers, the $ i $ -th number should be equal to the number of programmers, for which the $ i $ -th programmer can be a mentor. Programmers are numbered in the same order that their skills are given in the input.

    输入输出样例

    输入样例#1: 复制
    4 2
    10 4 10 15
    1 2
    4 3
    
    输出样例#1: 复制
    0 0 1 2 
    
    输入样例#2: 复制
    10 4
    5 4 1 5 4 3 7 1 2 5
    4 6
    2 1
    10 8
    3 5
    
    输出样例#2: 复制
    5 4 0 5 3 3 9 0 2 5 
    

    说明

    In the first example, the first programmer can not be mentor of any other (because only the second programmer has a skill, lower than first programmer skill, but they are in a quarrel). The second programmer can not be mentor of any other programmer, because his skill is minimal among others. The third programmer can be a mentor of the second programmer. The fourth programmer can be a mentor of the first and of the second programmers. He can not be a mentor of the third programmer, because they are in a quarrel.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。