AT_arc017_4 [ARC017D] ARCたんクッキー

[problemUrl]: https://atcoder.jp/contests/arc017/tasks/arc017_4 私はとあるクッキー工場に勤めている。 この工場では「ARCたんクッキー」というかわいいクッキーを作っている。 この工場には $ N $ 個のARCたんクッキー製造機があり、製造機には $ 1 $ から $ N $ まで番号がついている。製造機ごとに異なるフレーバーが設定されているため、異なる製造機から作られたクッキー同士は区別される。また製造機ごとに一度に生成するクッキーの量が設定されている。製造機は指定された製造数のクッキーを一度に全て生成する。 この度、私が勤めている工場では、$ M $ 日間、工場見学ツアーを実施することになった。それぞれの日には次のいずれかの作業が実行される。 - 見学ツアーを実施する。ツアーではそれぞれの日ごとに定められた、ある連続した番号の製造機をちょうど $ 1 $ 回ずつ稼働させ、それらの製造機が生成したクッキー全てをお土産としてツアー参加者に配る予定である。 - メンテナンスを実施し、それぞれの日ごとに定められた、ある連続した番号の製造機の製造数を一定数増減させる。 工場はとても広く迷子になりやすいので、それぞれのツアー実施日内ではツアー客の定員を固定することになっている。 ここの工場長は割り切れないことを好まず、どの製造機から作られたクッキーもその日参加した全てのツアー客に同数ずつ配らなければ気が済まない。また、ARCたんクッキーの一部を配らない、砕くなどかわいそうなことはしてはならない。つまり、作ったクッキーは全てツアー客に平等に配らなければならない。一方でこの工場の宣伝のため、このような条件を満たしつつできるだけ多くのツアー客を受け入れたいと考えている。 立案者である私は、それぞれのツアー実施日において、$ 1 $ 回あたりのツアーに参加できるツアー客の最大値を求めることになった。しかしながら私は新しいフレーバー開発に忙しい。そこであなたに是非ともこの問題を解いてもらいたい。 入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ a_2 $ … $ a_N $ $ M $ $ t_1 $ $ l_1 $ $ r_1 $ $ t_2 $ $ l_2 $ $ r_2 $ : $ t_M $ $ l_M $ $ r_M $ 1. $ 1 $ 行目には製造機の個数を表す整数 $ N\ (1≦N≦100,000) $ が与えられる。 2. $ 2 $ 行目には $ N $ 個の整数が空白を区切りとして与えられる。 - 整数 $ a_i\ (1≦a_i≦10^9) $ は製造機 $ i\ (1≦i≦N) $ が初期状態で製造するクッキーの個数を表す。 13. $ 3 $ 行目にはツアー及びメンテナンスをする日数を表す整数 $ M\ (1≦M≦100,000) $ が与えられる。 14. $ 4 $ 行目から $ M $ 回、ツアー及びメンテナンスの工程を表す $ 3 $ つの整数が空白を区切りとして与えられる。 - 整数 $ t_i\ (-10^9＜t_i＜10^9) $ は通算 $ i\ (1≦i≦M) $ 日目にする作業を表す。 - $ t_i=0 $ ならその日はツアーを実施する日であること表す。 - $ t_i≠0 $ ならその日はメンテナンスを実施する日であること表す。 - 少なくとも $ 1 $ 回はツアーを実施する日がある。 - 整数 $ l_i,r_i\ (1≦l_i≦r_i≦N) $ は通算 $ i $ 日目にする作業の詳細に関する情報を表す。 - その日がツアーを実施する日なら、番号 $ l_i\ ,\ l_i+1,\ ...\ ,\ r_i $ の製造機をツアー実施時に使用することを表す。 - その日がメンテナンスを実施する日なら、番号 $ l_i\ ,\ l_i+1,\ ...\ ,\ r_i $ の製造機に対し、メンテナンスを実施することを表す。$ t_i $ が正ならそれぞれの製造機の製造数を $ t_i $ ずつ増やし、$ t_i $ が負なら製造数を $ -t_i $ ずつ減らす処理をメンテナンス時に行う。 - 全てのメンテナンスを実施する日において、メンテナンス実施後、どの製造機も製造するクッキーの枚数が $ 1 $ 枚以上 $ 10^9 $ 枚以下である。 この問題には部分点が設定されている。 - 下記の条件を満たすテストケースのみで構成された、$ 30 $ 点分のセットがある。 - 全ての整数 $ i\ (1≦i≦M) $ において、$ t_i≠0 $ なら $ l_i=r_i $ が成立する。 - 上記のセットを含む全てのテストケースに正解することで、残りの $ 70 $ 点を得られる。 ツアーを行う回数を $ T $ とする。このとき出力は $ T $ 行だけ出力せよ。$ i $ 行目には、初日から数えて $ i $ 回目のツアー実施日において、観光客を呼べる人数の最大値を出力せよ。 なお、出力の最後には改行を入れること。 ```

4
6 3 38 49
7
0 1 3
-2 3 3
0 1 3
9 2 2
0 1 2
6 3 3
0 3 4
```

 ```
1
3
6
7
```

- 初期状態における製造機ごとのクッキー製造数は、$ 1 $ 番の製造機から順に $ 6,3,38,49 $ となっている。
- $ 1 $ 日目はツアーを実施する。
- ツアーでは製造機 $ 1,2,3 $ を用いるので、製造されるクッキーの個数は順に $ 6,3,38 $ となる。
- この場合、観光客は $ 1 $ 人しか受け入れられない。

- $ 2 $ 日目はメンテナンスを実施する。
- 製造機 $ 3 $ の製造数を $ 2 $ だけ減らす。メンテナンス後のクッキー製造数は、$ 1 $ 番の製造機から順に $ 6,3,36,49 $ となる。

- $ 3 $ 日目はツアーを実施する。
- ツアーでは製造機 $ 1,2,3 $ を用いるので、製造されるクッキーの個数は順に $ 6,3,36 $ となる。
- この場合、観光客は最大で $ 3 $ 人受け入れられる。

- $ 4 $ 日目はメンテナンスを実施する。
- 製造機 $ 2 $ の製造数を $ 9 $ だけ増やす。メンテナンス後のクッキー製造数は、$ 1 $ 番の製造機から順に $ 6,12,36,49 $ となる。

- $ 5 $ 日目はツアーを実施する。
- ツアーでは製造機 $ 1,2 $ を用いるので、製造されるクッキーの個数は順に $ 6,12 $ となる。
- この場合、観光客は最大で $ 6 $ 人受け入れられる。

- $ 6 $ 日目はメンテナンスを実施する。
- 製造機 $ 3 $ の製造数を $ 6 $ だけ増やす。メンテナンス後のクッキー製造数は、$ 1 $ 番の製造機から順に $ 6,12,42,49 $ となる。

- $ 7 $ 日目はツアーを実施する。
- ツアーでは製造機 $ 3,4 $ を用いるので、製造されるクッキーの個数は順に $ 42,49 $ となる。
- この場合、観光客は最大で $ 7 $ 人受け入れられる。
 

```
3
1 3 17
6
16 1 1
8 2 2
0 1 2
0 2 2
6 2 2
0 1 3
```

 ```
1
11
17
```
                            

N/A

N/A