結果
問題 | No.1698 Face to Face |
ユーザー | eSeF |
提出日時 | 2021-09-18 16:21:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 4,289 ms / 5,000 ms |
コード長 | 3,862 bytes |
コンパイル時間 | 1,719 ms |
コンパイル使用メモリ | 86,864 KB |
実行使用メモリ | 234,364 KB |
最終ジャッジ日時 | 2023-09-26 15:56:31 |
合計ジャッジ時間 | 100,233 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 70 ms
71,024 KB |
testcase_01 | AC | 68 ms
71,268 KB |
testcase_02 | AC | 71 ms
71,152 KB |
testcase_03 | AC | 823 ms
187,536 KB |
testcase_04 | AC | 1,185 ms
205,712 KB |
testcase_05 | AC | 3,418 ms
227,376 KB |
testcase_06 | AC | 3,326 ms
229,260 KB |
testcase_07 | AC | 3,210 ms
234,364 KB |
testcase_08 | AC | 3,143 ms
231,968 KB |
testcase_09 | AC | 3,185 ms
231,656 KB |
testcase_10 | AC | 1,097 ms
207,460 KB |
testcase_11 | AC | 3,544 ms
224,532 KB |
testcase_12 | AC | 3,696 ms
225,832 KB |
testcase_13 | AC | 69 ms
71,044 KB |
testcase_14 | AC | 69 ms
71,372 KB |
testcase_15 | AC | 4,256 ms
233,460 KB |
testcase_16 | AC | 4,279 ms
229,156 KB |
testcase_17 | AC | 4,115 ms
232,924 KB |
testcase_18 | AC | 3,802 ms
207,620 KB |
testcase_19 | AC | 3,891 ms
210,440 KB |
testcase_20 | AC | 3,643 ms
202,892 KB |
testcase_21 | AC | 2,506 ms
157,584 KB |
testcase_22 | AC | 2,355 ms
143,220 KB |
testcase_23 | AC | 1,097 ms
103,608 KB |
testcase_24 | AC | 2,840 ms
169,740 KB |
testcase_25 | AC | 3,946 ms
216,236 KB |
testcase_26 | AC | 793 ms
93,528 KB |
testcase_27 | AC | 1,895 ms
126,444 KB |
testcase_28 | AC | 1,850 ms
128,460 KB |
testcase_29 | AC | 1,666 ms
118,324 KB |
testcase_30 | AC | 2,868 ms
172,512 KB |
testcase_31 | AC | 2,574 ms
156,388 KB |
testcase_32 | AC | 3,508 ms
189,896 KB |
testcase_33 | AC | 3,420 ms
188,568 KB |
testcase_34 | AC | 4,289 ms
223,888 KB |
testcase_35 | AC | 71 ms
71,372 KB |
testcase_36 | AC | 71 ms
70,984 KB |
testcase_37 | AC | 70 ms
71,316 KB |
testcase_38 | AC | 72 ms
70,976 KB |
testcase_39 | AC | 70 ms
71,224 KB |
testcase_40 | AC | 71 ms
71,092 KB |
testcase_41 | AC | 70 ms
71,232 KB |
testcase_42 | AC | 70 ms
71,216 KB |
testcase_43 | AC | 72 ms
71,236 KB |
testcase_44 | AC | 69 ms
70,968 KB |
testcase_45 | AC | 2,841 ms
221,604 KB |
testcase_46 | AC | 2,852 ms
222,116 KB |
testcase_47 | AC | 2,649 ms
220,736 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 self.L[y] = min(self.L[y],self.L[x]) self.R[y] = max(self.R[y],self.R[x]) else: p[x] += p[y] p[y] = x self.L[x] = min(self.L[y],self.L[x]) self.R[x] = max(self.R[y],self.R[x]) 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): self.score -= self.sub_score(self.root(v)) self.num_pair[self.root(v)]+=1 self.score += self.sub_score(self.root(v)) 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 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 for i in range(n): 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 range(n)] for _ in range(17): for i in range(n): 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 range(n): 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 range(n): mid[r[i]].append(i) less_k = [0]*n ufi = UnionFind_IDX(n) ans = [] for k in range(n): 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 x in mid[k]: ufi.add_pair(pos_left[x]) ans.append(ufi.score) print("\n".join(map(str,ans)))