D - ARCたんクッキー Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

私はとあるクッキー工場に勤めている。

この工場では「ARCたんクッキー」というかわいいクッキーを作っている。

この工場には NN 個のARCたんクッキー製造機があり、製造機には 11 から NN まで番号がついている。製造機ごとに異なるフレーバーが設定されているため、異なる製造機から作られたクッキー同士は区別される。また製造機ごとに一度に生成するクッキーの量が設定されている。製造機は指定された製造数のクッキーを一度に全て生成する。

この度、私が勤めている工場では、MM 日間、工場見学ツアーを実施することになった。それぞれの日には次のいずれかの作業が実行される。

  • 見学ツアーを実施する。ツアーではそれぞれの日ごとに定められた、ある連続した番号の製造機をちょうど 11 回ずつ稼働させ、それらの製造機が生成したクッキー全てをお土産としてツアー参加者に配る予定である。
  • メンテナンスを実施し、それぞれの日ごとに定められた、ある連続した番号の製造機の製造数を一定数増減させる。

工場はとても広く迷子になりやすいので、それぞれのツアー実施日内ではツアー客の定員を固定することになっている。

ここの工場長は割り切れないことを好まず、どの製造機から作られたクッキーもその日参加した全てのツアー客に同数ずつ配らなければ気が済まない。また、ARCたんクッキーの一部を配らない、砕くなどかわいそうなことはしてはならない。つまり、作ったクッキーは全てツアー客に平等に配らなければならない。一方でこの工場の宣伝のため、このような条件を満たしつつできるだけ多くのツアー客を受け入れたいと考えている。

立案者である私は、それぞれのツアー実施日において、11 回あたりのツアーに参加できるツアー客の最大値を求めることになった。しかしながら私は新しいフレーバー開発に忙しい。そこであなたに是非ともこの問題を解いてもらいたい。

入力

入力は以下の形式で標準入力から与えられる。 
NN
a1a_1 a2a_2 … aNa_N
MM
t1t_1 l1l_1 r1r_1
t2t_2 l2l_2 r2r_2
:
tMt_M lMl_M rMr_M
  1. 11 行目には製造機の個数を表す整数 N(1≦N≦100,000)N (1≦N≦100,000) が与えられる。
  2. 22 行目には NN 個の整数が空白を区切りとして与えられる。
    • 整数 ai(1≦ai≦109)a_i (1≦a_i≦10^9) は製造機 i(1≦i≦N)i (1≦i≦N) が初期状態で製造するクッキーの個数を表す。
  3. 33 行目にはツアー及びメンテナンスをする日数を表す整数 M(1≦M≦100,000)M (1≦M≦100,000) が与えられる。
  4. 44 行目から MM 回、ツアー及びメンテナンスの工程を表す 33 つの整数が空白を区切りとして与えられる。
    • 整数 ti(−109＜ti＜109)t_i (-10^9＜t_i＜10^9) は通算 i(1≦i≦M)i (1≦i≦M) 日目にする作業を表す。
      • ti=0t_i=0 ならその日はツアーを実施する日であること表す。
      • ti≠0t_i≠0 ならその日はメンテナンスを実施する日であること表す。
      • 少なくとも 11 回はツアーを実施する日がある。
    • 整数 li,ri(1≦li≦ri≦N)l_i,r_i (1≦l_i≦r_i≦N) は通算 ii 日目にする作業の詳細に関する情報を表す。
      • その日がツアーを実施する日なら、番号 li,li+1,...,ril_i , l_i+1, ... , r_i の製造機をツアー実施時に使用することを表す。
      • その日がメンテナンスを実施する日なら、番号 li,li+1,...,ril_i , l_i+1, ... , r_i の製造機に対し、メンテナンスを実施することを表す。tit_i が正ならそれぞれの製造機の製造数を tit_i ずつ増やし、tit_i が負なら製造数を −ti-t_i ずつ減らす処理をメンテナンス時に行う。
    • 全てのメンテナンスを実施する日において、メンテナンス実施後、どの製造機も製造するクッキーの枚数が 11 枚以上 10910^9 枚以下である。

部分点

この問題には部分点が設定されている。
  • 下記の条件を満たすテストケースのみで構成された、3030 点分のセットがある。
    • 全ての整数 i(1≦i≦M)i (1≦i≦M) において、ti≠0t_i≠0 なら li=ril_i=r_i が成立する。
  • 上記のセットを含む全てのテストケースに正解することで、残りの 7070 点を得られる。

出力

ツアーを行う回数を TT とする。このとき出力は TT 行だけ出力せよ。ii 行目には、初日から数えて ii 回目のツアー実施日において、観光客を呼べる人数の最大値を出力せよ。

なお、出力の最後には改行を入れること。

入力例 1

Copy
  1. 4
  2. 6 3 38 49
  3. 7
  4. 0 1 3
  5. -2 3 3
  6. 0 1 3
  7. 9 2 2
  8. 0 1 2
  9. 6 3 3
  10. 0 3 4
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

Copy
  1. 1
  2. 3
  3. 6
  4. 7
1
3
6
7
  • 初期状態における製造機ごとのクッキー製造数は、11 番の製造機から順に 6,3,38,496,3,38,49 となっている。
  • 11 日目はツアーを実施する。
    • ツアーでは製造機 1,2,31,2,3 を用いるので、製造されるクッキーの個数は順に 6,3,386,3,38 となる。
    • この場合、観光客は 11 人しか受け入れられない。
  • 22 日目はメンテナンスを実施する。
    • 製造機 33 の製造数を 22 だけ減らす。メンテナンス後のクッキー製造数は、11 番の製造機から順に 6,3,36,496,3,36,49 となる。
  • 33 日目はツアーを実施する。
    • ツアーでは製造機 1,2,31,2,3 を用いるので、製造されるクッキーの個数は順に 6,3,366,3,36 となる。
    • この場合、観光客は最大で 33 人受け入れられる。
  • 44 日目はメンテナンスを実施する。
    • 製造機 22 の製造数を 99 だけ増やす。メンテナンス後のクッキー製造数は、11 番の製造機から順に 6,12,36,496,12,36,49 となる。
  • 55 日目はツアーを実施する。
    • ツアーでは製造機 1,21,2 を用いるので、製造されるクッキーの個数は順に 6,126,12 となる。
    • この場合、観光客は最大で 66 人受け入れられる。
  • 66 日目はメンテナンスを実施する。
    • 製造機 33 の製造数を 66 だけ増やす。メンテナンス後のクッキー製造数は、11 番の製造機から順に 6,12,42,496,12,42,49 となる。
  • 77 日目はツアーを実施する。
    • ツアーでは製造機 3,43,4 を用いるので、製造されるクッキーの個数は順に 42,4942,49 となる。
    • この場合、観光客は最大で 77 人受け入れられる。

入力例 2

Copy
  1. 3
  2. 1 3 17
  3. 6
  4. 16 1 1
  5. 8 2 2
  6. 0 1 2
  7. 0 2 2
  8. 6 2 2
  9. 0 1 3
3
1 3 17
6
16 1 1
8 2 2
0 1 2
0 2 2
6 2 2
0 1 3

出力例 2

Copy
  1. 1
  2. 11
  3. 17
1
11
17
  • このテストケース内の 44 日目のように、ツアー実施日に稼働させる製造機が 11 つだけのこともある。

2025-04-14 (Mon)
19:32:32 +00:00