結果
問題 | No.1054 Union add query |
ユーザー | Shinya Fujita |
提出日時 | 2024-10-06 14:23:10 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 6,757 bytes |
コンパイル時間 | 253 ms |
コンパイル使用メモリ | 82,204 KB |
実行使用メモリ | 401,432 KB |
最終ジャッジ日時 | 2024-10-06 14:23:25 |
合計ジャッジ時間 | 14,507 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
53,632 KB |
testcase_01 | AC | 42 ms
54,144 KB |
testcase_02 | AC | 40 ms
53,504 KB |
testcase_03 | AC | 1,732 ms
242,816 KB |
testcase_04 | TLE | - |
testcase_05 | AC | 1,354 ms
230,672 KB |
testcase_06 | AC | 1,367 ms
323,704 KB |
testcase_07 | AC | 1,299 ms
401,432 KB |
testcase_08 | AC | 1,466 ms
344,416 KB |
testcase_09 | AC | 1,487 ms
281,136 KB |
testcase_10 | AC | 1,158 ms
269,636 KB |
ソースコード
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(N+Q-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]*(2*N+2*Q)) 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))