← 返回题目列表

AtCoder · abc417_d

G. 高桥的期待

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

分数: 425 点

问题陈述

高桥将收到 N 呈现。

他有一个参数叫心情,是一个非负整数,每次收到礼物他的心情都会改变。 每个礼物都有三个参数:价值 P,情绪增加 A,情绪下降 B,他的情绪根据这些参数发生如下变化:

  • 当该值 P 收到的礼物大于或等于他的心情,他对礼物很满意,他的心情增加 A.
  • 当该值 P 收到的礼物低于他的心情,他对礼物感到失望,他的心情下降了 B。不过,如果他原本的心情不及 B,它变成 0.

的 i-th (1\le i\le N) 他收到的礼物很有价值 P _ i,情绪增加 A _ i,情绪下降 B _ i.

你被给予 Q 问题,所以请全部回答。 在 i-th (1\le i\le Q) 问题,给你一个非负整数 X _ i,所以回答以下问题:

找到高桥收到全部后的心情 N 当他的情绪最初出现时出现 X _ i.

约束

  • 1\le N\le10000
  • 1\le P _ i\le500\ (1\le i\le N)
  • 1\le A _ i\le500\ (1\le i\le N)
  • 1\le B _ i\le500\ (1\le i\le N)
  • 1\le Q\le5\times10 ^ 5
  • 0\le X _ i\le10 ^ 9\ (1\le i\le Q)
  • 所有输入值均为整数。

输入

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

N
P _ 1 A _ 1 B _ 1
P _ 2 A _ 2 B _ 2
\vdots
P _ N A _ N B _ N
Q
X _ 1
X _ 2
\vdots
X _ Q

输出

输出 Q 行。 的 i- 第行应包含以下问题的答案 i- 第一个问题。


示例输入 1

4
3 1 4
1 5 9
2 6 5
3 5 8
11
0
1
2
3
4
5
6
7
8
9
10

示例输出 1

6
0
0
0
5
6
0
0
0
0
0

当高桥最初的心情是 10,他的情绪变化如下:

  • 值 3 第一份礼物不及他的心情 10,所以他的情绪随着情绪的降低而降低 4,他的心情变成 第二个礼物的 6.
  • 值 1 低于他的心情 6,还有高桥的心情 6 小于心情下降 9,所以他的心情就变成了 0.
  • 值 2 第三个礼物不亚于他的心情 0,所以他的情绪随着情绪的增加而增加 6,他的心情变成 第二个礼物的 6.
  • 值 3 第四个礼物不及他的心情 6,还有高桥的心情 6 小于心情下降 8,所以他的心情就变成了 0.

所以,他最后的心情是 0.


示例输入 2

3
500 500 500
500 500 500
500 500 500
1
1000000000

示例输出 2

999998500

因为高桥的情绪太高,即使收到最好的礼物,他的情绪却不断下降。


示例输入 3

20
124 370 105
280 200 420
425 204 302
435 141 334
212 287 231
262 410 481
227 388 466
222 314 366
307 205 401
226 460 452
336 291 119
302 104 432
478 348 292
246 337 403
102 404 371
368 399 417
291 416 351
236 263 231
170 415 482
101 339 184
20
1162
1394
1695
2501
3008
3298
4053
4093
4330
5199
5302
5869
5875
6332
6567
7483
7562
7725
9723
9845

示例输出 3

339
339
339
339
339
339
339
339
339
339
339
339
339
389
339
643
722
885
2883
3005