Problem:


F - Acceleration of Network

  

インターネットと言う広大な海は少しずつ黒く塗りつぶされていった。

ボットの反乱、DDOS攻撃の嵐、ウィルスの蔓延、

何度も何度も繰り返されたクラッカーとの戦争で、人もインターネットもボロボロになった。

人の手では、インターネットはどうにもならない。

だから人は、とんでもない時間をかけて

インターネットを復旧できる「少女」を造った。

少女は、インターネットの手当をはじめた。

果てしなく広いインターネットの世界をどうにかしようと頑張った。

まだ少女ひとりでは撚り対線を織る事くらいしかできないけど、

長い長い時がすぎてインターネットが少し復旧すれば、

みんなと一緒に頑張れるだろうという期待をこめて。

問題文

少女はかつてインターネットに存在した N 個のサービスを復旧するために日々頑張っている．
現在を 0 日目とする．
インターネットがどの程度復旧しているかを復旧度という指標で表し，現在の復旧度は 0 であるとする．
少女は毎日作業をし，復旧度を 1 日につき 1 ずつ上げていく．
任意のまだ復旧していないサービス i は，復旧度が wi 以上になると自動的に復旧する．
サービス i が復旧すると，みんなが手伝ってくれることにより，復旧した次の日から xi 日間だけ作業がはかどり，復旧度の増加が加速する．
サービスには 3 つの種類があり，種類によって復旧度がどの程度増加するのかが異なる．
サービスの種類を 0, 1, 2 の番号で表すとする．
サービス i の種類を ti (&isin; {0, 1, 2}) とすると，
サービス i が復旧してから d-1 日目から d 日目にかけて (1 ≤ d ≤ xi)，
ti=0 の場合は 1，
ti=1 の場合は d，
そして ti=2 の場合は d2 だけ，少女の作業とは別に復旧度が増加する．
また，同時に複数のサービスが復旧している場合，それぞれのサービスは独立に並行して復旧度を増加させる．

少女はサービスが復旧するまでにとんでもない時間がかかると思ったので，現在から何日目にサービスが復旧するか調べることにした．
またある日にち yj に復旧度がいくらになっているかも気になったので，それも Q 日分だけ調べることにした．

入力形式

入力は以下の形式で与えられる．

N Q
w1 t1 x1
...
wN tN xN
y1
...
yQ

出力形式

最初に N 行出力し，i 行目にはサービス i の復旧する日にちを出力せよ．次に Q  行出力し，j 行目には yj 日目に復旧度がいくらになっているかを出力せよ．
サービスが復旧する日にちが 3,652,425 を超える場合はMany years laterと出力せよ．

制約

0 ≤ N ≤ 105

1 ≤ Q ≤ 105

0 ≤ wi < 260

wi ≤ wi+1 (1 ≤ i < N)

ti &isin; {0, 1, 2}

1 ≤ xi ≤ 104

0 ≤ yj ≤ 3,652,425

yj < yj+1 (1 ≤ j < Q)

入力値はすべて整数である．

この問題の判定には，15 点分のテストケースのグループが設定されている．このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす．

N,Q,wi,yj ≤ 1,000

注意

0 日目の復旧度は 0 である．

wi=0 の時，サービス i は 0 日目に復旧する．

入出力例

入力例1

3 11
1 0 2
4 1 3
7 2 4
0
1
2
3
4
5
6
7
8
9
10

出力例1

1
3
4
0
1
3
5
7
11
19
29
46
47
48

入力例2

5 5
10000 0 20
10000 1 30
10000 0 40
10000 2 70
30000 2 10000
5000
10000
15000
20000
25000

出力例2

10000
10000
10000
10000
10039
5000
10000
40711690801
329498273301
333383477320

入力例3

2 2
3652425 0 1
3652426 2 10000
3652424
3652425

出力例3

3652425
Many years later
3652424
3652425

2つ目のサービスは復旧する日にちが 3,652,425 日を超えているのでMany years laterと出力している．

Writer : 森槙悟
Tester : 田村和範



Sample input:
3 11
1 0 2
4 1 3
7 2 4
0
1
2
3
4
5
6
7
8
9
10


Sample output:
1
3
4
0
1
3
5
7
11
19
29
46
47
48

Submission status: Accepted

Solution code:
from collections import defaultdict
MAX = 3652425
n, q = map(int, input().split())
lst = [tuple(map(int, input().split())) for _ in range(n)]
restor = [0] * (MAX + 10010)
t0s = [0] * (MAX + 10010)
t1s = [0] * (MAX + 10010)
t2s = [0] * (MAX + 10010)
t3s = [0] * (MAX + 10010)
t1_cnt_save = defaultdict(int)
t3_cnt_save = defaultdict(int)
t1_cnt = 0
t3_cnt = 0
index = 0
for i, line in enumerate(lst):
  w, t ,x = line
  while index < MAX and w > restor[index]:
    t0s[index + 1] += t0s[index]
    t1_cnt -= t1_cnt_save[index + 1]
    t1s[index + 1] += t1s[index] + t1_cnt
    t3_cnt -= t3_cnt_save[index + 1]
    t3s[index + 1] += t3s[index] + 2 * t3_cnt
    t2s[index + 1] += t2s[index] + t3s[index + 1]
    restor[index + 1] = restor[index] + 1 + t0s[index] + t1s[index] + t2s[index]
    index += 1
  if w <= restor[index]:
    print(index)
    if t == 0:
      t0s[index] += 1
      t0s[index + x] -= 1
    elif t == 1:
      t1_cnt += 1
      t1_cnt_save[index + x] += 1
      t1s[index] += 1
      t1s[index + x] -= x
    elif t == 2:
      t3_cnt += 1
      t3_cnt_save[index + x] += 1
      t3s[index] += 1
      t3s[index + x] -= x * 2 - 1
      t2s[index] += 1
      t2s[index + x] -= x ** 2
  else:print("Many years later")

for _ in range(q):
  y = int(input())
  while index < y:
    t0s[index + 1] += t0s[index]
    t1_cnt -= t1_cnt_save[index + 1]
    t1s[index + 1] += t1s[index] + t1_cnt
    t3_cnt -= t3_cnt_save[index + 1]
    t3s[index + 1] += t3s[index] + 2 * t3_cnt
    t2s[index + 1] += t2s[index] + t3s[index + 1]
    restor[index + 1] = restor[index] + 1 + t0s[index] + t1s[index] + t2s[index]
    index += 1
  print(restor[y])

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
  MAX = 3652425
  n, q = map(int, input().split())
  lst = [tuple(map(int, input().split())) for _ in range(n)]
  restore = [0] * (MAX + 10010)
  t0s = [0] * (MAX + 10010)
  t1s = [0] * (MAX + 10010)
  t2s = [0] * (MAX + 10010)
  t3s = [0] * (MAX + 10010)
  t1_cnt_save = defaultdict(int)
  t3_cnt_save = defaultdict(int)
  t1_cnt = 0
  t3_cnt = 0
  day = 0
  for i, line in enumerate(lst):
    w, t ,x = line
    while day < MAX and w > restore[day]:
      t0s[day + 1] += t0s[day]
      if day + 1 in t1_cnt_save: t1_cnt -= t1_cnt_save[day + 1]
      t1s[day + 1] += t1s[day] + t1_cnt
      if day + 1 in t3_cnt_save: t3_cnt -= t3_cnt_save[day + 1]
      t3s[day + 1] += t3s[day] + 2 * t3_cnt
      t2s[day + 1] += t2s[day] + t3s[day + 1]
      restore[day + 1] = restore[day] + 1 + t0s[day] + t1s[day] + t2s[day]
      day += 1
    
    if w <= restore[day]:
      print(day)
      if t == 0:
        t0s[day] += 1
        t0s[day + x] -= 1
      elif t == 1:
        t1_cnt += 1
        t1_cnt_save[day + x] += 1
        t1s[day] += 1
        t1s[day + x] -= x
      elif t == 2:
        t3_cnt += 1
        t3_cnt_save[day + x] += 1
        t3s[day] += 1
        t3s[day + x] -= x * 2 - 1
        t2s[day] += 1
        t2s[day + x] -= x ** 2
    else:print("Many years later")
  
  for _ in range(q):
    y = int(input())
    while day < y:
      t0s[day + 1] += t0s[day]
      t1_cnt -= t1_cnt_save[day + 1]
      t1s[day + 1] += t1s[day] + t1_cnt
      t3_cnt -= t3_cnt_save[day + 1]
      t3s[day + 1] += t3s[day] + 2 * t3_cnt
      t2s[day + 1] += t2s[day] + t3s[day + 1]
      restore[day + 1] = restore[day] + 1 + t0s[day] + t1s[day] + t2s[day]
      day += 1
    print(restore[y])

main()