Mentors (Codeforces 978F)
Tags: Implement, binary search

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.

Input: 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.

Output: 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.

Note: 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.

Sample Inputs:
4 2
10 4 10 15
1 2
4 3

10 4
5 4 1 5 4 3 7 1 2 5
4 6
2 1
10 8
3 5

Sample Outputs:
0 0 1 2

5 4 0 5 3 3 9 0 2 5

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
MOD = 10 ** 9 + 7

def solve():
    (n, k) = map(int, input().split())
    R = list(map(int, input().split()))
    L = []
    for (i, r) in enumerate(R):
        L.append((r, i))
    L.sort()
    prev = -1
    res = [0] * n
    cnt = 0
    for i in range(n):
        if L[i][0] > prev:
            cnt = i
        res[L[i][1]] = cnt
        prev = L[i][0]
    for _ in range(k):
        (a, b) = map(lambda x: int(x) - 1, input().split())
        if R[a] > R[b]:
            res[a] -= 1
        if R[b] > R[a]:
            res[b] -= 1
    print(*res)
if __name__ == '__main__':
    solve()

Solution (Python):
import bisect

def solve():
    (n, k) = (int(x) for x in input().split())
    skills = [int(x) for x in input().split()]
    assert len(skills) == n
    quarrel_student_num = [0] * n
    for _ in range(k):
        (p1, p2) = (int(x) - 1 for x in input().split())
        (skill_1, skill_2) = (skills[p1], skills[p2])
        if skill_1 < skill_2:
            quarrel_student_num[p2] += 1
        elif skill_1 > skill_2:
            quarrel_student_num[p1] += 1
        else:
            pass
    sorted_skill = sorted(skills)
    students = []
    for i in range(n):
        skill_i = skills[i]
        students_num = bisect.bisect_left(sorted_skill, skill_i)
        students.append(students_num - quarrel_student_num[i])
    print(*students)
solve()

Solution (Python):
import bisect
import math
import collections
import sys
from functools import reduce
import decimal
sys.setrecursionlimit(10 ** 9)
decimal.getcontext().rounding = decimal.ROUND_HALF_UP
graphDict = collections.defaultdict
queue = collections.deque

class Graphs:

    def __init__(self):
        self.graph = graphDict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def dfs_utility(self, nodes, visited_nodes):
        visited_nodes.add(nodes)
        for neighbour in self.graph[nodes]:
            if neighbour not in visited_nodes:
                self.dfs_utility(neighbour, visited_nodes)
            else:
                return neighbour

    def dfs(self, node):
        Visited = set()
        self.dfs_utility(node, Visited)

    def bfs(self, node):
        visited = set()
        if node not in visited:
            queue.append(node)
            visited.add(node)
        while queue:
            parent = queue.popleft()
            print(parent)
            for item in self.graph[parent]:
                if item not in visited:
                    queue.append(item)
                    visited.add(item)

def rounding(n):
    return int(decimal.Decimal(f'{n}').to_integral_value())

def factors(n):
    return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def inp():
    return sys.stdin.readline().strip()

def map_inp(v_type):
    return map(v_type, inp().split())

def list_inp(v_type):
    return list(map_inp(v_type))
(n, k) = map_inp(int)
arr = list_inp(int)
arr_copy = sorted(arr)
result = [bisect.bisect_left(arr_copy, item) for item in arr]
for i in range(k):
    (a, b) = map_inp(int)
    if arr[a - 1] < arr[b - 1]:
        result[b - 1] -= 1
    elif arr[a - 1] > arr[b - 1]:
        result[a - 1] -= 1
print(*result)