EGOI '22 P5 - Data Centers - DMOJ: Modern Online Judge

EGOI '22 P5 - Data Centers

Points: 10 (partial)

Time limit: 2.0s

Memory limit: 256M

Problem types

GoncaSoft is an internet company that runs many services and has $n$ ~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$ ~i~ that requires $c_i$ ~c_i~ copies, each running on $m_i$ ~m_i~ machines, it sorts the data centers in descending order by their current available machines, and then uses $m_i$ ~m_i~ machines in each of the top $c_i$ ~c_i~ data centers. Please calculate the remaining available machines in the data centers after launching $s$ ~s~ services in a given order.

Input Specification

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

Output Specification

Output one line containing $n$ ~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$ ~1 \leq n \leq 100\,000~ and $0 \leq s \leq 5\,000$ ~0 \leq s \leq 5\,000~.
Each data center has at most $10^9$ ~10^9~ machines initially.
$1 \leq m_i \leq 10^9$ ~1 \leq m_i \leq 10^9~ for each service $i$ ~i~ such that $1 \leq i \leq s$ ~1 \leq i \leq s~.
$1 \leq c_i \leq n$ ~1 \leq c_i \leq n~, for each service $i$ ~i~ such that $1 \leq i \leq s$ ~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$ ~n \leq 100~, $s = 0$ ~s = 0~.
Subtask 2 (12 points): $n \leq 100$ ~n \leq 100~, $s \leq 10$ ~s \leq 10~.
Subtask 3 (9 points): $n \leq 50\,000$ ~n \leq 50\,000~, $s \leq 100$ ~s \leq 100~.
Subtask 4 (26 points): Each data center has initially at most $1\,000$ ~1\,000~ machines.
Subtask 5 (18 points): $c_i = 1$ ~c_i = 1~ for all services from $1$ ~1~ to $s$ ~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 Machines	Operations
Beginning	20 12 10 15 18
Service #1: before launching	20 18 15 12 10	Sort the data centers in descending order.
Service #1: after launching	17 15 12 9 10	Use 3 machines in each of the top 4 data centers.
Service #2: before launching	17 15 12 10 9	Sort the data centers in descending order.
Service #2: after launching	13 15 12 10 9	Use 4 machines in the top data center.
Service #3: before launching	15 13 12 10 9	Sort the data centers in descending order.
Service #3: after launching	14 12 11 10 9	Use 1 machine in each of the top 3 data centers.
Service #4: before launching	14 12 11 10 9	Sort the data centers in descending order.
Service #4: after launching	10 8 11 10 9	Use 4 machines in each of the top 2 data centers.
End	11 10 10 9 8	Sort the data centers in descending order.

Comments

There are no comments at the moment.