結果

問題 No.801 エレベーター
ユーザー kohei2019kohei2019
提出日時 2022-04-13 23:48:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,390 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 81,956 KB
実行使用メモリ 108,340 KB
最終ジャッジ日時 2024-06-06 10:07:36
合計ジャッジ時間 8,522 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
58,368 KB
testcase_01 AC 43 ms
53,760 KB
testcase_02 AC 52 ms
62,212 KB
testcase_03 AC 464 ms
80,288 KB
testcase_04 AC 454 ms
80,104 KB
testcase_05 AC 423 ms
80,236 KB
testcase_06 AC 405 ms
80,156 KB
testcase_07 AC 436 ms
80,600 KB
testcase_08 AC 464 ms
80,568 KB
testcase_09 AC 456 ms
80,068 KB
testcase_10 AC 431 ms
80,612 KB
testcase_11 AC 438 ms
80,252 KB
testcase_12 AC 451 ms
79,896 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 # 

class lazy_segtree:
  #遅延評価セグメント木
  def __init__(s, op, e, mapping, composition, id, v):
    if type(v) is int: v = [e()] * v
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.lz = [id()] * s.size
    s.e = e
    s.op = op
    s.mapping = mapping
    s.composition = composition
    s.id = id
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  # 1点更新
  def set(s, p, x):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)
 
  # 1点取得
  def get(s, p):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    return s.d[p]
 
  # 区間演算
  def prod(s, l, r):
    if l == r: return s.e()
    l += s.size
    r += s.size
    for i in range(s.log, 0, -1):
      if (((l >> i) << i) != l): s.push(l >> i)
      if (((r >> i) << i) != r): s.push(r >> i)
    sml, smr = s.e(), s.e()
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)
 
  # 全体演算
  def all_prod(s): return s.d[1]
 
  # 1点写像
  def apply(s, p, f):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    s.d[p] = s.mapping(f, s.d[p])
    for i in range(1, s.log + 1): s.update(p >> i)
 
  # 区間写像
  def apply(s, l, r, f):
    if l == r: return
    l += s.size
    r += s.size
    for i in range(s.log, 0, -1):
      if (((l >> i) << i) != l): s.push(l >> i)
      if (((r >> i) << i) != r): s.push((r - 1) >> i)
    l2, r2 = l, r
    while l < r:
      if l & 1: 
        sml = s.all_apply(l, f)
        l += 1
      if r & 1:
        r -= 1
        smr = s.all_apply(r, f)
      l >>= 1
      r >>= 1
    l, r = l2, r2
    for i in range(1, s.log + 1):
      if (((l >> i) << i) != l): s.update(l >> i)
      if (((r >> i) << i) != r): s.update((r - 1) >> i)
   
  # L固定時の最長区間のR
  def max_right(s, l, g):
    if l == s._n: return _n
    l += s.size
    for i in range(s.log, 0, -1): s.push(l >> i)
    sm = s.e()
    while True:
      while (l % 2 == 0): l >>= 1
      if not g(s.op(sm, s.d[l])):
        while l < s.size:
          s.push(l)
          l = 2 * l
          if g(s.op(sm, s.d[l])):
            sm = s.op(sm, s.d[l])
            l += 1
        return l - s.size
      sm = s.op(sm, s.d[l])
      l += 1
      if (l & -l) == l: break
    return s._n
 
  # R固定時の最長区間のL
  def min_left(s, r, g):
    if r == 0: return 0
    r += s.size
    for i in range(s.log, 0, -1): s.push((r - 1) >> i)
    sm = s.e()
    while True:
      r -= 1
      while r > 1 and (r % 2): r >>= 1
      if not g(s.op(s.d[r], sm)):
        while r < s.size:
          s.push(r)
          r = 2 * r + 1
          if g(s.op(s.d[r], sm)):
            sm = s.op(s.d[r], sm)
            r -= 1
        return r + 1 - s.size
      sm = s.op(s.d[r], sm)
      if (r & - r) == r: break
    return 0
 
  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def all_apply(s, k, f):
    s.d[k] = s.mapping(f, s.d[k])
    if k < s.size: s.lz[k] = s.composition(f, s.lz[k])
  def push(s, k):
    s.all_apply(2 * k, s.lz[k])
    s.all_apply(2 * k + 1, s.lz[k])
    s.lz[k] = s.id()
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x
 
import sys
MOD = 10**9+7
def e():
  return 0
 
def op(s, t):
  sv, sn = s >> 32, s % (1 << 32)
  tv, tn = t >> 32, t % (1 << 32)
  return (((sv + tv) % MOD) << 32) + sn + tn
 
def mapping(f, a):
  fb, fc = f >> 32, f % (1 << 32)
  av, an = a >> 32, a % (1 << 32)
  return (((fb * av + fc * an) % MOD) << 32) + an
 
def composition(f, g):
  fb, fc = f >> 32, f % (1 << 32)
  gb, gc = g >> 32, g % (1 << 32)
  return ((fb * gb % MOD) << 32) + ((gc * fb + fc) % MOD)

def id():
  return 1 << 32
 
N,M,K = map(int,input().split())
lsLR = [tuple(map(int,input().split())) for i in range(M)]
ids = 1
ls = [ids]*(N+1)
ls[1] += 1<<32
dp = lazy_segtree(op, e, mapping, composition, id, ls)
for i in range(K):
    dp2 = lazy_segtree(op, e, mapping, composition, id, [ids]*(N+1))
    for j in range(M):
        ad = dp.prod(lsLR[j][0], lsLR[j][1]+1)>>32
        dp2.apply(lsLR[j][0], lsLR[j][1]+1,(1<<32)+ad)
    dp = dp2
print(dp.get(N)>>32)
0