Problem:


Score : 400 points

Problem Statement

Mountaineers Mr. Takahashi and Mr. Aoki recently trekked across a certain famous mountain range.
The mountain range consists of N mountains, extending from west to east in a straight line as Mt. 1, Mt. 2, ..., Mt. N.
Mr. Takahashi traversed the range from the west and Mr. Aoki from the east.  

The height of Mt. i is h_i, but they have forgotten the value of each h_i.
Instead, for each i (1 ≤ i ≤ N), they recorded the maximum height of the mountains climbed up to the time they reached the peak of Mt. i (including Mt. i).
Mr. Takahashi's record is T_i and Mr. Aoki's record is A_i.  

We know that the height of each mountain h_i is a positive integer.
Compute the number of the possible sequences of the mountains' heights, modulo 10^9 + 7.

Note that the records may be incorrect and thus there may be no possible sequence of the mountains' heights.
In such a case, output 0.

Constraints

1 ≤ N ≤ 10^5

1 ≤ T_i ≤ 10^9

1 ≤ A_i ≤ 10^9

T_i ≤ T_{i+1} (1 ≤ i ≤ N - 1)

A_i ≥ A_{i+1} (1 ≤ i ≤ N - 1)

Input

The input is given from Standard Input in the following format:

N
T_1 T_2 ... T_N
A_1 A_2 ... A_N

Output

Print the number of possible sequences of the mountains' heights, modulo 10^9 + 7.

Sample Input 1

5
1 3 3 3 3
3 3 2 2 2

Sample Output 1

4

The possible sequences of the mountains' heights are:

1, 3, 2, 2, 2 

1, 3, 2, 1, 2 

1, 3, 1, 2, 2 

1, 3, 1, 1, 2 

for a total of four sequences.

Sample Input 2

5
1 1 1 2 2
3 2 1 1 1

Sample Output 2

0

The records are contradictory, since Mr. Takahashi recorded 2 as the highest peak after climbing all the mountains but Mr. Aoki recorded 3.

Sample Input 3

10
1 3776 3776 8848 8848 8848 8848 8848 8848 8848
8848 8848 8848 8848 8848 8848 8848 8848 3776 5

Sample Output 3

884111967

Don't forget to compute the number modulo 10^9 + 7.

Sample Input 4

1
17
17

Sample Output 4

1

Some mountain ranges consist of only one mountain.



Sample input:
5
1 3 3 3 3
3 3 2 2 2


Sample output:
4

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))

def main():
    N = I()
    T = LI()
    A = LI()

    lim = [inf]*N
    confirm = [None]*N
    
    now = 0
    for i,a in enumerate(T):
        if now < a:
            confirm[i] = a
            now = a
        lim[i] = a
    
    now = 0
    for i in range(N)[::-1]:
        a = A[i]
        if now < a:
            if confirm[i] is not None:
                if confirm[i] != a:
                    print(0)
                    return
            if lim[i] < a:
                print(0)
                return
            confirm[i] = a
            now = a
        lim[i] = min(lim[i], a)
        if confirm[i] is not None:
            if confirm[i] > lim[i]:
                print(0)
                return 
    
    ans = ModInt(1)
    for i,(l,c) in enumerate(zip(lim, confirm)):
        if c is None:
            ans *= l

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))

M = [[-1, 10**9] for i in range(N)]

for i in range(N):
    if i == 0:
        M[i][0] = T[i]
    else:
        if T[i] != T[i-1]:
            M[i][0] = T[i]
        else:
            M[i][1] = T[i]

for i in range(N-1, -1, -1):
    if i == N-1:
        if M[i][0] != -1 and M[i][0] != A[i]:
            print(0)
            exit(0)
        else:
            if M[i][1] >= A[i]:
                M[i][0] = A[i]
            else:
                print(0)
                exit(0)

    else:
        if A[i] != A[i+1]:
            if M[i][0] != -1 and M[i][0] != A[i]:
                print(0)
                exit(0)
            else:
                if A[i] <= M[i][1]:
                    M[i][0] = A[i]
                else:
                    print(0)
                    exit(0)
        else:
            M[i][1] = min(M[i][1], A[i])
ans = 1
mod = (10 ** 9) + 7
for x, y in M:
    if x == -1:
        ans *= y
        ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
T = np.array(lr()).astype('int64')
A = np.array(lr()).astype('int64')
MOD = 10 ** 9 + 7

T_low = T.copy()
T_low[1:][T[1:] <= T[:-1]] = 1
A_low = A.copy()
A_low[:-1][A[:-1] <= A[1:]] = 1

lower = np.maximum(T_low, A_low)
upper = np.minimum(T, A)
domain = np.maximum(0, upper - lower + 1) #変域が0の時は記録が間違い
L = len(domain); LSQ = int(L**.5 + 1) # least squares method 最小二乗推定?
domain = np.resize(domain, LSQ**2) #行列の形に無理やりする下準備（1次元）
domain[L:] = 1 #後半は全部1
domain = domain.reshape((LSQ, LSQ))
for n in range(1, LSQ):
    domain[:, n] *= domain[:, n-1]; domain[:, n] %= MOD
for n in range(1, LSQ):
    domain[n] *= domain[n-1, -1]; domain[n] %= MOD
answer = domain[-1, -1]
print(answer)

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
T = np.array(lr()).astype('int64')
A = np.array(lr()).astype('int64')
MOD = 10 ** 9 + 7

T_low = T.copy()
T_low[1:][T[1:] <= T[:-1]] = 1
A_low = A.copy()
A_low[:-1][A[:-1] <= A[1:]] = 1

lower = np.maximum(T_low, A_low)
upper = np.minimum(T, A)
domain = np.maximum(0, upper - lower + 1) #変域が0の時は記録が間違い
L = len(domain); LSQ = int(L**.5 + 1)
domain = np.resize(domain, LSQ**2) #行列の形に無理やりする下準備（1次元）
domain[L:] = 1 #後半は全部1
domain = domain.reshape((LSQ, LSQ))
for n in range(1, LSQ):
    domain[:, n] *= domain[:, n-1]; domain[:, n] %= MOD
for n in range(1, LSQ):
    domain[n] *= domain[n-1, -1]; domain[n] %= MOD
answer = domain[-1, -1]
print(answer)

Submission status: Accepted

Solution code:

if __name__ == '__main__':
    N = int(input())
    T = list(map(int, input().split()))
    A = list(map(int, input().split()))
    ans = 1
    if T[0] > A[0] or T[N-1] < A[N-1]:
        ans = 0
    for i in range(N-1):
        if T[i] > T[i+1]:
            ans = 0
        if T[i] < T[i+1] and T[i+1] > A[i+1]:
            ans = 0
    for i in range(N-1, 0, -1):
        if A[i] > A[i-1]:
            ans = 0
        if A[i] < A[i-1] and A[i-1] > T[i-1]:
            ans = 0
    for i in range(1, N-1):
        if T[i] != T[i-1] or A[i] != A[i+1]:
            continue
        else:
            ans *= min(A[i], T[i])
            ans %= int(1e9+7)
    print(ans)

Submission status: Accepted

Solution code:
def main():
    mod = 10 ** 9 + 7

    n = int(input())
    *t, = map(int, input().split())
    *a, = map(int, input().split())

    if t[-1] != a[0]:
        # 高橋と青木の見た山の高さの最大値が一致しない
        print(0)
        return

    ret = 1

    # [lo,hi]
    for i in range(n):
        if i == 0:
            lo = hi = t[i]
        else:
            if t[i - 1] < t[i]:
                # 山iの高さは一意に定まる
                lo = hi = t[i]
            elif t[i - 1] == t[i]:
                # [1,t[i]]の範囲で自由に選べる
                lo = 1
                hi = t[i]
            else:
                # t[i - 1] > t[i]:
                print(0)
                return

        if i == n - 1:
            lo = max(lo, a[i])
            hi = min(hi, a[i])
        else:
            if a[i] > a[i + 1]:
                # 山iの高さは一意に定まる
                lo = max(lo, a[i])
                hi = min(hi, a[i])
            elif a[i] == a[i + 1]:
                # [1,a[i]]の範囲で自由に選べる
                lo = max(lo, 1)
                hi = min(hi, a[i])
            else:
                # a[i] < a[i + 1]:
                print(0)
                return

        if lo > hi:
            print(0)
            return

        ret = ret * (hi - lo + 1) % mod

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
T = list(map(int,input().split()))
A = list(map(int,input().split()))

B = [[-1] * n for i in range(4)]

B[0][0] = T[0]
B[1][0] = T[0]+1

for i in range(1, n):
    if T[i] == T[i-1]:
        B[0][i] = 1
        B[1][i] = T[i] + 1
    elif T[i] > T[i-1]:
        B[0][i] = T[i]
        B[1][i] = T[i] + 1

B[2][n-1] = A[-1]
B[3][n-1] = A[-1]+1

for i in range(n-2, -1, -1):
    if A[i] == A[i+1]:
        B[2][i] = 1
        B[3][i] = A[i] + 1
    elif A[i] > A[i+1]:
        B[2][i] = A[i]
        B[3][i] = A[i] + 1

# print(B)

ans = 1
mod = 10**9+7
for i in range(n):
    ans = (ans * max(0, min(B[1][i], B[3][i]) - max(B[0][i], B[2][i]))) % mod
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n=I()
L=LI()
R=LI()
h=[() for i in range(n)]

p=0

for i in range(n):
    c=L[i]
    if c>p:
        h[i]=(c,c)
    else:
        h[i]=(1,c)
    p=c

p=0
for i in range(n-1,-1,-1):
    c=R[i]
    l,r=h[i]
    if c>p:
        if l==r:
            if l!=c:
                h[i]=(c,c-1)
        elif l<=c<=r:
            h[i]=(c,c)
        else:
            h[i]=(c,c-1)
    else:
        h[i]=(max(l,1),min(r,c))
    p=c

ans=1
for i in range(n):
    l,r=h[i]
    ans*=r-l+1
    ans%=mo

print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
import sys

N = int(input())

T = list(map(int,input().split()))
A = list(map(int,input().split()))

able = [0] * N
dif = [False] * N

for i in range(N):

    able[i] = min(T[i],A[i])

for i in range(N):

    if i == 0 or T[i] != T[i-1]:
        dif[i] = True

        if A[i] < T[i]:
            print (0)
            sys.exit()

for i in range(N):
    if i == N-1 or A[i] != A[i+1]:

        if dif[i]:
            if T[i] != A[i]:
                print (0)
                sys.exit()

        else:
            if A[i] > T[i]:
                print (0)
                sys.exit()
        
        dif[i] = True

ans = 1
for i in range(N):

    if dif[i]:
        continue

    ans *= able[i]
    ans %= mod

print (ans)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10**9+7
ans = 1
if n == 1 and t != a:
    print(0)
    exit()
for i in range(1,n-1):
    if t[i-1] == t[i] and a[i] == a[i+1]:
        ans = (ans*min(t[i],a[i]))%mod
    elif t[i-1] < t[i] and t[i] > a[i]:
        print(0)
        exit()
    elif a[i] > a[i+1] and t[i] < a[i]:
        print(0)
        exit()
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

N=input()
T=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

if max(T)!=max(A):
    print 0
    quit()

L=[ None for _ in range(N) ]

#一意に決まる山の高さを配列に代入。配列にNoneで残っているところが山の高さが一意に決まらない箇所
#左から
for i,t in enumerate(T):
    if i==0:
        L[i]=t
    else:
        if prev_t<t:
            L[i]=t
        elif prev_t>t:
            print 0
            quit()
    prev_t=t


#右から
for i,a in enumerate(A[::-1]):
    i=N-i-1 #左から見た順のインデックスに置き換える
    if i==N-1:
        L[i]=a
    else:
        if prev_a<a:
            if L[i] is not None:    #山の高さが既に入っているときは
                if L[i]!=a: #同じ高さじゃないと矛盾があるので、その場合はゼロで終了
                    print 0
                    quit()
            L[i]=a  #それ以外の場合は山の高さを配列に代入
        elif prev_a>a:
            print 0
            quit()
    prev_a=a

#一意に決まる値を入れたLを左から再検査。最大値が配列Aと矛盾していないか
max_x=0
for x,t in zip(L,T):
    #print x,t
    if x is not None:
        max_x=max(max_x,x)
        if max_x!=t:
            print 0
            quit()

#Lを右から再検査
max_x=0
for x,a in zip(L[::-1],A[::-1]):
    if x is not None:
        max_x=max(max_x,x)
        if max_x!=a:
            print 0
            quit()


ans=1
mod=10**9+7
for x,a,t in zip(L,T,A):
    if x is None:   #山の高さがNoneになっている箇所は自由度がある所なので、aとtの最小値の通り数を答えにかける
        ans*=min(a,t)
        ans%=mod
print ans

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))

T_d = [1] * N
T_d[0] = T[0]
for i in range(1, N):
    if T[i - 1] < T[i]:
        T_d[i] = T[i]

A_d = [1] * N
A_d[-1] = A[-1]
for i in range(N - 2, -1, -1):
    if A[i] > A[i + 1]:
        A_d[i] = A[i]

# print (T)
# print (T_d)
# print ()
# print (A)
# print (A_d)

ans = 1
for i in range(N):
    tmp = max(0, min(A[i], T[i]) - max(A_d[i], T_d[i]) + 1)
    ans *= tmp
    ans %= MOD

print (ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()] + [0]
B = [int(a) for a in input().split()] + [0]

MA = [0] * N
MI = [1] * N
P = 10**9+7
for i in range(N):
    if A[i] > A[i-1]:
        MA[i] = MI[i] = A[i]
    else:
        MA[i] = A[i]

for i in range(N)[::-1]:
    if B[i] > B[i+1]:
        if MI[i] <= B[i] <= MA[i]:
            MA[i] = MI[i] = B[i]
        else:
            print(0)
            exit()
    else:
        if B[i] >= MI[i]:
            MA[i] = min(MA[i], B[i])
        else:
            print(0)
            exit()
ans = 1
for i in range(N):
    ans = ans * (MA[i] - MI[i] + 1) % P
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    t = LI()
    a = LI()[::-1]
    dt = [None] * n
    da = [None] * n
    ba = 0
    bt = 0
    for i in range(n):
        if bt < t[i]:
            dt[i] = (1, t[i])
            bt = t[i]
        else:
            dt[i] = (bt, bt)
    for i in range(n):
        if ba < a[i]:
            da[i] = (1, a[i])
            ba = a[i]
        else:
            da[i] = (ba, ba)
    da = da[::-1]
    ans = 1
    for i in range(n):
        f = True
        if da[i][0] == 1:
            if da[i][1] > dt[i][1]:
                print(0)
                return
            f &= 0
        if dt[i][0] == 1:
            if da[i][1] < dt[i][1]:
                print(0)
                return
            f &= 0
        if f:
            ans *= min(da[i][1], dt[i][1])
            ans %= mod
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))

    # A,Bそれぞれについて、隣接している値が異なる -> その山の値は確定
    C=[None]*n
    C[0]=A[0]
    for i in range(1,n):
        if(A[i]!=A[i-1]):
            C[i]=A[i]

    for i in range(n):
        if(C[i] and B[i]<C[i]):
            print(0)
            return

    D=[None]*n
    D[-1]=B[-1]
    for i in range(n-2,-1,-1):
        if(B[i]!=B[i+1]):
            D[i]=B[i]

    for i in range(n):
        if(D[i] and A[i]<D[i]):
            print(0)
            return

    ans=1
    for i in range(n):
        if(C[i] or D[i]): continue
        ans*=min(A[i],B[i])
        ans%=MOD

    print(ans)
resolve()

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
renew = [0] * n
b = 0
for i, h in enumerate(t):
	if b < h:
		if h > a[i]:
			print(0)
			exit()
		renew[i] = 1
		b = h
b = 0
for i, h in enumerate(a[::-1]):
	if b < h:
		if h > t[n - i - 1]:
			print(0)
			exit()
		renew[n - i - 1] = 1
		b = h
ans = 1
for f, th, ah in zip(renew, t, a):
	if not f:
		ans *= min(th, ah)
		ans %= mod
print(ans)

Submission status: Accepted

Solution code:
p = 10**9+7
N = int(input())
T = list(map(int,input().split()))
A = list(map(int,input().split()))
H = [0 for _ in range(N)]
cnt = 1
H[0] = T[0]
for i in range(1,N):
    if T[i]>T[i-1]:
        H[i] = T[i]
if H[-1]>0 and H[-1]!=A[-1]:
    cnt = 0
else:
    H[-1] = A[-1]
    for i in range(-2,-N-1,-1):
        if H[i]==0 and A[i]>A[i+1]:
            if A[i]<=T[i]:
                H[i] = A[i]
            else:
                cnt = 0
                break
        elif H[i]>0 and A[i]>A[i+1]:
            if H[i]==A[i]:continue
            else:
                cnt = 0
                break
    if cnt==1:
        for i in range(1,N-1):
            if H[i]==0:
                cnt = (cnt*min(T[i],A[i]))%p
print(cnt)

Submission status: Accepted

Solution code:
MOD = 1000000007

N = int(input())
T = list(map(int,input().split()))
A = list(map(int,input().split()))

H0 = [None for _ in range(N)]
H1 = [None for _ in range(N)]

incorrect = False

maxh = 0
for i in range(N):
    if maxh < T[i]:
        H0[i] = T[i]
        maxh = T[i]

maxh = 0
for i in reversed(range(N)):
    if H0[i] != None and H0[i] > A[i]:
        incorrect = True
    if maxh < A[i]:
        H1[i] = A[i]
        maxh = A[i]

ans = 1
for i in range(N):
    if H0[i]==None and H1[i]==None:
        ans *= min(A[i],T[i])
        ans %= MOD

print(ans if not incorrect else 0)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))

H = [0] * N
for i in range(N):
    if i == 0 or T[i - 1] < T[i]:
        H[i] = T[i]

for i in range(N - 1, -1, -1):
    if i == N - 1 or A[i] > A[i + 1]:
        H[i] = A[i]
    
ans = 1
for i in range(N):
    if H[i] == 0:
        H[i] = min(T[i], A[i])
        ans *= min(T[i], A[i])
        ans %= mod

flag = True
M = 0
for i in range(N):
    M = max(M, H[i])
    flag &= (M == T[i])
M = 0
for i in range(N - 1, -1, -1):
    M = max(M, H[i])
    flag &= (M == A[i])

if flag is True:
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    ans = "No"
    flag = False
    for s in S:
        if flag:
            if s=="F":
                ans = "Yes"
                break
        else:
            if s=="C":
                flag = True
    print(ans)
    return

def examB():
    K, T = LI()
    A = LI(); A.sort()
    ans = max(0,A[-1]*2-sum(A)-1)
    print(ans)
    return

def examC(mod):
    N = I()
    T = LI(); A = LI()
    H = [0]*N
    ans = 1
    if T[-1] != A[0]:
        ans = 0
    H[0] = T[0]; H[N-1] = A[N-1]
    for i in range(N-1):
        if T[i+1]>T[i]:
            if H[i+1]==0:
                H[i+1] = T[i+1]
            elif H[i+1]!=T[i+1]:
                ans = 0
        else:
            if H[i+1]==0:
                H[i+1] = -T[i+1]
    for i in range(N-1,0,-1):
        if A[i-1]>A[i]:
            if H[i-1]==0:
                H[i-1] = A[i-1]
            elif H[i-1]<0:
                if -H[i-1]<A[i-1]:
                    ans = 0
                else:
                    H[i-1] = A[i-1]
            elif H[i-1]!=A[i-1]:
                ans = 0
#    print(H)
    flag = False; cur = 0
    for i in H:
        if flag:
            if i<0:
                cur +=1
            else:
                ans *=(min(now,i)**cur)%mod
                ans %=mod
                flag = False
                cur = 0; now = i
        else:
            if i<0:
                cur = 1
                flag = True
            else:
                now = i
    print(ans%mod)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC(mod)

Submission status: Accepted

Solution code:
n=int(input())
t=list(map(int,input().split()))
a=list(map(int,input().split()))
if t[0]>a[0] or t[-1]<a[-1]:print(0);exit()
x=[1]*n
x[0]=x[-1]=0
for i in range(1,n):
  if t[i-1]!=t[i]:
    x[i]=0
    if t[i]>a[i]:print(0);exit()
for i in range(n-2,-1,-1):
  if a[i+1]!=a[i]:
    x[i]=0
    if t[i]<a[i]:print(0);exit()
ans=1
for i in range(n):
  if x[i]:
    ans*=min(t[i],a[i])
    ans%=10**9+7
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
b = b[::-1]

ua = [0 for i in range(n)]
fa = [False for i in range(n)]
ub = [0 for i in range(n)]
fb = [False for i in range(n)]


bm = 0
for i in range(n):
    if a[i] > bm:
        ua[i] = a[i]
        fa[i] = True
        bm = a[i]
    else:
        ua[i] = bm

bm = 0
for i in range(n):
    if b[i] > bm:
        ub[i] = b[i]
        fb[i] = True
        bm = b[i]
    else:
        ub[i] = bm
ub = ub[::-1]
fb = fb[::-1]
ans = 1
m = 10**9+7

for i in range(n):
    if fa[i] and fb[i]:
        if not ua[i] == ub[i]:
            ans = 0
            break
    elif fa[i] or fb[i]:
        if ua[i] > ub[i]:
            if not fb[i]:
                ans = 0
                break
        elif ua[i] == ub[i]:
            ans = ans
        else:
            if not fa[i]:
                ans = 0
                break
    else:
        ans *= min(ua[i],ub[i])
        ans %= m
    # print(ans)

print(ans)

# print(ua)
# print(fa)
# print(ub)
# print(fb)

Submission status: Accepted

Solution code:
import sys
N=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]

if T[-1] != A[0]:
    print(0)
    sys.exit()

max_=T[-1]
MAX_T=[max_ for _ in range(N)]
MIN_T=[1 for _ in range(N)]
MAX_A=[max_ for _ in range(N)]
MIN_A=[1 for _ in range(N)]

MAX_T[0] = T[0]
MIN_T[0] = T[0]
for i in range(1,N):
    MAX_T[i] = T[i]
    if T[i] > T[i-1]:
        MIN_T[i] = T[i]
    else:
        MIN_T[i] = 1 

#print(MAX_T)
#print(MIN_T)   
        
MAX_A[-1] = A[-1]
MIN_A[-1] = A[-1]
for i in range(0,N-1)[::-1]:
    MAX_A[i] = min(MAX_A[i],A[i])
    if A[i] > A[i+1]:
        MIN_A[i] = min(MAX_A[i],A[i])
    else:
        MIN_A[i] = max(1,MIN_A[i])
        
#print(MAX_A)
#print(MIN_A)

sum_= 1
lim = 10**9 + 7
for i in range(N):
    if (MAX_T[i] < MIN_A[i]) or (MAX_A[i] < MIN_T[i]):
        print(0)
        sys.exit()
    else:
        sum_ = (sum_ * (min(MAX_T[i],MAX_A[i]) - max(MIN_T[i],MIN_A[i]) +1 )) % lim
print(sum_)

Submission status: Accepted

Solution code:
N = int(input())
T = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
mod = 10 ** 9 + 7

def solve() :
    if T[-1] != A[0] :
        return 0
        
    for i in range(N) :
        if T[i] == T[-1] :
            break
    for j in range(N - 1, -1, -1) :
        if A[j] == A[0] :
            break
            
    if i > j :
        return 0
        
    ok = [False] * N
    ok[0] = ok[-1] = True
    for i in range(1, N) :
        if T[i] != T[i-1] :
            ok[i] = True
        if A[N-1-i] != A[N-i] :
            ok[N-1-i] = True

    ret = 1
    for i in range(N) :
        if ok[i] : continue
        ret = ret * min(T[i], A[i]) % mod   
    
    return ret
    
print(solve())

Submission status: Accepted

Solution code:
n=int(input())
tM=list(map(int,input().split()))
aM=list(map(int,input().split()))
tm=[1]*n
am=[1]*n

tm[0]=tM[0]
for i in range(1,n):
    if tM[i]>tM[i-1]:
        tm[i]=tM[i]

aM.reverse()
am[0]=aM[0]
for i in range(1,n):
    if aM[i]>aM[i-1]:
        am[i]=aM[i]
aM.reverse()
am.reverse()

m=[]
M=[]
for i in range(n):
    m.append(max(tm[i],am[i]))
    M.append(min(tM[i],aM[i]))

ans=1
mod=10**9+7
for i in range(n):
    ans*=max(0,M[i]-m[i]+1)
    ans%=mod

print(ans)

Submission status: Accepted

Solution code:
#不可能な場合の場合分け
n= int(input())
t = [0]+list(map(int, input().split( )))
tmx = max(t)
a = [tmx]+list(map(int, input().split( )))+[0]

if a[0]!= a[1]:
    print(0)
    exit()
ans = 1

for i in range(1,n+1):
    if t[i]>t[i-1]:
        if t[i]>a[i]:
            print(0)
            exit()
        continue
    if a[i]>a[i+1]:
        if a[i]>t[i]:
            print(0)
            exit()
        continue
    if t[i]>t[i-1] and a[i]>a[i+1]:
        if t[i]!=a[i]:
            print(0)
            exit()
        continue

    else:
        ans *= min(t[i],a[i])
        ans %=10**9+7
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = int(input())
*T, = map(int, input().split())
*A, = map(int, input().split())
ans = 1
for i in range(N):
    temp1 = -1
    temp2 = -1
    if i == 0 or T[i-1] < T[i]:
        temp1 = T[i]
    if i == N-1 or A[i] > A[i+1]:
        temp2 = A[i]

    if temp1 == -1 and temp2 == -1:
        ans = (ans * min(T[i], A[i])) % MOD
    elif temp1 == -1 and temp2 != -1:
        if temp2 > T[i]: ans = 0; break
    elif temp1 != -1 and temp2 == -1:
        if temp2 > A[i]: ans = 0; break
    else:
        if temp1 != temp2: ans = 0; break
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    T = list(map(int, input().split()))
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7

    ans = [0] * N
    H = [0] * N
    tmp = 0
    for i in range(N):
        if tmp < T[i]:
            tmp = T[i]
            ans[i] = 1
            H[i] = T[i]
        else:
            ans[i] = T[i]
            H[i] = T[i]

    tmp = 0
    for i in range(N-1,-1,-1):
        if tmp < A[i]:
            tmp = A[i]
            ans[i] = min(ans[i],1)
            H[i] = min(H[i],A[i])
        else:
            ans[i] = min(A[i],ans[i])
            H[i] = min(H[i],A[i])

    tmp = 0
    for i in range(N):
        tmp = max(tmp, H[i])
        if tmp != T[i]:
            print(0)
            exit()

    tmp = 0
    for i in range(N-1,-1,-1):
        tmp = max(tmp, H[i])
        if tmp != A[i]:
            print(0)
            exit()
    

    cnt = 1
    for i in ans:
        cnt *= i
        cnt %= MOD
    
    print(cnt)

if __name__ == "__main__":
    main()