結果

問題 No.801 エレベーター
コンテスト
ユーザー persimmon-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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

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