← 返回题目列表

AtCoder · past20_o

O. 超额查询

中文机器翻译题面 查看原题

问题陈述

有一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N。最初,所有元素 A 是 0。时 i=1,2,\ldots,T,针对 A:

  • 添加 V_i 到每个 A_{L_i},A_{L_i+1},\dots,和 A_{R_i}.

鉴于 Q 查询,按顺序处理。 i第查询描述如下。

  • 给定整数 l_i,r_i,和 x_i,第一次打印 A_{l_i}+A_{l_i+1}+\dots+A_{r_i} 变为 x_i 或更大。如果 A_{l_i}+A_{l_i+1}+\dots+A_{r_i} 小于 x_i 时间 T,打印 -1.

约束

  • 1\leq N\leq 10^5
  • 1\leq T,Q\leq 10^5
  • 1\leq L_i\leq R_i\leq N
  • 1\leq V_i\leq 10^5
  • 1\leq l_i\leq r_i\leq N
  • 1\leq x_i\leq 10^{15}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N T Q
L_1 R_1 V_1 
L_2 R_2 V_2
\vdots
L_T R_T V_T 
l_1 r_1 x_1 
l_2 r_2 x_2
\vdots
l_Q r_Q x_Q

输出

打印 Q 行。 i第行应包含以下问题的答案 i第一个查询。


示例输入 1

6 3 4
3 5 3
1 4 2
2 6 4
2 5 15
3 4 5
6 6 5
1 6 30

示例输出 1

2
1
-1
3

序列 A 转换如下:

  • 时间 1: (0,0,3,3,3,0).
  • 时间 2: (2,2,5,5,3,0).
  • 时间 3: (2,6,9,9,7,4).

每个查询的答案如下。

  • 查询 1:值 第一次或大于 A_2+A_3+A_4+A_5 变为 15 时间 2.
  • 查询 2:值 第一次或大于 A_4+A_5 变为 5 时间 1.
  • 查询 3:值 第一次或大于 A_6 时间 3 小于 5,所以 -1 。
  • 查询 4:值 第一次或大于 A_1+A_2+A_3+A_4+A_5+A_6 变为 30 时间 3.

示例输入 2

100 10 10
54 77 89179
3 23 9999
35 58 58890
38 66 74496
27 49 86313
12 59 86105
23 91 9688
55 74 55468
53 61 36846
4 46 25191
23 48 6659862
6 59 2233031
38 73 9618591
65 86 801679
20 73 3689737
2 19 1320865
27 100 13177888
27 65 762017
80 96 6436
35 66 7954927

示例输出 2

-1
4
9
1
4
-1
-1
1
7
6