{"problem":{"name":"[EGOI 2022] Data Centers / 数据中心","description":{"content":"贡卡软件（贡软）是一家互联网公司，经营许多服务，在全球有 $n$ 个数据中心。每个数据中心都有一些可用的机器。出于安全和冗余的原因，每个服务都有一个或多个副本同时运行。每个副本在一个不同的数据中心运行，并需要一些机器来运行。一个服务的所有副本需要相同数量的机器。 当贡软计划推出一项需要 $c_i$ 个副本，每个副本在 $m$ 台机器上运行的新的服务 $i$ 时，它按照当前可用机器对数据中心降序排","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9321"},"statements":[{"statement_type":"Markdown","content":"贡卡软件（贡软）是一家互联网公司，经营许多服务，在全球有 $n$ 个数据中心。每个数据中心都有一些可用的机器。出于安全和冗余的原因，每个服务都有一个或多个副本同时运行。每个副本在一个不同的数据中心运行，并需要一些机器来运行。一个服务的所有副本需要相同数量的机器。\n\n当贡软计划推出一项需要 $c_i$ 个副本，每个副本在 $m$ 台机器上运行的新的服务 $i$ 时，它按照当前可用机器对数据中心降序排序，然后在前 $c_i$ 个数据中心各使用 $m$ 台机器。\n\n请求出在推出 $s$ 个服务后，每个数据中心剩余的机器数量。\n\n## Input\n\n第一行两个整数 $n,s$，表示数据中心数和服务数。\n\n第二行 $n$ 个整数 $a_i$，表示每个数据中心初始可用机器数。\n\n接下来 $s$ 行，每行两个整数 $m_i,c_i$，表示需要的机器数、副本数。\n\n## Output\n\n一行，**降序排列**的 $n$ 个整数，表示每个数据中心剩余的机器数。\n\n[samples]\n\n## Background\n\nDay 2 Problem A.\n\n题面译自 [EGOI2022 datacenters](https://stats.egoi.org/media/task_description/2022_datacenters_en.pdf)。\n\n[![CC BY-SA 3.0](https://licensebuttons.net/l/by-sa/3.0/80x15.png)](https://creativecommons.org/licenses/by-sa/3.0/)\n\n## Note\n\n**样例解释**\n\n|步骤|剩余机器数|操作|\n|:-|:-|:-|\n|初始|$[20,12,10,15,18]$||\n|服务 $1$ 前|$[20,18,15,12,10]$|数据中心降序排序|\n|服务 $1$ 后|$[17,15,12,9,10]$|前 $4$ 个数据中心各使用 $3$ 台机器|\n|服务 $2$ 前|$[17,15,12,10,9]$|数据中心降序排序|\n|服务 $2$ 后|$[13,15,12,10,9]$|第 $1$ 个数据中心使用 $4$ 台机器|\n|服务 $3$ 前|$[15,13,12,10,9]$|数据中心降序排序|\n|服务 $3$ 后|$[14,12,11,10,9]$|前 $3$ 个数据中心各使用 $1$ 台机器|\n|服务 $4$ 前|$[14,12,11,10,9]$|数据中心降序排序|\n|服务 $4$ 后|$[10,8,11,10,9]$|前 $2$ 个数据中心各使用 $4$ 台机器|\n|结束|$[11,10,10,9,8]$|数据中心降序排序|\n\n---\n\n**数据范围**\n\n对于全部数据，$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$，保证任意时刻任意数据中心可用机器数非负。\n\n- 子任务一（$12$ 分）：$n\\le 100$，$s=0$。\n- 子任务二（$12$ 分）：$n\\le 100$，$s\\le 10$。\n- 子任务三（$9$ 分）：$n\\le 5\\times 10^4$，$s\\le 100$。\n- 子任务四（$26$ 分）：$a_i\\le 10^3$。\n- 子任务五（$18$ 分）：$c_i=1$。\n- 子任务六（$23$ 分）：无特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9321","tags":["2022","O2优化","EGOI（欧洲/女生）"],"sample_group":[["5 4\n20 12 10 15 18\n3 4\n4 1\n1 3\n4 2","11 10 10 9 8"]],"created_at":"2026-03-03 11:09:25"}}