P9321 [EGOI 2022] Data Centers / 数据中心

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

贡卡软件（贡软）是一家互联网公司，经营许多服务，在全球有 $n$ 个数据中心。每个数据中心都有一些可用的机器。出于安全和冗余的原因，每个服务都有一个或多个副本同时运行。每个副本在一个不同的数据中心运行，并需要一些机器来运行。一个服务的所有副本需要相同数量的机器。 当贡软计划推出一项需要 $c_i$ 个副本，每个副本在 $m$ 台机器上运行的新的服务 $i$ 时，它按照当前可用机器对数据中心降序排序，然后在前 $c_i$ 个数据中心各使用 $m$ 台机器。 请求出在推出 $s$ 个服务后，每个数据中心剩余的机器数量。

第一行两个整数 $n,s$，表示数据中心数和服务数。 第二行 $n$ 个整数 $a_i$，表示每个数据中心初始可用机器数。 接下来 $s$ 行，每行两个整数 $m_i,c_i$，表示需要的机器数、副本数。

一行，**降序排列**的 $n$ 个整数，表示每个数据中心剩余的机器数。

**样例解释** |步骤|剩余机器数|操作| |:-|:-|:-| |初始|$[20,12,10,15,18]$|| |服务 $1$ 前|$[20,18,15,12,10]$|数据中心降序排序| |服务 $1$ 后|$[17,15,12,9,10]$|前 $4$ 个数据中心各使用 $3$ 台机器| |服务 $2$ 前|$[17,15,12,10,9]$|数据中心降序排序| |服务 $2$ 后|$[13,15,12,10,9]$|第 $1$ 个数据中心使用 $4$ 台机器| |服务 $3$ 前|$[15,13,12,10,9]$|数据中心降序排序| |服务 $3$ 后|$[14,12,11,10,9]$|前 $3$ 个数据中心各使用 $1$ 台机器| |服务 $4$ 前|$[14,12,11,10,9]$|数据中心降序排序| |服务 $4$ 后|$[10,8,11,10,9]$|前 $2$ 个数据中心各使用 $4$ 台机器| |结束|$[11,10,10,9,8]$|数据中心降序排序| --- **数据范围** 对于全部数据，$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$，保证任意时刻任意数据中心可用机器数非负。 - 子任务一（$12$ 分）：$n\le 100$，$s=0$。 - 子任务二（$12$ 分）：$n\le 100$，$s\le 10$。 - 子任务三（$9$ 分）：$n\le 5\times 10^4$，$s\le 100$。 - 子任务四（$26$ 分）：$a_i\le 10^3$。 - 子任务五（$18$ 分）：$c_i=1$。 - 子任务六（$23$ 分）：无特殊限制。