#P18944. [Mladen Manev 2020 B1] databases / 等差增量与首次达标

[Mladen Manev 2020 B1] databases / 等差增量与首次达标

等差增量与首次达标

有 NN 个数据库,第 ii 个初始存储量为 aia_i,推荐上限为 bib_i。依次进行 MM 次操作。

操作 (l,r,x,y)(l,r,x,y) 给编号 j∈[l,r]j\in[l,r] 的数据库增加 x+(j−l)yx+(j-l)y 的存储量。某个数据库一旦达到或超过其上限,此后对它的操作可以忽略。

对每个数据库,求首次达到或超过上限的操作编号。初始已经达标则输出 00,全部操作后仍未达标则输出 −1-1。

输入格式

第一行 NN;第二行 NN 个整数 aia_i;第三行 NN 个整数 bib_i;第四行 MM。接下来 MM 行,每行为 l,r,x,yl,r,x,y。

输出格式

一行 NN 个整数,依次表示每个数据库首次达标的操作编号,或 0,−10,-1。

数据范围

1≤N≤1051\le N\le10^5,0≤M≤1050\le M\le10^5,0≤ai,bi≤2⋅1090\le a_i,b_i\le2\cdot10^9,1≤l≤r≤N1\le l\le r\le N,0≤x,y≤1050\le x,y\le10^5。累计增量可能超出 32 位整数。

样例

5
5 4 5 2 1
7 7 4 6 3
4
2 4 1 1
1 2 2 0
1 2 2 0
3 4 2 2
2 2 0 4 -1

来源与数据说明

2020 年 Dr. Mladen Manev,B1,原题名 databases。赛事资料,原文题面见附件 statement.pdf。

本题使用官方原始测试数据;评测接口按本站环境适配。总分为 100 分。