結果

問題 No.801 エレベーター
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-06-29 14:17:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,970 bytes
コンパイル時間 262 ms
コンパイル使用メモリ 87,124 KB
実行使用メモリ 89,124 KB
最終ジャッジ日時 2023-09-08 00:15:34
合計ジャッジ時間 41,737 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 74 ms
71,168 KB
testcase_01 AC 68 ms
71,380 KB
testcase_02 AC 69 ms
71,276 KB
testcase_03 AC 129 ms
77,512 KB
testcase_04 AC 139 ms
77,656 KB
testcase_05 AC 135 ms
77,724 KB
testcase_06 AC 153 ms
77,800 KB
testcase_07 AC 145 ms
77,896 KB
testcase_08 AC 141 ms
77,596 KB
testcase_09 AC 134 ms
77,924 KB
testcase_10 AC 137 ms
77,796 KB
testcase_11 AC 140 ms
77,812 KB
testcase_12 AC 142 ms
77,740 KB
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 AC 1,785 ms
86,980 KB
testcase_24 AC 1,796 ms
86,616 KB
testcase_25 AC 1,823 ms
86,980 KB
testcase_26 TLE -
testcase_27 AC 1,852 ms
86,976 KB
testcase_28 AC 1,756 ms
88,972 KB
権限があれば一括ダウンロードができます

ソースコード

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)

def main0(n,m,k,lr):
  mod=10**9+7
  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
  return (bit.sum(n+1)-bit.sum(n))%mod

def main1(n,m,k,lr):
  mod=10**9+7
  lr.sort(key=lambda x:x[0])
  lrr=[[l,r] for l,r in lr]
  lrr.sort(key=lambda x:x[1],reverse=True)
  dp=[0]*(n+1)
  dp[1]=1

  now=0
  cnt=0
  mat=[[] for _ in range(n+1)]
  for _ in range(k):
    ndp=[0]*(n+1)
    sdp=[0]
    for x in dp:sdp.append((sdp[-1]+x)%mod)
    # 下からの遷移。同じ階の移動も含む
    idx=0
    now=0
    cnt=0
    for j in range(1,n+1):
      # j階への遷移
      while idx<m and lr[idx][0]==j:
        l,r=lr[idx]
        idx+=1
        cnt+=1
        mat[r].append(l)
      now+=cnt*dp[j]
      now%=mod
      ndp[j]+=now
      ndp[j]%=mod
      while mat[j]:
        l=mat[j].pop()
        # [l,j]のエレベータに乗り込む場合数を引く。sum(dp[l:j+1])
        now-=sdp[j+1]-sdp[l]
        #now-=sum(dp[l:j+1])
        cnt-=1
    # 上からの遷移。同じ階の移動は含まない
    now=0
    cnt=0
    idx=0
    for j in reversed(range(1,n+1)):
      # j階への遷移
      while idx<m and lrr[idx][1]==j:
        l,r=lrr[idx]
        idx+=1
        cnt+=1
        mat[l].append(r)
      ndp[j]+=now
      ndp[j]%=mod
      now+=cnt*dp[j]
      now%=mod
      while mat[j]:
        r=mat[j].pop()
        # [j,r]のエレベータに乗る場合数を引く。sum(dp[j:r+1])
        now-=sdp[r+1]-sdp[j]
        #now-=sum(dp[j:r+1])
        cnt-=1
    dp=ndp
  return dp[n]

if __name__=='__main__':
  n,m,k=map(int,input().split())
  lr=[list(map(int,input().split())) for _ in range(m)]
  #ret0=main0(n,m,k,lr)
  ret1=main1(n,m,k,lr)
  #print(ret0)
  print(ret1)
0