結果

問題 No.1768 The frog in the well knows the great ocean.
ユーザー chineristACchineristAC
提出日時 2021-10-24 03:53:36
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,029 bytes
コンパイル時間 597 ms
コンパイル使用メモリ 86,908 KB
実行使用メモリ 103,380 KB
最終ジャッジ日時 2023-09-12 05:46:43
合計ジャッジ時間 6,037 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 158 ms
102,268 KB
testcase_20 AC 159 ms
102,360 KB
testcase_21 AC 110 ms
74,044 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 RE -
testcase_26 RE -
testcase_27 AC 114 ms
74,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        self.size = n
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = self.segfunc(self.tree[k],x)
        while k > 1:
            k >>= 1
            self.tree[k] = self.segfunc(self.tree[2*k], self.tree[2*k+1])

    def query(self, l, r):
        if r==self.size:
            r = self.num

        res = self.ide_ele

        l += self.num
        r += self.num
        right = []
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                right.append(self.tree[r-1])
            l >>= 1
            r >>= 1

        for e in right[::-1]:
            res = self.segfunc(res,e)
        return res
    
    def bisect_left(self,l,r,x):
        l += self.num
        r += self.num
        segment = []
        segment_r = []
        while l<r:
            if l&1:
                segment.append(l)
                l += 1
            if r&1:
                segment_r.append(r-1)
            l >>= 1
            r >>= 1
        segment += segment_r[::-1]
        tmp = self.ide_ele
        for pos in segment:
            check = self.segfunc(tmp,self.tree[pos])
            if x <= check :
                break
            else:
                tmp = check
        else:
            return -1
        
        while pos < self.num:
            check = self.segfunc(tmp,self.tree[2*pos])
            if x <= check:
                pos = 2 * pos
            else:
                tmp = check
                pos = 2 * pos + 1
        return pos - self.num
    
    def bisect_right(self,l,r,x):
        l += self.num
        r += self.num
        segment = []
        segment_r = []
        while l<r:
            if l&1:
                segment.append(l)
                l += 1
            if r&1:
                segment_r.append(r-1)
            l >>= 1
            r >>= 1
        segment += segment_r[::-1]
        tmp = self.ide_ele
        for pos in segment[::-1]:
            check = self.segfunc(tmp,self.tree[pos])
            if check >= x:
                break
            else:
                tmp = check
        else:
            return -1
        
        while pos < self.num:
            check = self.segfunc(tmp,self.tree[2*pos])
            if check >= x:
                pos = 2 * pos
            else:
                tmp = check
                pos = 2 * pos + 1
        return pos - self.num
    


import sys,random
from collections import deque
import bisect

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

def solve(N,A,B):
    if any(A[i] > B[i] for i in range(N)):
        return "No"
    
    val_to_idx = [[] for i in range(N+1)]
    check = [[] for i in range(N+1)]
    for i in range(N):
        val_to_idx[A[i]].append(i)
        check[B[i]].append(i)
    
    seg_A = SegmentTree(A,max,0)
    seg_B = SegmentTree(B,min,N+1)
    for k in range(1,N+1):
        t = val_to_idx[k]
        for idx in check[k]:
            flag = (A[idx]==k)
            i = bisect.bisect_right(t,idx)
            if i!=0:
                l = t[i-1]
                if seg_A.query(l,idx+1) <= k <= seg_B.query(l,idx+1):
                    flag = True
            if i!=len(t):
                r = t[i]
                if seg_A.query(idx,r+1) <= k <= seg_B.query(idx,r+1):
                    flag = True
            
            if not flag:
                return "No"
    
    return "Yes"

N = int(input())
A = li()
B = li()
print(solve(N,A,B))
0