章鱼烧变美味机AI (CI翻译)
あなたのたこ焼き屋さんは試食イベントのおかげもあり、とても繁盛しました。
喜んだ高橋社長は全国展開するために、工場で冷凍たこ焼きの生産をすることを決めました。
高橋社長がたこ焼き生産のために買ってきた機械の $1$ つにタコヤキオイシクナールという機械があります。
このタコヤキオイシクナールはトンネルの形をした $N$ 個のボックスからできています。
それぞれのボックスはベルトコンベアで一直線に接続されており、$i(1≦i≦N-1)$ 番目のボックスの出口が $i+1$ 番目のボックスの入り口に繋がっています。
ボックスにはそれぞれ $2$ つの実数 $(a,b)$ が書かれており、美味しさ $r$ のたこ焼きを入れると不思議なことに美味しさが $a×r+b$ に変化します。
多亏了试吃活动，你的章鱼烧店生意十分兴隆。
高兴的高桥社长为了将业务拓展到全国，决定在工厂里生产冷冻章鱼烧。
高桥社长为生产章鱼烧买来的机器中，有 $1$ 台叫作“章鱼烧变美味机”。
这台章鱼烧变美味机由 $N$ 个隧道状的箱体组成。
各个箱体通过传送带连接成一条直线，第 $i(1≦i≦N-1)$ 个箱体的出口与第 $i+1$ 个箱体的入口相连。
每个箱体上都写着 $2$ 个实数 $(a,b)$。将美味度为 $r$ 的章鱼烧放入其中后，它的美味度就会神奇地变为 $a×r+b$。AI (CI翻译)
図 $1$ はタコヤキオイシクナールにたこ焼きを入れた図です。
$(2,1)$ と書かれたボックスを美味しさ $1$ のたこ焼きが通過すると美味しさは $2×1+1=3$ に変化し、さらに次の $(-1,2)$ と書かれたボックスを通過すると $3$ から $-1$ へと美味しさが変化します。
图 $1$ 展示了将章鱼烧放入章鱼烧变美味机的情形。
美味度为 $1$ 的章鱼烧通过写着 $(2,1)$ 的箱体后，美味度会变为 $2×1+1=3$；接着通过下一个写着 $(-1,2)$ 的箱体后，美味度会从 $3$ 变为 $-1$。AI (CI翻译)
図：美味しさ $1$ のたこ焼きを $1$ 個、タコヤキオイシクナールに載せた場合の美味しさの変化
图：将 $1$ 个美味度为 $1$ 的章鱼烧放上章鱼烧变美味机时，美味度的变化AI (CI翻译)
最初ボックスに書かれている数字は全て $(1,0)$ になっておりたこ焼きは $N$ 個のボックスを通過しても美味しさが変化しない状態でした。
そこで、あなたは美味しさ $1$ のたこ焼きを $1$ 個ずつタコヤキオイシクナールに入れてみることにしました。
しかし、ボックスの数字を $M$ 回いたずら好きの高橋社長が変更してしまいました。
美味しさが保障できないと出荷ができません。出来上がったたこ焼きの美味しさの最小値と最大値を求めなさい。
最初，所有箱体上写的数都是 $(1,0)$，因此章鱼烧即使通过全部 $N$ 个箱体，美味度也不会发生变化。
于是，你决定将美味度为 $1$ 的章鱼烧逐个放入章鱼烧变美味机。
然而，喜欢恶作剧的高桥社长将箱体上的数修改了 $M$ 次。
如果无法保证美味度，就不能出货。请求出制作完成的章鱼烧的美味度的最小值和最大值。AI (CI翻译)
なお、タコヤキオイシクナールは同時に $1$ 個分のたこ焼きしか加工することができず、タコヤキオイシクナールが加工を行なっている間に高橋社長が任意のボックスの数字を変更することはありません。
つまり、高橋社長がボックスの数字を変更することができるのは、たこ焼きが出来上がってから次のたこ焼きをあなたがタコヤキオイシクナールのベルトコンベアに乗せるまでの間です。
また、その間に高橋社長が複数のボックスの数字を変更することはないものとする。
另外，章鱼烧变美味机同时只能加工 $1$ 个章鱼烧，在机器加工期间，高桥社长不会修改任何箱体上的数。
也就是说，高桥社长只能在一个章鱼烧制作完成后、你将下一个章鱼烧放上传送带之前，修改箱体上的数。
此外，保证在这段时间内，高桥社长不会修改多个箱体上的数。AI (CI翻译)
N M
p_0 a_0 b_0
p_1 a_1 b_1
:
:
p_{M-1} a_{M-1} b_{M-1}N M
p_0 a_0 b_0
p_1 a_1 b_1
:
:
p_{M-1} a_{M-1} b_{M-1}- 入力は
$M+1$行ある。 $1$行目には、一直線上に接続するボックスの個数を表す整数$N$と高橋社長がボックスの数字を変更した回数を表す整数$M$が空白区切りで与えられる。$2$行目からの$M$行には高橋社長が変更したボックスの内容が与えられる。
- 输入共
$M+1$行。 - 第
$1$行给出两个以空格分隔的整数$N$和$M$，分别表示连接成一条直线的箱体数量，以及高桥社长修改箱体上的数的次数。 - 从第
$2$行开始的$M$行给出高桥社长对箱体所做的修改。
2
2AI (CI翻译)
N
NAI (CI翻译)
M
MAI (CI翻译)
- small (
$50$点) :$1≦N≦1,000,\ 0≦M≦1,000$ - large (
$50$点) :$1≦N≦10^{12},\ 0≦M≦100,000$
- small (
$50$分) :$1≦N≦1,000,\ 0≦M≦1,000$ - large (
$50$分) :$1≦N≦10^{12},\ 0≦M≦100,000$
1
1AI (CI翻译)
2
2AI (CI翻译)
10^{−6}
10^{−6}AI (CI翻译)
1 1
1 1 01 1
1 1 01
11
1- 高橋社長が数字を変更してしまいますが、変更後の数字が元の数字と同じなので美味しさは変化しません。
- したがって、出来上がるたこ焼きの美味しさは全て
$1$になります。
- 虽然高桥社长修改了数，但修改后的数与原来的数相同，因此美味度不会发生变化。
- 所以，制作完成的章鱼烧的美味度全都是
$1$。
3 2
2 -1 1
2 1 0.53 2
2 -1 1
2 1 0.50
1.50
1.5$1$回目のボックスの数字変更後のたこ焼きの美味しさは$(-1)×1+1=0$となります。$2$回目のボックスの数字変更後のたこ焼きの美味しさは$1×1+0.5=1.5$となります。
- 第
$1$次修改箱体上的数后，章鱼烧的美味度为$(-1)×1+1=0$。 - 第
$2$次修改箱体上的数后，章鱼烧的美味度为$1×1+0.5=1.5$。
4 5
1 -0.8 0.5
2 0.72 -0.21
3 1 0.8
4 0.3 0.4142
3 1 0.84 5
1 -0.8 0.5
2 0.72 -0.21
3 1 0.8
4 0.3 0.4142
3 1 0.8-0.426
1-0.426
1$2$回目のボックスの数字変更後のたこ焼きの美味しさは$-0.426$、$4$回目のボックスの数字変更後のたこ焼きの美味しさは$0.5264$になります。- しかし、
$1$回目のボックスの数字を変更前はたこ焼きの美味しさは$1$だったので、美味しさの最大値は$1$になります。
- 第
$2$次修改箱体上的数后，章鱼烧的美味度为$-0.426$；第$4$次修改箱体上的数后，章鱼烧的美味度为$0.5264$。 - 不过，在第
$1$次修改箱体上的数之前，章鱼烧的美味度为$1$，因此美味度的最大值为$1$。
10 10
6 0.5674 -1
3 -0.432 0.1235
8 0.92 0
4 -0.673 0.12578
6 0.986 -0.567
1 0.11111 1
10 0.98765 -0.1234
10 0.18543 -0.16532
9 -0.756 0.54849
2 -1 0.7443610 10
6 0.5674 -1
3 -0.432 0.1235
8 0.92 0
4 -0.673 0.12578
6 0.986 -0.567
1 0.11111 1
10 0.98765 -0.1234
10 0.18543 -0.16532
9 -0.756 0.54849
2 -1 0.74436-1.175043
1-1.175043
1题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。