結果
| 問題 | No.749 クエリ全部盛り |
| ユーザー |
 toyuzuko
|
| 提出日時 | 2020-09-22 17:52:48 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,911 bytes |
| コンパイル時間 | 270 ms |
| コンパイル使用メモリ | 82,308 KB |
| 実行使用メモリ | 496,044 KB |
| 最終ジャッジ日時 | 2024-06-26 07:55:56 |
| 合計ジャッジ時間 | 9,000 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 44 ms
61,504 KB |
| testcase_01 | AC | 43 ms
53,632 KB |
| testcase_02 | AC | 39 ms
53,760 KB |
| testcase_03 | AC | 39 ms
53,376 KB |
| testcase_04 | AC | 42 ms
53,632 KB |
| testcase_05 | AC | 168 ms
79,872 KB |
| testcase_06 | AC | 164 ms
79,568 KB |
| testcase_07 | AC | 164 ms
79,272 KB |
| testcase_08 | AC | 168 ms
80,988 KB |
| testcase_09 | AC | 170 ms
80,068 KB |
| testcase_10 | AC | 514 ms
100,184 KB |
| testcase_11 | AC | 484 ms
99,184 KB |
| testcase_12 | AC | 483 ms
98,616 KB |
| testcase_13 | AC | 490 ms
99,500 KB |
| testcase_14 | AC | 480 ms
98,148 KB |
| testcase_15 | TLE | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
ソースコード
class LazySegmentTree():
def __init__(self, n, op, e, mapping, composition, id):
self.n = n
self.op = op
self.e = e
self.mapping = mapping
self.composition = composition
self.id = id
self.log = (n - 1).bit_length()
self.size = 1 << self.log
self.d = [e] * (2 * self.size)
self.lz = [id] * (self.size)
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 build(self, arr):
#assert len(arr) == self.n
for i, a in enumerate(arr):
self.d[self.size + i] = a
for i in range(1, self.size)[::-1]:
self.update(i)
def set(self, p, x):
#assert 0 <= p < self.n
p += self.size
for i in range(1, self.log + 1)[::-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 < self.n
p += self.size
for i in range(1, self.log + 1):
self.push(p >> i)
return self.d[p]
def prod(self, l, r):
#assert 0 <= l <= r <= self.n
if l == r: return self.e
l += self.size
r += self.size
for i in range(1, self.log + 1)[::-1]:
if ((l >> i) << i) != l: self.push(l >> i)
if ((r >> i) << i) != r: self.push(r >> i)
sml = smr = self.e
while l < r:
if l & 1:
sml = self.op(sml, self.d[l])
l += 1
if r & 1:
r -= 1
smr = self.op(self.d[r], smr)
l >>= 1
r >>= 1
return self.op(sml, smr)
def all_prod(self):
return self.d[1]
def apply(self, p, f):
#assert 0 <= p < self.n
p += self.size
for i in range(1, self.log + 1)[::-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 range_apply(self, l, r, f):
#assert 0 <= l <= r <= self.n
if l == r: return
l += self.size
r += self.size
for i in range(1, self.log + 1)[::-1]:
if ((l >> i) << i) != l: self.push(l >> i)
if ((r >> i) << i) != r: self.push((r - 1) >> i)
l2 = l
r2 = r
while l < r:
if l & 1:
self.all_apply(l, f)
l += 1
if r & 1:
r -= 1
self.all_apply(r, f)
l >>= 1
r >>= 1
l = l2
r = r2
for i in range(1, self.log + 1):
if ((l >> i) << i) != l: self.update(l >> i)
if ((r >> i) << i) != r: self.update((r - 1) >> i)
def max_right(self, l, g):
#assert 0 <= l <= self.n
#assert g(self.e)
if l == self.n: return self.n
l += self.size
for i in range(1, self.log + 1)[::-1]:
self.push(l >> i)
sm = self.e
while True:
while l % 2 == 0: l >>= 1
if not g(self.op(sm, self.d[l])):
while l < self.size:
self.push(l)
l = 2 * l
if g(self.op(sm, self.d[l])):
sm = self.op(sm, self.d[l])
l += 1
return l - self.size
sm = self.op(sm, self.d[l])
l += 1
if (l & -l) == l: return self.n
def min_left(self, r, g):
#assert 0 <= r <= self.n
#assert g(self.e)
if r == 0: return 0
r += self.size
for i in range(1, self.log + 1)[::-1]:
self.push((r - 1) >> i)
sm = self.e
while True:
r -= 1
while r > 1 and r % 2: r >>= 1
if not g(self.op(self.d[r], sm)):
while r < self.size:
self.push(r)
r = 2 * r + 1
if g(self.op(self.d[r], sm)):
sm = self.op(self.d[r], sm)
r -= 1
return r + 1 - self.size
sm = self.op(self.d[r], sm)
if (r & -r) == r: return 0
def fibonacci(n, mod=1000000007):
res = [0 for _ in range(n + 1)]
res[0] = 0
res[1] = 1
for i in range(2, n + 1):
res[i] = res[i - 1] + res[i - 2]
res[i] %= mod
return res
import sys
input = sys.stdin.buffer.readline
MOD = 1000000007
N, Q = map(int, input().split())
F = fibonacci(N)
arr = [(0, 1, F[i]) for i in range(N)]
e = (0, 0, 0)
id = (1, 0, 0)
def op(a, b):
a1, a2, a3 = a
b1, b2, b3 = b
c1 = (a1 + b1) % MOD
c2 = (a2 + b2) % MOD
c3 = (a3 + b3) % MOD
return c1, c2, c3
def mapping(x, a):
x1, x2, x3 = x
a1, a2, a3 = a
c1 = (a1 * x1 + a2 * x2 + a3 * x3) % MOD
c2 = a2 % MOD
c3 = a3 % MOD
return c1, c2, c3
def composition(x, y):
x1, x2, x3 = x
y1, y2, y3 = y
z1 = (x1 * y1) % MOD
z2 = (x1 * y2 + x2) % MOD
z3 = (x1 * y3 + x3) % MOD
return z1, z2, z3
st = LazySegmentTree(N, op, e, mapping, composition, id)
st.build(arr)
res = []
for _ in range(Q):
q, l, r, k = map(int, input().split())
if q == 0:
res.append(k * st.prod(l, r + 1)[0] % MOD)
elif q == 1:
st.range_apply(l, r + 1, (0, k, 0))
elif q == 2:
st.range_apply(l, r + 1, (1, k, 0))
elif q == 3:
st.range_apply(l, r + 1, (k, 0, 0))
else:
st.range_apply(l, r + 1, (1, 0, k))
print('\n'.join(map(str, res)))