← 返回题目列表

AtCoder · awc0078_e

E. 公司管理模拟

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

分数: 433 分

问题陈述

高桥制定了一个管理计划,该计划每隔 N 天。在此计划中,每天确定收入、采购成本和人工成本。

当天 管理计划 i (1 \leq i \leq N) ,当日结束,资金增加 A_i - B_i - C_i 日元,其中 A_i 代表收入, B_i 代表采购成本,并且 C_i 代表人工成本。 (如果增加为负数,则资金减少。)

本管理计划返回日 1 日复一日 N,并且相同的计划无限重复。

如果在任何一天结束时资金少于 0 日元(负),该公司被认为已经走了 破产 给出了.

Q 查询。在 j第查询,高桥从当天开始管理 管理计划的 L_j ,他的资金是 S_j 日前一点的日元 L_j的处理发生。

此后,每天按照管理计划的顺序进行管理。即管理计划中的天数按顺序进行 L_j, L_j+1, \ldots, N, 1, 2, \ldots。进行管理的第一天(day 管理计划的 L_j )被算作“管理开始后的第1天”。

对于每个查询,输出自管理开始以来公司第一次破产的日期(当天结束时)。如果公司永远不会破产,无论管理持续多久,产出 0.

约束

  • 1 \leq N
  • 1 \leq Q
  • N + Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_i \leq 10^9
  • 0 \leq C_i \leq 10^9
  • 1 \leq L_j \leq N
  • 0 \leq S_j \leq 10^{12}
  • 所有输入均为整数

输入

N Q
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_N B_N C_N
L_1 S_1
L_2 S_2
\vdots
L_Q S_Q
  • 第一行包含一个整数 N 表示管理计划周期的天数和整数 Q 代表查询数量,以空格分隔。
  • 以下 N 行提供有关管理计划每一天的信息。
  • 的 (1 + i)第行 (1 \leq i \leq N) 包含 A_i 代表当天的收入 i, B_i 代表采购成本,以及 C_i 代表人工成本,用空格分隔。
  • 以下 Q 行提供有关每个查询的信息。
  • 的 (1 + N + j)第行 (1 \leq j \leq Q) 包含 L_j 代表管理开始日 j第一个查询和 S_j 代表初始资金,以空格分隔。

输出

输出 Q 行。

关于 j第行,输出一个整数,代表自管理开始以来公司第一次破产的日期(当天结束时) j第一个查询。如果公司没有破产,输出 0.


示例输入 1

3 5
10 3 2
4 7 5
8 4 3
1 0
1 10
2 7
3 1
2 20

示例输出 1

2
14
1
3
22

示例输入 2

4 4
5 2 3
10 4 1
0 0 0
7 3 2
1 0
2 1
3 100
4 5

示例输出 2

0
0
0
0

示例输入 3

8 8
100 30 20
20 50 10
0 40 30
80 20 20
10 5 5
50 60 20
200 100 50
30 20 40
1 0
2 25
3 100
4 10
5 60
6 5
7 1000
8 15

示例输出 3

3
1
17
8
7
1
269
1

示例输入 4

20 15
1000000000 400000000 300000000
200000000 500000000 100000000
0 600000000 500000000
750000000 250000000 250000000
123456789 123456789 0
900000000 100000000 100000000
10000000 20000000 30000000
500000000 600000000 100000000
1000000000 0 0
0 0 0
300000000 100000000 250000000
800000000 900000000 50000000
450000000 200000000 100000000
100000000 300000000 400000000
600000000 100000000 100000000
700000000 350000000 350000000
1 1000000000 0
999999999 1 1
250000000 250000000 250000000
400000000 100000000 200000000
1 0
1 1000000000000
3 500000000
5 123456789
7 10000000
9 0
10 100
12 800000000
14 1500000000
16 0
18 999999999999
20 300000000
4 700000000
11 250000000
15 50

示例输出 4

2
0
1
19
1
9
2
6
10
2
0
4
0
4
3

示例输入 5

1 5
0 1000000000 1000000000
1 0
1 1
1 1999999999
1 2000000000
1 1000000000000

示例输出 5

1
1
1
2
501