Algorithm

F. Mentors
time limit per test
3 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/978/problem/F
input
standard input
output
standard output

In BerSoft n� programmers work, the programmer i� is characterized by a skill ri��.

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� (ra>rb)(��>��) 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≤n≤2⋅105(2≤�≤2⋅105, 0≤k≤min(2⋅105,n⋅(n−1)2))0≤�≤min(2⋅105,�⋅(�−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 r1,r2,…,rn�1,�2,…,�� (1≤ri≤109)(1≤��≤109), where ri�� equals to the skill of the i�-th programmer.

Each of the following k� lines contains two distinct integers x�, y� (1≤x,y≤n(1≤�,�≤�, x≠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.

Examples
input
Copy
4 2
10 4 10 15
1 2
4 3
output
Copy
0 0 1 2
input
Copy
10 4
5 4 1 5 4 3 7 1 2 5
4 6
2 1
10 8
3 5
output
Copy
5 4 0 5 3 3 9 0 2 5
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.

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 10;
int n, m, a[N], fr[N], cs[N], sol[N];
vector<int> all;
vector<vector<int> > g;

int main() {
  cin >> n >> m;
  for(int i = 0; i < n; ++i)
    cin >> a[i], all.push_back(a[i]);

  sort(all.begin(), all.end());
  all.resize(unique(all.begin(), all.end()) - all.begin());

  for(int i = 0; i < n; ++i) {
    a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin();
    ++fr[a[i]];
  }

  for(int i = 1; i < N; ++i)
    cs[i] = cs[i - 1] + fr[i - 1];

  g.resize(n);
  for(int i = 0, a, b; i < m; ++i) {
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    swap(a, b);
    g[a].push_back(b);
  }

  for(int i = 0; i < n; ++i) {
    sol[i] = cs[a[i]];

    for(int j = 0; j < g[i].size(); ++j)
      if(a[g[i][j]] < a[i])
        --sol[i];
  }

  for(int i = 0; i < n; ++i)
    cout << sol[i] << ' ';
  cout << endl;

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
4 2
10 4 10 15
1 2
4 3

Output

x
–
+
cmd
0 0 1 2
Advertisements

Demonstration

Codeforces Solution-F. Mentors-Solution in C, C++, Java, Python ,Codeforces Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+