D - Corridor Doors and Hit Points Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

横一列に並んだ L 個の部屋からなる通路があります。部屋には左から順に 0 から L - 1 までの番号が付いています。

隣り合う部屋の間には扉があります。具体的には、1 \leq x \leq L - 1 を満たす各整数 x に対して、部屋 x - 1 と部屋 x の間に扉 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 つかけます。1 つの扉に対して複数の警備パターンが同時に錠をかけることもあります。

時刻 t における扉 x の 重さ を、時刻 t にその扉にかけられている錠の総数と定めます。

Q 個の質問が与えられます。質問 j では、時刻 T_j に高橋君が部屋 S_j にいます。時刻 T_j における錠の状態を固定して（時間経過による変化を考えずに）以下を考えます。

高橋君の体力は P_j です。高橋君が部屋 S_j から部屋 c に到達するには、S_j と c の間にあるすべての扉を順に通過する必要があります。このとき通過する扉の重さの合計が P_j 以下であれば、高橋君は部屋 c に到達できます。

各質問について、高橋君が到達できる部屋の個数を求めてください。ただし、高橋君が最初にいる部屋 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
  • 1 行目には、警備パターンの数を表す N 、部屋の個数を表す L 、質問の個数を表す Q がスペース区切りで与えられる。
  • 続く N 行では、警備パターンの情報が与えられる。
  • 1 + i 行目には、パターン i の法 A_i 、初期値 R_i 、時刻係数 V_i がスペース区切りで与えられる。
  • 続く Q 行では、質問の情報が与えられる。
  • 1 + N + j 行目には、質問 j の時刻 T_j 、高橋君のいる部屋番号 S_j 、体力 P_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

Score : 400 pts

Problem Statement

There is a corridor consisting of L rooms arranged in a horizontal row. The rooms are numbered from 0 to L - 1 from left to right.

There is a door between each pair of adjacent rooms. Specifically, for each integer x satisfying 1 \leq x \leq L - 1, there is door x between room x - 1 and room x. Both ends of the corridor (the left side of room 0 and the right side of room L-1) are outer walls and cannot be passed through.

This corridor has N types of security patterns configured. Security pattern i has modulus A_i, initial value R_i, and time coefficient V_i. At integer time t, if door x (1 \leq x \leq L - 1) satisfies

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

then security pattern i places 1 lock on that door. Multiple security patterns may place locks on the same door at the same time.

The weight of door x at time t is defined as the total number of locks placed on that door at time t.

You are given Q queries. In query j, Takahashi is in room S_j at time T_j. Fix the state of the locks at time T_j (without considering changes over time) and consider the following.

Takahashi's stamina is P_j. For Takahashi to reach room c from room S_j, he must pass through all doors between S_j and c in order. If the total weight of the doors he passes through is at most P_j, then Takahashi can reach room c.

For each query, find the number of rooms Takahashi can reach. Note that room S_j where Takahashi starts is also counted as a reachable room.

Constraints

  • 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}
  • All inputs are integers.

Input

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
  • The first line contains N representing the number of security patterns, L representing the number of rooms, and Q representing the number of queries, separated by spaces.
  • The following N lines give the security pattern information.
  • The (1 + i)-th line contains the modulus A_i, initial value R_i, and time coefficient V_i of pattern i, separated by spaces.
  • The following Q lines give the query information.
  • The (1 + N + j)-th line contains the time T_j, the room number S_j where Takahashi is, and the stamina P_j for query j, separated by spaces.

Output

Output Q lines.

On the j-th line, output the number of rooms Takahashi can reach for query j.

Sample Input 1

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

Sample Output 1

1
6
4
6

Sample Input 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

Sample Output 2

7
2
5
1
8

Sample Input 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

Sample Output 3

8
27
5
50
50
50
19
30
8
50

Sample Input 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

Sample Output 4

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

Sample Input 5

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

Sample Output 5

1
2
1
2
2