結果
| 問題 |
No.1054 Union add query
|
| コンテスト | |
| ユーザー |
 Shinya Fujita
|
| 提出日時 | 2024-10-06 14:34:23 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,774 bytes |
| コンパイル時間 | 338 ms |
| コンパイル使用メモリ | 82,176 KB |
| 実行使用メモリ | 389,004 KB |
| 最終ジャッジ日時 | 2024-10-06 14:34:38 |
| 合計ジャッジ時間 | 14,067 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 7 TLE * 1 |
ソースコード
import sys
sys.setrecursionlimit(10**8)
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, Q = map(int, input().split())
P = list(range(N+Q))
def find(i):
if i == P[i]:
return i
P[i] = find(P[i])
return P[i]
nex = N
tree = [[] for _ in range(N+Q)]
qs = []
for _ in range(Q):
t, a, b = map(int, input().split())
a -= 1
if t == 1:
b -= 1
pa = find(a)
pb = find(b)
if pa != pb:
tree[nex].append(pa)
tree[nex].append(pb)
tree[pa].append(nex)
tree[pb].append(nex)
P[pa] = P[pb] = nex
nex += 1
elif t == 2:
pa = find(a)
qs.append((2, pa, b))
else:
qs.append((3, a, 0))
In = [-1] * (N+Q)
Out = [-1] * (N+Q)
idx = 0
visited = [0] * (N+Q)
for i in range(nex-1, -1, -1):
if visited[i]:
continue
stack = [i]
while stack:
node = stack.pop()
if node >= 0:
visited[node] = 1
stack.append((~node))
In[node] = idx
idx += 1
for nex in tree[node]:
if In[nex] == -1:
stack.append(nex)
else:
Out[~node] = idx
idx += 1
INF = 10**10
op = lambda x,y: min(x,y)
e = INF
mapping = lambda p,x: p+x
composition = lambda p,q: p+q
id_ = 0
st = LazyPropSegTree(
op=op, e=e, mapping=mapping, composition=composition, id_=id_,
v=[0]*(max(max(In), max(Out))+1))
for t, a, b in qs:
if t == 2:
fr = In[a]
to = Out[a]
st.apply_lr(fr, to+1, b)
else:
pos = In[a]
print(st.get(pos))