P1083 [NOIP 2012 提高组] 借教室

难度： 普及/提高−
算法标签： 二分答案、差分、前缀和
来源： 洛谷 P1083

题目背景

本题围绕“[NOIP 2012 提高组] 借教室”所描述的场景展开。学校未来 $n$ 天每天有 $r_i$ 间教室可用。

下面的题面采用非逐字重述方式整理，但保留原题中的全部判定条件、边界含义、输入输出要求与特殊约定。

题目描述

学校未来 $n$ 天每天有 $r_i$ 间教室可用。共有 $m$ 份按顺序处理的订单，第 $j$ 份要求在第 $s_j$ 到 $t_j$ 天（含两端）每天使用 $d_j$ 间。订单按先到先得处理；一旦某份订单加入后有任意一天需求超过可用量，就停止并通知该订单申请人。请判断所有订单能否满足；若不能，找出第一份无法满足的订单。

完整规则与任务要求

处理本题时，必须同时满足下列全部要求，不能只实现其中一部分：

• 学校未来 $n$ 天每天有 $r_i$ 间教室可用。
• 共有 $m$ 份按顺序处理的订单，第 $j$ 份要求在第 $s_j$ 到 $t_j$ 天（含两端）每天使用 $d_j$ 间。
• 订单按先到先得处理；。
• 一旦某份订单加入后有任意一天需求超过可用量，就停止并通知该订单申请人。
• 请判断所有订单能否满足；。
• 若不能，找出第一份无法满足的订单。
• 订单严格按输入顺序处理，前面的订单优先。
• 只要订单覆盖区间内有任意一天教室不足，该订单就无法满足。
• 遇到第一份无法满足的订单后立即停止，并输出其编号。

程序应完整读取“输入格式”中规定的所有数据，并严格按照“输出格式”给出结果。题目中的区间端点、编号起点、排序优先级、同分处理、空结构处理、取模方式和特殊字符串，均以本题面明确写出的规则为准。

所有算法还必须覆盖“数据范围”中的最小规模、最大规模及边界情况，不能只针对样例或小数据。

输入格式

第一行两个整数 $n,m$。第二行 $n$ 个整数 $r_i$。接下来 $m$ 行每行三个整数 $d_j,s_j,t_j$。

输出格式

若全部可满足，输出一行 0。否则输出两行：第一行 -1，第二行第一份无法满足的订单编号。

输入输出样例

样例 1

4 3
2 5 4 3
2 1 3
3 2 4
1 1 4

-1
2

样例说明

处理第一份订单后，第二份订单覆盖的某一天剩余教室不足，因此第一份无法满足的订单编号为 $2$。

数据范围

$1\le n,m\le10^6$，$0\le r_i,d_j\le10^9$，$1\le s_j\le t_j\le n$。

边界与子任务说明

• 测试数据可能覆盖题面允许的最小值、最大值、重复值、空结果、无解或极端结构等边界情形。
• 若原题未额外列出分档子任务，则所有测试点统一遵守上述完整数据范围；若题面已经列出比例或分档条件，则这些条件均应视为题面的一部分。
• 不能根据公开样例推断未写出的额外限制。

本题面依据洛谷 P1083 的公开题目信息重新整理，为内容完整的非逐字重述版。