結果
問題 | No.674 n連勤 |
ユーザー | detteiuu |
提出日時 | 2024-07-29 00:04:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 446 ms / 2,000 ms |
コード長 | 2,352 bytes |
コンパイル時間 | 401 ms |
コンパイル使用メモリ | 82,848 KB |
実行使用メモリ | 115,056 KB |
最終ジャッジ日時 | 2024-07-29 00:04:47 |
合計ジャッジ時間 | 4,552 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 37 ms
53,756 KB |
testcase_01 | AC | 38 ms
53,576 KB |
testcase_02 | AC | 37 ms
53,744 KB |
testcase_03 | AC | 39 ms
53,632 KB |
testcase_04 | AC | 38 ms
54,272 KB |
testcase_05 | AC | 37 ms
53,140 KB |
testcase_06 | AC | 39 ms
53,940 KB |
testcase_07 | AC | 41 ms
54,384 KB |
testcase_08 | AC | 40 ms
53,204 KB |
testcase_09 | AC | 38 ms
53,548 KB |
testcase_10 | AC | 37 ms
53,824 KB |
testcase_11 | AC | 134 ms
78,256 KB |
testcase_12 | AC | 139 ms
78,200 KB |
testcase_13 | AC | 116 ms
84,184 KB |
testcase_14 | AC | 192 ms
114,692 KB |
testcase_15 | AC | 209 ms
114,560 KB |
testcase_16 | AC | 374 ms
114,808 KB |
testcase_17 | AC | 376 ms
115,056 KB |
testcase_18 | AC | 446 ms
105,732 KB |
testcase_19 | AC | 237 ms
114,880 KB |
ソースコード
class UnionFind: def __init__(self,n): self.n = n self.parent_size = [-1]*n def leader(self,a): if self.parent_size[a] < 0: return a self.parent_size[a] = self.leader(self.parent_size[a]) return self.parent_size[a] def merge(self,a,b): x, y = self.leader(a), self.leader(b) if x == y: return if abs(self.parent_size[x]) < abs(self.parent_size[y]): x, y = y, x self.parent_size[x] += self.parent_size[y] self.parent_size[y] = x return def same(self,a,b): return self.leader(a) == self.leader(b) def size(self,a): return abs(self.parent_size[self.leader(a)]) def groups(self): result = [[] for _ in range(self.n)] for i in range(self.n): result[self.leader(i)].append(i) return [r for r in result if r != []] N, Q = map(int, input().split()) AB = [list(map(int, input().split())) for _ in range(Q)] L = [] for A, B in AB: L.append(A) L.append(B) S = sorted(set(L)) idx = dict() idxR = dict() for i in range(len(S)): idx[S[i]] = i idxR[i] = S[i] L = len(idx) UF = UnionFind(L) left = list(range(L)) right = list(range(L)) visited = [False]*L ans = [] MAX = 1 for A, B in AB: l, r = idx[A], idx[B] visited[l] = True if 1 <= l and visited[l-1] and not UF.same(l-1, l) and idxR[l]-idxR[l-1] == 1: nl = left[UF.leader(l-1)] nr = right[UF.leader(l)] UF.merge(l-1, l) left[UF.leader(l)] = nl right[UF.leader(l)] = nr MAX = max(MAX, idxR[right[UF.leader(l)]]-idxR[left[UF.leader(l-1)]]+1) l = right[UF.leader(l)] while l < r: visited[l+1] = True nl = left[UF.leader(l)] nr = right[UF.leader(l+1)] UF.merge(l, l+1) left[UF.leader(l)] = nl right[UF.leader(l)] = nr l = nr MAX = max(MAX, idxR[right[UF.leader(l)]]-idxR[left[UF.leader(l)]]+1) if r < L-1 and visited[r+1] and not UF.same(r, r+1) and idxR[r+1]-idxR[r] == 1: nl = left[UF.leader(r)] nr = right[UF.leader(r+1)] UF.merge(r, r+1) left[UF.leader(r)] = nl right[UF.leader(r)] = nr MAX = max(MAX, idxR[right[UF.leader(r)]]-idxR[left[UF.leader(r)]]+1) ans.append(MAX) print(*ans, sep="\n")