結果
問題 | No.1698 Face to Face |
ユーザー | eSeF |
提出日時 | 2021-09-18 17:04:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 4,029 ms / 5,000 ms |
コード長 | 4,278 bytes |
コンパイル時間 | 266 ms |
コンパイル使用メモリ | 86,784 KB |
実行使用メモリ | 224,652 KB |
最終ジャッジ日時 | 2023-09-26 16:02:20 |
合計ジャッジ時間 | 91,903 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 94 ms
72,240 KB |
testcase_01 | AC | 94 ms
72,116 KB |
testcase_02 | AC | 92 ms
71,924 KB |
testcase_03 | AC | 818 ms
188,244 KB |
testcase_04 | AC | 1,150 ms
201,676 KB |
testcase_05 | AC | 3,294 ms
220,208 KB |
testcase_06 | AC | 3,277 ms
223,056 KB |
testcase_07 | AC | 3,017 ms
224,652 KB |
testcase_08 | AC | 2,925 ms
220,772 KB |
testcase_09 | AC | 2,967 ms
222,332 KB |
testcase_10 | AC | 1,131 ms
204,700 KB |
testcase_11 | AC | 3,322 ms
217,616 KB |
testcase_12 | AC | 3,655 ms
219,356 KB |
testcase_13 | AC | 92 ms
71,992 KB |
testcase_14 | AC | 92 ms
71,924 KB |
testcase_15 | AC | 3,652 ms
213,212 KB |
testcase_16 | AC | 3,961 ms
217,004 KB |
testcase_17 | AC | 3,918 ms
218,048 KB |
testcase_18 | AC | 3,392 ms
199,368 KB |
testcase_19 | AC | 3,515 ms
198,116 KB |
testcase_20 | AC | 3,458 ms
193,696 KB |
testcase_21 | AC | 2,168 ms
144,344 KB |
testcase_22 | AC | 1,936 ms
132,208 KB |
testcase_23 | AC | 898 ms
95,808 KB |
testcase_24 | AC | 2,412 ms
151,984 KB |
testcase_25 | AC | 4,029 ms
212,460 KB |
testcase_26 | AC | 680 ms
90,492 KB |
testcase_27 | AC | 1,467 ms
119,176 KB |
testcase_28 | AC | 1,619 ms
121,232 KB |
testcase_29 | AC | 1,399 ms
114,892 KB |
testcase_30 | AC | 2,661 ms
163,832 KB |
testcase_31 | AC | 2,438 ms
150,456 KB |
testcase_32 | AC | 2,900 ms
174,300 KB |
testcase_33 | AC | 2,980 ms
178,104 KB |
testcase_34 | AC | 3,708 ms
208,136 KB |
testcase_35 | AC | 92 ms
71,944 KB |
testcase_36 | AC | 96 ms
72,044 KB |
testcase_37 | AC | 93 ms
72,096 KB |
testcase_38 | AC | 93 ms
71,924 KB |
testcase_39 | AC | 92 ms
72,236 KB |
testcase_40 | AC | 94 ms
71,936 KB |
testcase_41 | AC | 92 ms
72,064 KB |
testcase_42 | AC | 92 ms
72,116 KB |
testcase_43 | AC | 94 ms
72,184 KB |
testcase_44 | AC | 91 ms
72,004 KB |
testcase_45 | AC | 2,340 ms
211,196 KB |
testcase_46 | AC | 2,459 ms
216,604 KB |
testcase_47 | AC | 2,452 ms
215,960 KB |
ソースコード
class UnionFind_AB: def __init__(self, N): self.p = [-1] * N self.L = [i for i in range(N)] self.R = [i for i in range(N)] def root(self, x): while self.p[x] >= 0: x = self.p[x] return x def same(self, x, y): return self.root(x) == self.root(y) def unite(self, x, y): x = self.root(x) y = self.root(y) if x == y: return p = self.p if p[x] > p[y]: p[y] += p[x] p[x] = y if self.L[y] > self.L[x]: self.L[y] = self.L[x] if self.R[y] < self.R[x]: self.R[y] = self.R[x] else: p[x] += p[y] p[y] = x if self.L[x] > self.L[y]: self.L[x] = self.L[y] if self.R[x] < self.R[y]: self.R[x] = self.R[y] def size(self, x): return -self.p[self.root(x)] def left(self, v): return self.L[self.root(v)] def right(self,v): return self.R[self.root(v)] class UnionFind_IDX: def __init__(self, N): self.p = [-1] * N self.num_pair = [0] * N self.score = 0 def root(self, x): while self.p[x] >= 0: x = self.p[x] return x def same(self, x, y): return self.root(x) == self.root(y) def unite(self, x, y): x = self.root(x) y = self.root(y) if x == y: return self.score -= self.sub_score(x) + self.sub_score(y) p = self.p if p[x] > p[y]: p[y] += p[x] p[x] = y self.num_pair[y] += self.num_pair[x] self.score += self.sub_score(y) else: p[x] += p[y] p[y] = x self.num_pair[x] += self.num_pair[y] self.score += self.sub_score(x) def add_pair(self,v): rv = self.root(v) self.score -= self.sub_score(rv) self.num_pair[rv]+=1 self.score += self.sub_score(rv) def size(self, x): return -self.p[self.root(x)] def sub_score(self,v): return min(-self.p[self.root(v)],self.num_pair[self.root(v)]) import sys from collections import deque def main(): input = sys.stdin.readline n = int(input()) a = list(map(int,input().split())) b = list(map(int,input().split())) z = list(map(int,input().split())) ida = [-1]*n idb = [-1]*n rn = range(n) for i in rn: a[i]-=1 b[i]-=1 z[i]-=1 ida[a[i]]=i idb[b[i]]=i pos_left = [-1]*n l = [-1]*n r = [n]*n mid = [[] for i in rn] for _ in [0]*(17): for i in rn: if r[i]-l[i]>1: mid[(l[i]+r[i])//2].append(i) ufa = UnionFind_AB(n) ufb = UnionFind_AB(n) for k in rn: ia = ida[k] ib = idb[k] if 0<ia and a[ia-1]<=k: ufa.unite(ia-1,ia) if ia+1<n and a[ia+1]<=k: ufa.unite(ia,ia+1) if 0<ib and b[ib-1]<=k: ufb.unite(ib-1,ib) if ib+1<n and b[ib+1]<=k: ufb.unite(ib,ib+1) for j in mid[k]: la, ra = ufa.left(ida[j]),ufa.right(ida[j]) lb, rb = ufb.left(idb[z[j]]),ufb.right(idb[z[j]]) if ra < lb or rb < la: l[j] = k else: r[j] = k pos_left[j] = max(la,lb) mid[k].clear() for i in rn: mid[r[i]].append(i) less_k = [0]*n ufi = UnionFind_IDX(n) ans = [] for k in rn: ia, ib = ida[k],idb[k] less_k[ia]+=1 less_k[ib]+=1 if less_k[ia]==2: if 0<ia and less_k[ia-1]==2: ufi.unite(ia-1,ia) if ia+1<n and less_k[ia+1]==2: ufi.unite(ia,ia+1) if less_k[ib]==2: if 0<ib and less_k[ib-1]==2: ufi.unite(ib-1,ib) if ib+1<n and less_k[ib+1]==2: ufi.unite(ib,ib+1) for j in mid[k]: ufi.add_pair(pos_left[j]) ans.append(ufi.score) print("\n".join(map(str,ans))) if __name__=='__main__': main()