P9321 [EGOI 2022] Data Centers / Data Centers

Day 2 Problem A. Translated from [EGOI2022 datacenters](https://stats.egoi.org/media/task_description/2022_datacenters_en.pdf). [](https://creativecommons.org/licenses/by-sa/3.0/)

Gonka Software (Gongsoft) is an Internet company that runs many services and has $n$ data centers around the world. Each data center has some available machines. For security and redundancy reasons, each service runs with one or more replicas at the same time. Each replica runs in a different data center and needs some machines to run. All replicas of one service require the same number of machines. When Gongsoft plans to launch a new service $i$ that needs $c_i$ replicas, with each replica running on $m$ machines, it sorts the data centers in descending order by the number of currently available machines, and then uses $m$ machines in each of the first $c_i$ data centers. Output the number of machines remaining in each data center after launching $s$ services.

The first line contains two integers $n, s$, representing the number of data centers and the number of services. The second line contains $n$ integers $a_i$, representing the initial number of available machines in each data center. The next $s$ lines each contain two integers $m_i, c_i$, representing the required number of machines and the number of replicas.

Output one line with $n$ integers in **descending order**, representing the number of machines remaining in each data center.

**Sample explanation** |Step|Remaining machines|Operation| |:-|:-|:-| |Initial|$[20,12,10,15,18]$|| |Before service $1$|$[20,18,15,12,10]$|Sort data centers in descending order| |After service $1$|$[17,15,12,9,10]$|Use $3$ machines in each of the first $4$ data centers| |Before service $2$|$[17,15,12,10,9]$|Sort data centers in descending order| |After service $2$|$[13,15,12,10,9]$|Use $4$ machines in the $1$st data center| |Before service $3$|$[15,13,12,10,9]$|Sort data centers in descending order| |After service $3$|$[14,12,11,10,9]$|Use $1$ machine in each of the first $3$ data centers| |Before service $4$|$[14,12,11,10,9]$|Sort data centers in descending order| |After service $4$|$[10,8,11,10,9]$|Use $4$ machines in each of the first $2$ data centers| |End|$[11,10,10,9,8]$|Sort data centers in descending order| --- **Constraints** For all testdata, $1\le n\le 10^5$, $0\le s\le 5\times 10^3$, $0\le a_i\le 10^9$, $1\le m_i\le 10^9$, $1\le c_i\le n$. It is guaranteed that at any time, the number of available machines in any data center is non-negative. - Subtask 1 ($12$ points): $n\le 100$, $s=0$. - Subtask 2 ($12$ points): $n\le 100$, $s\le 10$. - Subtask 3 ($9$ points): $n\le 5\times 10^4$, $s\le 100$. - Subtask 4 ($26$ points): $a_i\le 10^3$. - Subtask 5 ($18$ points): $c_i=1$. - Subtask 6 ($23$ points): No additional constraints. Translated by ChatGPT 5