#P18798. [Omi2019] 大都市区域

[Omi2019] 大都市区域

[Omi2019] 大都市区域

题目描述

一座城市由 NN 行、MM 列的建筑组成。初始时,第 ii 行、第 jj 列的建筑中有 Ai,jA_{i,j} 人。

给定正整数 KK 和人口上限 LIMLIM。如果某个连续 KK 行、连续 KK 列组成的正方形区域内,总人口严格大于 LIMLIM,就称这个区域人口超限。

还有 QQ 项人口迁移计划。每项计划由四个整数 i,j,x,ti,j,x,t 描述:在时刻 tt,建筑 (i,j)(i,j) 的人口变化 xx。其中 x>0x>0 表示迁入,x<0x<0 表示迁出。

同一时刻的所有迁移同时发生。 该时刻的人口状态应当在所有这些变化合并后计算,不能把处理其中一项计划时的中间状态视为城市的实际状态。

求最早在哪个时刻存在人口超限的 K×KK\times K 正方形区域。

如果初始状态就存在超限区域,答案为 00;如果始终不存在,答案为 −1-1。

输入格式

第一行包含四个整数 N,M,K,LIMN,M,K,LIM。

接下来 NN 行,每行包含 MM 个整数,表示初始人口矩阵。

下一行包含整数 QQ。

接下来 QQ 行,每行包含四个整数 i,j,x,ti,j,x,t,描述一项迁移计划。计划不保证按时间顺序给出。

保证实际人口不会因迁出变为负数。人口迁移瞬间完成。

输出格式

输出一个整数,表示最早出现超限区域的时刻。如果始终不超限,输出 -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×22\times2 正方形的人口分别为 10,8,12,1310,8,12,13,均未超限。在时刻 22,右上区域的人口变为 1515,恰好等于上限,不算超限。时刻 44 出现人口大于 1515 的区域。

样例 2 中,初始已有格子的人口大于上限,答案为 00。

样例 3 中,同一建筑在时刻 22 同时迁入和迁出一人,人口没有变化,所以始终不超限。

数据范围与分组

  • 1≤K≤min⁡(N,M)1\le K\le\min(N,M),1≤N,M≤2501\le N,M\le250;
  • 0≤Q≤200000\le Q\le20000;
  • 1≤LIM≤10151\le LIM\le10^{15};
  • 0≤Ai,j≤1060\le A_{i,j}\le10^6;
  • 1≤i≤N1\le i\le N,1≤j≤M1\le j\le M;
  • −106≤x≤106-10^6\le x\le10^6;
  • 1≤t≤1061\le t\le10^6。

所有人口、正方形人口总和及比较运算应使用足够大的整数类型。

前五组数据只有迁入,即 x>0x>0。各组条件如下:

分值 额外限制
7 N,M≤50,Q=0N,M\le50,Q=0
N,M≤50,K=1N,M\le50,K=1
15 K=3K=3
20 Q≤250Q\le250
23 无其他限制,但 x>0x>0
28 无额外限制,允许迁出