結果

問題 No.801 エレベーター
ユーザー persimmon-persimmon
提出日時 2021-06-29 14:17:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,970 bytes
コンパイル時間 203 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 87,680 KB
最終ジャッジ日時 2024-06-25 17:30:58
合計ジャッジ時間 39,027 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

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