EGOI '22 P5 - Data Centers - Olympiads Online Judge

EGOI '22 P5 - Data Centers

View as PDF

Submit solution

All submissions

Best submissions

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

Copy

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

Sample Output

Copy

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.