結果

問題 No.801 エレベーター
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-06-29 13:26:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,850 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,116 KB
実行使用メモリ 199,344 KB
最終ジャッジ日時 2024-06-25 17:29:59
合計ジャッジ時間 5,722 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
58,112 KB
testcase_01 AC 37 ms
52,480 KB
testcase_02 AC 38 ms
52,992 KB
testcase_03 AC 158 ms
77,616 KB
testcase_04 AC 153 ms
77,592 KB
testcase_05 AC 159 ms
77,680 KB
testcase_06 AC 156 ms
77,716 KB
testcase_07 AC 167 ms
77,480 KB
testcase_08 AC 158 ms
77,604 KB
testcase_09 AC 152 ms
77,900 KB
testcase_10 AC 161 ms
77,932 KB
testcase_11 AC 155 ms
77,468 KB
testcase_12 AC 159 ms
77,808 KB
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Binary Indexed Tree (Fenwick Tree)
# 1-indexed
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  # sum(ary[:i])
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  # ary[i]+=x
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  # sum(ary[i:j])
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)

# 区間加算可能なBIT。内部的に1-indexed BITを使う
class BIT_Range():
  def __init__(self,n):
    self.n=n
    self.bit0=BIT(n+1)
    self.bit1=BIT(n+1)
  # for i in range(l,r):ary[i]+=x
  def add(self,l,r,x):
    l+=1
    self.bit0.add(l,-x*(l-1))
    self.bit0.add(r+1,x*r)
    self.bit1.add(l,x)
    self.bit1.add(r+1,-x)
  # sum(ary[:i])
  def sum(self,i):
    if i==0:return 0
    #i-=1
    return self.bit0.sum(i)+self.bit1.sum(i)*i
  # ary[i]
  def get(self,i):
    return self.sum(i+1)-self.sum(i)
  # sum(ary[i:j])
  def get_range(self,i,j):
    return self.sum(j)-self.sum(i)

n,m,k=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(m)]
mod=10**9+7
"""
1<=n<=3000
各階について、次の移動でいけるところのパターンを列挙→行列になる。
区間加算seg木？
j回目の移動でi階につく場合数
これをO(1)で計算できれば問題ない。
[li,ri]
区間合計をそのままこの区間に加算する。
"""
bit=BIT_Range(n+1)
bit.add(1,2,1)
for _ in range(k):
  nbit=BIT_Range(n+1)
  for l,r in lr:
    s=bit.sum(r+1)-bit.sum(l)
    s%=mod
    nbit.add(l,r+1,s)
  bit=nbit
#print([bit.sum(i+1)-bit.sum(i) for i in range(1,n+1)])
print((bit.sum(n+1)-bit.sum(n))%mod)
#print(bit.sum(n+1))
"""
2 2 2
1 2
1 2

2 2 1
1 2
1 2

"""
0