← 返回题目列表

AtCoder · awc0079_c

C. 周期性追逐

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

分数: 366 分

问题陈述

在一条数轴上,高桥和青木正在玩追逐游戏。青木朝正方向跑去,高桥追了上去。

它们的速度随时间变化 N 秒。最初,一个 速度表 给出 长度 N ,其中 i第一个条目 (1 \leq i \leq N) 指定 Aoki 的速度 A_i 和高桥的速度 B_i.

时间从 0。对于每个非负整数 s,期间 1- 时间的秒间隔 使用速度表的 s 到时间 s + 1, i = (s \bmod N) + 1第条目。也就是说,在这期间 1 第二,青木出招 A_i 和高桥的举动 B_i 正方向。此对应关系每次都会以相同的顺序重复 N 秒。

你处理 Q 按顺序查询。有两种类型的查询:

  • 1 i a b:更改 i速度表的第一项,使 Aoki 的速度变为 a 高桥的速度变成 b.
  • 2 d:根据当前速度表,回答以下问题。假设在某个时间 0,高桥在坐标处 0 和青木在坐标 d,求高桥追上青木的最小非负整数时间。如果他永远追不上,则输出 -1.

在这里, 追赶 表示在某个非负整数时间 t,高桥的坐标大于或等于青木的坐标。仅在整数次时执行检查;不考虑中间两者的位置。

每个 2 查询是独立的,两者的位置不会结转到下一个查询。另一方面,对速度表所做的更改 1 查询将延续到所有后续查询。

约束

  • 1 \leq N \leq 3000
  • 1 \leq Q \leq 10^5
  • NQ \leq 10^7
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_i \leq 10^9
  • 对于 1 查询: 1 \leq i \leq N, 0 \leq a \leq 10^9, 0 \leq b \leq 10^9
  • 对于 2 查询: 1 \leq d \leq 10^{15}
  • 至少有一个 2 查询
  • 所有输入值均为整数

输入

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
query_1
query_2
\vdots
query_Q

第一行给出句点 N 和查询数量 Q。以下 N 行给出 A_i 和 B_i 上 i第行。以下 Q 行给出以下格式的查询 1 i a b or 2 d。每行上的值均以空格分隔。

输出

对于每个 2 查询,一行输出高桥追上青木的最小非负整数时间。如果他永远追不上,则输出 -1.


示例输入 1

3 5
2 5
4 3
1 2
2 1
2 4
1 2 0 6
2 8
2 20

示例输出 1

1
4
2
6

示例输入 2

3 5
2 1
0 2
1 0
2 2
2 1
1 2 5 5
2 1
2 100

示例输出 2

-1
2
-1
-1

示例输入 3

8 14
5 8
7 4
3 6
10 2
0 5
4 4
6 9
2 1
2 3
2 10
1 4 1 12
2 15
1 8 5 20
2 30
1 2 10 10
2 7
2 100
1 5 8 0
2 12
1 4 0 0
2 25
2 1

示例输出 3

1
33
5
8
4
21
4
16
1

示例输入 4

20 30
100 150
80 60
0 200
300 100
50 50
20 70
90 30
10 110
400 0
0 0
15 45
60 90
120 80
5 205
700 900
1000 500
30 31
45 40
200 250
75 125
2 1000
2 100000
1 9 0 1000
2 5000
1 16 100 1000
2 20000
1 4 0 0
1 7 0 300
2 12345
2 999999999999999
1 1 1000 0
2 100
1 10 0 1000000000
2 1000000000
1 10 1000000000 0
2 1000000000
1 15 900 700
1 20 125 75
2 7777
2 42
1 2 0 0
1 3 500 100
2 314159
1 18 0 100
2 271828
1 5 0 0
2 1000000000000000
1 12 1000000000 1000000000
2 600
2 600000

示例输出 4

-1
-1
89
156
80
6459948320415
9
10
-1
-1
9
-1
-1
-1
-1
-1

示例输入 5

1 8
1000000000 0
2 1
1 1 0 0
2 1
1 1 0 1000000000
2 1000000000000000
2 1
1 1 1000000000 1000000000
2 1

示例输出 5

-1
-1
1000000
1
-1