EGOI '22 P5 - Data Centers

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

GoncaSoft is an internet company that runs many services and has n data centers worldwide. Each data center has a number of available machines. For security and redundancy reasons, one or more copies of each service are running at the same time. Each copy runs in a separate data center, and requires a number of machines to run on. All the copies of a given service require the same number of machines.

When GoncaSoft plans to launch a new service i that requires c_i copies, each running on m_i machines, it sorts the data centers in descending order by their current available machines, and then uses m_i machines in each of the top c_i data centers. Please calculate the remaining available machines in the data centers after launching s services in a given order.

Input Specification

The first line of the input contains two space-separated integers n and s, representing the number of data centers GoncaSoft has and the number of new services GoncaSoft wants to launch. The next line contains n space-separated integers, representing the number of available machines in each of the n data centers, before any services are launched. The next s lines describe the services that will be launched: the i-th line contains two space-separated integers m_i and c_i, representing the number of machines and the number of copies the i-th service requires.

Output Specification

Output one line containing n space-separated integers sorted in descending order, representing the number of remaining available machines in the data centers after all services have launched.

Constraints

  • 1 \leq n \leq 100\,000 and 0 \leq s \leq 5\,000.
  • Each data center has at most 10^9 machines initially.
  • 1 \leq m_i \leq 10^9 for each service i such that 1 \leq i \leq s.
  • 1 \leq c_i \leq n, for each service i such that 1 \leq i \leq s. The data centers will always have enough machines for the new services.

Subtasks

  • Subtask 1 (12 points): n \leq 100, s = 0.
  • Subtask 2 (12 points): n \leq 100, s \leq 10.
  • Subtask 3 (9 points): n \leq 50\,000, s \leq 100.
  • Subtask 4 (26 points): Each data center has initially at most 1\,000 machines.
  • Subtask 5 (18 points): c_i = 1 for all services from 1 to s.
  • Subtask 6 (23 points): No further constraints.

Sample Input

5 4
20 12 10 15 18
3 4
4 1
1 3
4 2

Sample Output

11 10 10 9 8

Explanation

Step Available MachinesOperations
Beginning20 12 10 15 18
Service #1: before launching20 18 15 12 10Sort the data centers in descending order.
Service #1: after launching17 15 12 9 10Use 3 machines in each of the top 4 data centers.
Service #2: before launching17 15 12 10 9Sort the data centers in descending order.
Service #2: after launching13 15 12 10 9Use 4 machines in the top data center.
Service #3: before launching15 13 12 10 9Sort the data centers in descending order.
Service #3: after launching14 12 11 10 9Use 1 machine in each of the top 3 data centers.
Service #4: before launching14 12 11 10 9Sort the data centers in descending order.
Service #4: after launching10 8 11 10 9Use 4 machines in each of the top 2 data centers.
End11 10 10 9 8Sort the data centers in descending order.

Comments

There are no comments at the moment.