{"problem":{"name":"[蓝桥杯 2021 省 AB2] 负载均衡","description":{"content":"有 $n$ 台计算机，第 $i$ 台计算机的运算能力为 $v_{i}$ 。 有一系列的任务被指派到各个计算机上，第 $i$ 个任务在 $a_{i}$ 时刻分配，指定计算机编号为 $b_{i}$, 耗时为 $c_{i}$ 且算力消耗为 $d_{i}$。如果此任务成功分配，将立刻开始运行, 期间持续占用 $b_{i}$ 号计算机 $d_{i}$ 的算力, 持续 $c_{i}$ 秒。 对于每次任务分","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8755"},"statements":[{"statement_type":"Markdown","content":"有 $n$ 台计算机，第 $i$ 台计算机的运算能力为 $v_{i}$ 。\n\n有一系列的任务被指派到各个计算机上，第 $i$ 个任务在 $a_{i}$ 时刻分配，指定计算机编号为 $b_{i}$, 耗时为 $c_{i}$ 且算力消耗为 $d_{i}$。如果此任务成功分配，将立刻开始运行, 期间持续占用 $b_{i}$ 号计算机 $d_{i}$ 的算力, 持续 $c_{i}$ 秒。\n\n对于每次任务分配，如果计算机剩余的运算能力不足则输出 $-1$，并取消这次分配，否则输出分配完这个任务后这台计算机的剩余运算能力。\n\n## Input\n\n输入的第一行包含两个整数 $n, m$，分别表示计算机数目和要分配的任务数。\n\n第二行包含 $n$ 个整数 $v_{1}, v_{2}, \\cdots v_{n}$，分别表示每个计算机的运算能力。\n\n接下来 $m$ 行每行 $4$ 个整数 $a_{i}, b_{i}, c_{i}, d_{i}$，意义如上所述。数据保证 $a_{i}$ 严格递增，即 $a_{i}<a_{i+1}$ 。\n\n## Output\n\n输出 $m$ 行，每行包含一个数，对应每次任务分配的结果。\n\n[samples]\n\n## Note\n\n**【样例说明】**\n\n时刻 $1$，第 $1$ 个任务被分配到第 $1$ 台计算机，耗时为 $5$，这个任务时刻 $6$ 会结束, 占用计算机 $1$ 的算力 $3$。\n\n时刻 $2$，第 $2$ 个任务需要的算力不足，所以分配失败了。\n\n时刻 $3$，第 $1$ 个计算机仍然正在计算第 $1$ 个任务，剩余算力不足 $3$，所以失败。\n\n时刻 $4$，第 $1$ 个计算机仍然正在计算第 $1$ 个任务，但剩余算力足够，分配后剩余算力 $1$。\n\n时刻 $5$，第 $1$ 个计算机仍然正在计算第 $1$，$4$ 个任务，剩余算力不足 $4$，失败。\n\n时刻 $6$，第 $1$ 个计算机仍然正在计算第 $4$ 个任务，剩余算力足够，且恰好用完。\n\n**【评测用例规模与约定】**\n\n对于 $20 \\%$ 的评测用例, $n, m \\leq 200$。\n\n对于 $40 \\%$ 的评测用例, $n, m \\leq 2000$。\n\n对于所有评测用例, $1 \\leq n, m \\leq 2\\times 10^5,1 \\leq a_{i}, c_{i}, d_{i}, v_{i} \\leq 10^{9}, 1 \\leq b_{i} \\leq n$。 \n\n蓝桥杯 2021 第二轮省赛 A 组 H 题（B 组 I 题）。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8755","tags":["模拟","堆","2021","蓝桥杯省赛"],"sample_group":[["2 6\n5 5\n1 1 5 3\n2 2 2 6\n3 1 2 3\n4 1 6 1\n5 1 3 3\n6 1 3 4","2\n-1\n-1\n1\n-1\n0"]],"created_at":"2026-03-03 11:09:25"}}