結果
| 問題 | No.801 エレベーター |
| コンテスト | |
| ユーザー |
 Shinya Fujita
|
| 提出日時 | 2024-10-08 11:24:56 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,198 bytes |
| コンパイル時間 | 414 ms |
| コンパイル使用メモリ | 82,048 KB |
| 実行使用メモリ | 105,404 KB |
| 最終ジャッジ日時 | 2024-10-08 11:25:10 |
| 合計ジャッジ時間 | 11,669 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 10 TLE * 1 -- * 15 |
ソースコード
class LazyPropSegTree:
def __init__(self, op, e, mapping, composition, id_, v=[]):
assert (len(v) >= 0)
self.n = len(v)
self.log = (self.n - 1).bit_length()
self.size = 1 << self.log
self.d = [e for _ in range(2*self.size)]
self.lz = [id_ for _ in range(self.size)]
self.op = op
self.e = e
self.mapping = mapping
self.composition = composition
self.id_ = id_
for i in range(self.n):
self.d[self.size + i] = v[i]
for i in range(self.size - 1, 0, -1):
self.update(i)
def update(self, k):
self.d[k] = self.op(self.d[2*k], self.d[2*k+1])
def all_apply(self, k, f):
self.d[k] = self.mapping(f, self.d[k])
if k < self.size:
self.lz[k] = self.composition(f, self.lz[k])
def push(self, k):
self.all_apply(2*k, self.lz[k])
self.all_apply(2*k+1, self.lz[k])
self.lz[k] = self.id_
def set(self, p, x):
assert (0 <= p) and (p < self.n)
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
self.d[p] = x
for i in range(1, self.log + 1):
self.update(p >> i)
def get(self, p):
assert (0 <= p) and (p < self.n)
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
return self.d[p]
def prod(self, left, right):
assert 0<=left and left<=right and right<=self.n
if left == right:
return self.e
left += self.size
right += self.size
for i in range(self.log, 0, -1):
if (((left >> i) << i) != left):
self.push(left >> i)
if (((right >> i) << i) != right):
self.push(right >> i)
sml, smr = self.e, self.e
while left < right:
if left & 1:
sml = self.op(sml, self.d[left])
left += 1
if right & 1:
right -= 1
smr = self.op(self.d[right], smr)
left >>= 1
right >>= 1
return self.op(sml, smr)
def all_prod(self):
return self.d[1]
def apply(self, p, f):
assert (0 <= p) and (p < self.n)
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
self.d[p] = self.mapping(f, self.d[p])
for i in range(1, self.log+1):
self.update(p >> i)
def apply_lr(self, left, right, f):
assert 0<=left and left<=right and right<=self.n
if left == right:
return
left += self.size
right += self.size
for i in range(self.log, 0, -1):
if (((left >> i) << i) != left):
self.push(left >> i)
if (((right >> i) << i) != right):
self.push((right - 1) >> i)
l2, r2 = left, right
while left < right:
if left & 1:
self.all_apply(left, f)
left += 1
if right & 1:
right -= 1
self.all_apply(right, f)
left >>= 1
right >>= 1
left, right = l2, r2
for i in range(1,self.log+1):
if (((left >> i) << i) != left):
self.update(left >> i)
if (((right >> i) << i) != right):
self.update((right-1) >> i)
def max_right(self, left, g):
assert (0 <= left) and (left <= self.n)
assert g(self.e)
if left == self.n:
return self.n
left += self.size
for i in range(self.log, 0, -1):
self.push(left >> i)
sm = self.e
while True:
while(left % 2 == 0):
left >>= 1
if not g(self.op(sm, self.d[left])):
while left < self.size:
self.push(left)
left <<= 1
if g(self.op(sm, self.d[left])):
sm = self.op(sm, self.d[left])
left += 1
return left - self.size
sm = self.op(sm, self.d[left])
left += 1
if(left & -left) == left:
break
return self.n
def min_left(self, right, g):
assert (0 <= right) and (right <= self.n)
assert g(self.e)
if right == 0:
return 0
right += self.size
for i in range(self.log, 0, -1):
self.push((right-1) >> i)
sm = self.e
while True:
right -= 1
while(right > 1) and (right % 2):
right >>= 1
if not g(self.op(self.d[right], sm)):
while right < self.size:
self.push(right)
right = 2 * right + 1
if g(self.op(self.d[right], sm)):
sm = self.op(self.d[right], sm)
right -= 1
return right + 1 - self.size
sm = self.op(self.d[right], sm)
if(right & -right) == right:
break
return 0
N, M, K = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(M)]
MOD = 10**9 + 7
e = 0
def composition(p, q):
if p is None:
return q
else:
if q is None:
return p
else:
return (p + q) % MOD
id_ = None
BASE = 1 << 20
def op(x, y):
x0, x1 = divmod(x, BASE)
y0, y1 = divmod(y, BASE)
s0 = (x0 + y0) % MOD
s1 = x1 + y1
return s0*BASE + s1
def mapping(p, x):
if p is None:
return x
x0, x1 = divmod(x, BASE)
x0 = (x0 + p*x1) % MOD
return x0*BASE + x1
v = [1] * N
v[0] += BASE
st = LazyPropSegTree(
op=op, e=e, mapping=mapping, composition=composition, id_=id_, v=v)
for _ in range(K):
nex = LazyPropSegTree(
op=op, e=e, mapping=mapping, composition=composition, id_=id_,
v=[1]*N)
for li, ri in data:
v = st.prod(li-1, ri)
s, _ = divmod(v, BASE)
nex.apply_lr(li-1, ri, s)
st = nex
v = st.get(N-1)
ans, _ = divmod(v, BASE)
print(ans)