結果
| 問題 |
No.1673 Lamps on a line
|
| コンテスト | |
| ユーザー |
 nephrologist
|
| 提出日時 | 2021-09-11 12:49:28 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,496 ms / 2,000 ms |
| コード長 | 6,431 bytes |
| コンパイル時間 | 148 ms |
| コンパイル使用メモリ | 82,444 KB |
| 実行使用メモリ | 203,864 KB |
| 最終ジャッジ日時 | 2024-06-22 20:45:14 |
| 合計ジャッジ時間 | 7,978 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 11 |
ソースコード
# https://yukicoder.me/problems/no/1673
# from ACL python
# https://github.com/shakayami/ACL-for-python
import sys
input = sys.stdin.buffer.readline
class LazySegmentTree:
"""
V: initial array
OP: (seg, seg) -> (seg)
E: element of segment tree
MAPPING: lazy -> segment
COMPOSITION: (lazy,lazy) -> (lazy)
ID: element of lazy
apply
apply_point: apply_point
apply: apply_range
queries
get: get_point
prod: get_range
"""
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.identity
def __init__(self, V, OP, E, MAPPING, COMPOSITION, ID):
self.n = len(V)
self.log = (self.n - 1).bit_length()
self.size = 1 << self.log
self.d = [E for i in range(2 * self.size)]
self.lz = [ID for i in range(self.size)]
self.e = E
self.op = OP
self.mapping = MAPPING
self.composition = COMPOSITION
self.identity = 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 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, l, r):
assert 0 <= l and l <= r and r <= self.n
if l == r:
return self.e
l += self.size
r += self.size
for i in range(self.log, 0, -1):
if ((l >> i) << i) != l:
self.push(l >> i)
if ((r >> i) << i) != r:
self.push(r >> i)
sml, smr = self.e, 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_point(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(self, l, r, f):
assert 0 <= l and l <= r and r <= self.n
if l == r:
return
l += self.size
r += self.size
for i in range(self.log, 0, -1):
if ((l >> i) << i) != l:
self.push(l >> i)
if ((r >> i) << i) != r:
self.push((r - 1) >> i)
l2, r2 = l, 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, r = l2, 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 and l <= self.n
assert g(self.e)
if l == self.n:
return self.n
l += self.size
for i in range(self.log, 0, -1):
self.push(l >> i)
sm = self.e
while 1:
while i % 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:
break
return self.n
def min_left(self, r, g):
assert 0 <= r and r <= self.n
assert g(self.e)
if r == 0:
return 0
r += self.size
for i in range(self.log, 0, -1):
self.push((r - 1) >> i)
sm = self.e
while 1:
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:
break
return 0
def debug(self):
print("Segmant")
for i in range(self.log):
print(self.d[1 << i : 1 << (i + 1)])
print("Lazy")
for i in range(self.log):
print(self.lz[1 << i : 1 << (i + 1)])
element = (0, -1, -1)
lazy_element = 0
def operation(s1, s2):
a1, b1, c1 = s1
a2, b2, c2 = s2
if b1 == -1:
return s2
if b2 == -1:
return s1
assert b1 < b2
assert c1 < c2
return (a1 + a2, b1, c2)
def mapping(l1, s1):
if not l1:
return s1
a1, b1, c1 = s1
if b1 == -1:
return s1
return ((c1 - b1) - a1, b1, c1)
def composition(l1, l2):
if l1 == 1 and l2 == 1:
return 0
if l1 == 0 and l2 == 1:
return 1
if l1 == 1 and l2 == 0:
return 1
if l1 == 0 and l2 == 0:
return 0
return l1 ^ l2
n, q = map(int, input().split())
A = [(0, i, i + 1) for i in range(n)]
LST = LazySegmentTree(A, operation, element, mapping, composition, lazy_element)
for _ in range(q):
left, right = map(int, input().split())
left, right = left - 1, right - 1
LST.apply(left, right + 1, 1)
print(LST.prod(0, n)[0])
# print(LST.all_prod())