結果
問題 | No.1698 Face to Face |
ユーザー | eSeF |
提出日時 | 2021-09-18 16:40:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 4,747 ms / 5,000 ms |
コード長 | 4,220 bytes |
コンパイル時間 | 443 ms |
コンパイル使用メモリ | 87,016 KB |
実行使用メモリ | 271,832 KB |
最終ジャッジ日時 | 2023-09-26 16:05:21 |
合計ジャッジ時間 | 107,567 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 101 ms
72,212 KB |
testcase_01 | AC | 102 ms
72,308 KB |
testcase_02 | AC | 103 ms
72,228 KB |
testcase_03 | AC | 886 ms
255,444 KB |
testcase_04 | AC | 1,460 ms
265,768 KB |
testcase_05 | AC | 3,565 ms
268,868 KB |
testcase_06 | AC | 3,506 ms
268,248 KB |
testcase_07 | AC | 4,020 ms
267,036 KB |
testcase_08 | AC | 3,582 ms
268,996 KB |
testcase_09 | AC | 3,592 ms
271,832 KB |
testcase_10 | AC | 1,384 ms
268,676 KB |
testcase_11 | AC | 4,297 ms
265,368 KB |
testcase_12 | AC | 4,409 ms
269,992 KB |
testcase_13 | AC | 101 ms
72,384 KB |
testcase_14 | AC | 101 ms
72,256 KB |
testcase_15 | AC | 4,706 ms
268,696 KB |
testcase_16 | AC | 4,740 ms
270,832 KB |
testcase_17 | AC | 4,747 ms
271,132 KB |
testcase_18 | AC | 4,225 ms
270,972 KB |
testcase_19 | AC | 4,213 ms
268,904 KB |
testcase_20 | AC | 4,143 ms
268,592 KB |
testcase_21 | AC | 2,631 ms
189,624 KB |
testcase_22 | AC | 2,267 ms
167,212 KB |
testcase_23 | AC | 1,000 ms
106,420 KB |
testcase_24 | AC | 2,818 ms
205,236 KB |
testcase_25 | AC | 4,459 ms
268,980 KB |
testcase_26 | AC | 770 ms
97,104 KB |
testcase_27 | AC | 1,737 ms
141,464 KB |
testcase_28 | AC | 1,826 ms
148,708 KB |
testcase_29 | AC | 1,500 ms
128,784 KB |
testcase_30 | AC | 3,126 ms
222,856 KB |
testcase_31 | AC | 2,553 ms
189,232 KB |
testcase_32 | AC | 3,637 ms
246,856 KB |
testcase_33 | AC | 3,582 ms
249,852 KB |
testcase_34 | AC | 4,368 ms
268,620 KB |
testcase_35 | AC | 102 ms
72,492 KB |
testcase_36 | AC | 100 ms
72,436 KB |
testcase_37 | AC | 99 ms
72,316 KB |
testcase_38 | AC | 99 ms
72,352 KB |
testcase_39 | AC | 104 ms
72,340 KB |
testcase_40 | AC | 99 ms
72,292 KB |
testcase_41 | AC | 101 ms
72,188 KB |
testcase_42 | AC | 99 ms
72,540 KB |
testcase_43 | AC | 101 ms
72,132 KB |
testcase_44 | AC | 100 ms
72,424 KB |
testcase_45 | AC | 2,634 ms
268,972 KB |
testcase_46 | AC | 2,949 ms
266,240 KB |
testcase_47 | AC | 2,917 ms
264,812 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 from collections import deque input = sys.stdin.readline def main(): 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 = [deque() 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) while len(mid[k])>0: j = mid[k].pop() 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) 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) while len(mid[k])>0: ufi.add_pair(pos_left[mid[k].pop()]) ans.append(ufi.score) print("\n".join(map(str,ans))) if __name__=='__main__': main()