結果
問題 | No.1768 The frog in the well knows the great ocean. |
ユーザー |
|
提出日時 | 2025-01-26 03:20:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 824 ms / 3,000 ms |
コード長 | 3,566 bytes |
コンパイル時間 | 566 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 154,512 KB |
最終ジャッジ日時 | 2025-01-26 03:20:53 |
合計ジャッジ時間 | 13,171 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 27 |
ソースコード
## https://yukicoder.me/problems/no/1768class BinaryIndexTree:"""フェニック木(BinaryIndexTree)の基本的な機能を実装したクラス"""def __init__(self, size):self.size = sizeself.array = [0] * (size + 1)def add(self, x, a):index = xwhile index <= self.size:self.array[index] += aindex += index & (-index)def sum(self, x):index = xans = 0while index > 0:ans += self.array[index]index -= index & (-index)return ansdef least_upper_bound(self, value):if self.sum(self.size) < value:return -1elif value <= 0:return 0m = 1while m < self.size:m *= 2k = 0k_sum = 0while m > 0:k0 = k + mif k0 < self.size:if k_sum + self.array[k0] < value:k_sum += self.array[k0]k += mm //= 2if k < self.size:return k + 1else:return -1def solve(N, A, B):a_map = {}for i in range(N):a = A[i]if a not in a_map:a_map[a] = []a_map[a].append(i)b_map = {}for i in range(N):a = B[i]if a not in b_map:b_map[a] = []b_map[a].append(i)# keyの統合events = list(a_map.keys()) + list(b_map.keys())events = set(events)events = list(events)events.sort(reverse=True)bit = BinaryIndexTree(N)for i in range(N + 1):bit.add(i + 1, 1)b_blocked = [True] * Nfor e in events:if e in b_map:for i in b_map[e]:bit.add(i + 1, -1)b_blocked[i] = Falseif e not in a_map:return "No"arrays = []for j in a_map[e]:if b_blocked[j]:return "No"x = bit.sum(j + 1)if x == 0:l = 0else:l = bit.least_upper_bound(x)if x == bit.sum(bit.size):r = N - 1else:r = bit.least_upper_bound(x + 1)r -= 2arrays.append((l, r))for i in b_map[e]:if i < arrays[0][0]:return "No"low = 0high = len(arrays) - 1while high - low > 1:mid = (high + low) // 2if arrays[mid][0] <= i:low = midelse:high = midif arrays[high][0] <= i:vv = highelse:vv = lowif arrays[vv][1] < i:return "No"if e in a_map:for j in a_map[e]:bit.add(j + 1, 1)return "Yes"def main():T = int(input())answers = []for _ in range(T):N = int(input())A = list(map(int, input().split()))B = list(map(int, input().split()))ans = solve(N, A, B)answers.append(ans)for ans in answers:print(ans)if __name__ == "__main__":main()