#P18798. [Omi2019] 大都市区域
[Omi2019] 大都市区域
[Omi2019] 大都市区域
题目描述
一座城市由 行、 列的建筑组成。初始时,第 行、第 列的建筑中有 人。
给定正整数 和人口上限 。如果某个连续 行、连续 列组成的正方形区域内,总人口严格大于 ,就称这个区域人口超限。
还有 项人口迁移计划。每项计划由四个整数 描述:在时刻 ,建筑 的人口变化 。其中 表示迁入, 表示迁出。
同一时刻的所有迁移同时发生。 该时刻的人口状态应当在所有这些变化合并后计算,不能把处理其中一项计划时的中间状态视为城市的实际状态。
求最早在哪个时刻存在人口超限的 正方形区域。
如果初始状态就存在超限区域,答案为 ;如果始终不存在,答案为 。
输入格式
第一行包含四个整数 。
接下来 行,每行包含 个整数,表示初始人口矩阵。
下一行包含整数 。
接下来 行,每行包含四个整数 ,描述一项迁移计划。计划不保证按时间顺序给出。
保证实际人口不会因迁出变为负数。人口迁移瞬间完成。
输出格式
输出一个整数,表示最早出现超限区域的时刻。如果始终不超限,输出 -1。
样例输入 1
3 3 2 15
1 2 1
4 3 2
1 5 2
3
2 2 6 4
1 2 10 6
1 3 7 2
样例输出 1
4
样例输入 2
2 2 1 2
1 2
3 4
1
1 1 10 1
样例输出 2
0
样例输入 3
2 2 1 100
99 2
3 4
2
1 1 1 2
1 1 -1 2
样例输出 3
-1
样例说明
样例 1 中,初始四个 正方形的人口分别为 ,均未超限。在时刻 ,右上区域的人口变为 ,恰好等于上限,不算超限。时刻 出现人口大于 的区域。
样例 2 中,初始已有格子的人口大于上限,答案为 。
样例 3 中,同一建筑在时刻 同时迁入和迁出一人,人口没有变化,所以始终不超限。
数据范围与分组
- ,;
- ;
- ;
- ;
- ,;
- ;
- 。
所有人口、正方形人口总和及比较运算应使用足够大的整数类型。
前五组数据只有迁入,即 。各组条件如下:
| 分值 | 额外限制 |
|---|---|
| 7 | |
| 15 | |
| 20 | |
| 23 | 无其他限制,但 |
| 28 | 无额外限制,允许迁出 |