結果

問題 No.801 エレベーター
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-06-29 13:26:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,850 bytes
コンパイル時間 278 ms
コンパイル使用メモリ 87,136 KB
実行使用メモリ 78,788 KB
最終ジャッジ日時 2023-09-08 00:14:32
合計ジャッジ時間 6,646 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 65 ms
76,056 KB
testcase_01 AC 65 ms
71,440 KB
testcase_02 AC 66 ms
71,512 KB
testcase_03 AC 185 ms
78,552 KB
testcase_04 AC 184 ms
78,408 KB
testcase_05 AC 182 ms
78,528 KB
testcase_06 AC 173 ms
78,520 KB
testcase_07 AC 179 ms
78,704 KB
testcase_08 AC 180 ms
78,572 KB
testcase_09 AC 179 ms
78,604 KB
testcase_10 AC 177 ms
78,600 KB
testcase_11 AC 174 ms
78,536 KB
testcase_12 AC 178 ms
78,788 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