← 返回题目列表

AtCoder · awc0082_d

D. 走廊门和生命值

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

分数: 400 分

问题陈述

有一条走廊,包括 L 房间水平排列。房间编号从 0 to L - 1 从左到右。

每对相邻的房间之间有一扇门。具体来说,对于每个整数 x 满意 1 \leq x \leq L - 1,有门 x 房间之间 x - 1 和房间 x。走廊两端(房间左侧 0 和房间的右侧 L-1) 是外墙,不能穿过。

这条走廊有 N 配置的安全模式类型。安全图案 i 有模数 A_i,初始值 R_i和时间系数 V_i。在整数时间 t,如果门 x (1 \leq x \leq L - 1) 满足

x \equiv R_i + V_i \cdot t \pmod{A_i}

然后安全模式 i 地方 1 锁上那扇门。多种安全模式可以同时在同一扇门上上锁。

的 重量 门 x 时间 t 定义为当时该门上的锁总数 t.

你被给予 Q 查询。查询中 j,高桥在房间里 S_j 时间 T_j。及时修复锁的状态 T_j (不考虑随时间的变化)并考虑以下事项。

高桥的体力是 P_j。让高桥到达房间 c 来自房间 S_j,他必须穿过之间的所有门 S_j 和 c 按顺序。如果他经过的门的总重量最多为 P_j,然后高桥就可以到达房间 c.

对于每个查询,查找 Takahashi 可以到达的房间数量。注意那个房间 高桥开始的 S_j 也算作可达房间。

约束

  • 1 \leq N \leq 10^5
  • 2 \leq L \leq 10^9
  • 1 \leq Q \leq 10^5
  • N \times Q \leq 3 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 0 \leq R_i \leq A_i - 1
  • 0 \leq V_i \leq A_i - 1
  • 0 \leq T_j \leq 10^9
  • 0 \leq S_j \leq L - 1
  • 0 \leq P_j \leq 10^{14}
  • 所有输入均为整数。

输入

N L Q
A_1 R_1 V_1
A_2 R_2 V_2
:
A_N R_N V_N
T_1 S_1 P_1
T_2 S_2 P_2
:
T_Q S_Q P_Q
  • 第一行包含 N 代表安全图案的数量, L 代表房间数量,以及 Q 代表查询数量,以空格分隔。
  • 以下 N 行给出安全模式信息。
  • 的 (1 + i)第行包含模数 图案的 A_i,初始值 R_i和时间系数 V_i 图案的 i,用空格分隔。
  • 以下 Q 行给出查询信息。
  • 的 (1 + N + j)- 第行包含时间 T_j,房间号 S_j 高桥在哪里,以及体力 P_j 查询 j,用空格分隔。

输出

输出 Q 行。

关于 j第行,输出高桥可到达的房间数以供查询 j.


示例输入 1

2 6 4
2 0 1
3 1 0
0 0 0
0 2 2
1 3 1
2 5 10

示例输出 1

1
6
4
6

示例输入 2

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

示例输出 2

7
2
5
1
8

示例输入 3

8 50 10
7 0 3
11 5 2
13 12 0
6 4 5
17 8 9
10 1 7
9 3 3
25 24 1
0 0 5
1 10 12
2 20 0
5 25 30
10 49 100
12345 17 50
999999 33 7
42 4 20
7 48 1
100 12 1000

示例输出 3

8
27
5
50
50
50
19
30
8
50

示例输入 4

20 100000 15
1000 0 1
99991 12345 67890
2 1 1
3 2 0
97 96 13
1000000000 999999999 0
50000 25000 24999
65536 32768 12345
12345 6789 1111
88888 77777 66666
100 0 99
999 998 997
100000 54321 1234
271828 1828 271
314159 26535 89793
42 17 23
73 0 72
1000000000 0 999999999
1234567 765432 123456
987654321 123456789 98765432
0 0 0
1 99999 10
2 50000 1000
1000 12345 50000
999999999 54321 100000000000000
314159265 999 123456789
271828182 88888 9876543210
42 4242 42
73 7300 7300
1000000000 1 1
555555555 77777 333333
123456789 23456 1000000
987654321 65432 999999999999
80808080 90909 12345678901234
60606060 10101 0

示例输出 4

1
11
2238
68321
100000
100000
100000
96
15474
2
100000
100000
100000
100000
2

示例输入 5

1 2 5
1 0 0
0 0 0
0 0 1
1000000000 1 0
1000000000 1 100000000000000
123 0 100000000000000

示例输出 5

1
2
1
2
2