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:
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
MIN = []
MAX = []
MIN.append(t[0])
MAX.append(t[0])

for i in range(1,n):
  if t[i] == t[i-1]:
    MIN.append(1)
    MAX.append(t[i])
  else:
    MIN.append(t[i])
    MAX.append(t[i])
MIN[-1] = max(MIN[-1],a[-1])
MAX[-1] = min(MAX[-1],a[-1])
for i in range(n-1,0,-1):
  if a[i-1] == a[i]:
    MAX[i-1] = min(MAX[i-1],a[i-1])
  else:
    MIN[i-1] = max(MIN[i-1],a[i-1])
    MAX[i-1] = min(MAX[i-1],a[i-1])
ans = 1
for i,j in zip(MIN,MAX):
  diff = j-i+1
  if diff <= 0:
    print(0)
    exit()
  ans *= diff
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys

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

# i番目の山が取りうる高さの下限、上限
cand = [[1, float("inf")] for _ in range(N)]

l_max = 0
for i in range(N):
    if l_max < T[i]:
        l_max = T[i]
        if cand[i][0] > T[i] or cand[i][1] < T[i]:
            # print("here1", cand[i][0], cand[i][1], T[i])
            print(0)
            sys.exit()
        else:
            cand[i] = [T[i], T[i]]

    else:
        cand[i][1] = min(cand[i][1], T[i])

r_max = 0
for i in range(N-1, -1, -1):
    if r_max < A[i]:
        r_max = A[i]
        if cand[i][0] > A[i] or cand[i][1] < A[i]:
            # print("here2", cand[i][0], cand[i][1], A[i])
            print(0)
            sys.exit()
        else:
            cand[i] = [A[i], A[i]]
    else:
        cand[i][1] = min(cand[i][1], A[i])

# print(l_max, r_max)
if l_max != r_max:
    print(0)
else:
    ans = 1
    for h_min, h_max in cand:
        ans *= (h_max - h_min + 1)
        ans %= 10**9 + 7

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))

tc = []
ac = []

tc.append((t[0], t[0]))
flag = 1
for i in range(n-1):
    if t[i+1] > t[i]:
        tc.append((t[i+1], t[i+1]))
    elif t[i+1] < t[i]:
        flag = 0
    else:
        tc.append((1, t[i+1]))

a.reverse()
ac.append((a[-1], a[-1]))
for i in range(n-1):
    if a[i+1] > a[i]:
        ac.append((a[i+1], a[i+1]))
    elif a[i+1] < a[i]:
        flag = 0
    else:
        ac.append((1, a[i+1]))

ac.reverse()
import sys
if flag == 0:
    print(0)
    sys.exit()

else:
    ans = 1
    for i in range(n):
        maxi = min(tc[i][1], ac[i][1])
        mini = max(tc[i][0], ac[i][0])
        ans *= max(0, maxi-mini+1)
        ans %= 10**9+7

    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
t_max = max(t)
for i in range(n):
  if t[i] == t_max:
    max_ind = i
    break
if t[max_ind] != a[max_ind] or t[-1] != a[0]:
  print(0)
else:
  idx = []
  before = 0
  for i in range(n):
    if before == t[i]:
      idx .append(i)
    before = t[i]
  if len(idx) == 0:
    print(1)
  else:
    new_idx = []
    for j in idx:
      if j < n-1 and a[j] == a[j+1]:
        new_idx.append(j)
    if len(new_idx) == 0:
      print(1)
    else:
      ans = 1
      for k in new_idx:
        ans *= min(t[k], a[k])
        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
h1=[[-1,-1]for _ in range(n)]
h1[0]=[t[0],t[0]]
for i in range(n-1):
	if t[i+1]>t[i]:
		h1[i+1]=[t[i+1],t[i+1]]
	else:
		h1[i+1]=[1,t[i+1]]
h2=[[-1,-1]for _ in range(n)]
a.reverse()
h2[-1]=[a[0],a[0]]
for i in range(n-1):
	if a[i+1]>a[i]:
		h2[-i-2]=[a[i+1],a[i+1]]
	else:
		h2[-i-2]=[1,a[i+1]]
ans=1
for i in range(n):
	ran=min(h1[i][1],h2[i][1])-max(h1[i][0],h2[i][0])+1
	if ran<=0:
		ans=0
		break
	ans*=ran
	ans%=mod
print(ans if ans>=0 else 0)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int,input().split()))
a = list(map(int,input().split()))
ans = 1
mod = 10**9+7
if (not a[0] == t[n-1]):
    print(0)
    exit()

for i in range(1,n-1):
    if ((not t[i] == t[i-1]) and t[i] > a[i]) or ((not a[i] == a[i+1]) and a[i] > t[i]):
        print(0)
        exit()
    elif t[i] == t[i-1] and a[i] == a[i+1]:
        ans = (ans*min(t[i],a[i]))%mod

print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**9
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    T = LI()
    A = LI()
    T = [0] + T + [T[-1]]
    A = [A[0]] + A + [0]

    ans = 1
    for i in range(1,N+1):
        m = 0
        if T[i] > T[i-1]:
            tmp1 = 1
            m1 = T[i]
        else:
            tmp1 = T[i]
            m1 = 1
        if A[i] > A[i+1]:
            tmp2 = 1
            m2 = A[i]
        else:
            tmp2 = A[i]
            m2 = 1

        if m1 <= m2 < m1 + tmp1 or m2 <= m1 < m2 + tmp2:
            tmp = min(tmp1,tmp2)
        else:
            tmp = 0
        ans = (ans * tmp) % MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 1000000007
n= int(input())
t= list(map(int,input().split()))
a= list(map(int,input().split()))
tb = [-1]*n
pre=-1
for i in range(n):
    if i==0:tb[i]=1
    else:
        if pre!=t[i]:tb[i]=1
    pre=t[i]
ab = [-1]*n
post=-1
for i in range(n-1,-1,-1):
    if i==n-1:ab[i]=1
    else:
        if post!=a[i]:ab[i]=1
    post=a[i]
er = False
if a[0]!=t[-1]:er=True
else:
    b=1
    for i in range(n):
        if tb[i]==1 or ab[i]==1:
            if tb[i]==1 and ab[i]==1:
                if t[i]==a[i]:pass
                else:
                    er=True
                    break
            else:
                if tb[i]==1:
                    if a[i]<t[i]:
                        er=True
                        break
                elif ab[i]==1:
                    if a[i]>t[i]:
                        er = True
                        break
        else:
            m = min(a[i],t[i])
            b = ((b% mod) * (m % mod)) % mod
if er:print(0)
else:print(b)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
T = LIST()
A = LIST()

h = [0]*N
ma = -1
for i, t in enumerate(T):
	if t > ma:
		h[i] = t
		ma = t

ma = -1
for i, a in enumerate(A[::-1]):
	if a > ma:
		if h[-i-1] and a != h[-i-1]:
			print(0)
			exit()
		h[-i-1] = a
		ma = a

acc_t = list(accumulate(h, max))
acc_a = list(accumulate(h[::-1], max))[::-1]

if acc_t != T or acc_a != A:
	print(0)
	exit()

mi = [min(t, a) for t, a in zip(T, A)]

ans = 1
for i in range(N):
	if h[i] == 0:
		ans *= mi[i]
		ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
t = na()
a = na()
mod = 10**9+7

ans = 1
for i in range(n):
    tt,aa = 1,1
    if i == 0 or t[i-1] < t[i]:
        tt = t[i]
    if i == n-1 or a[i+1] < a[i]:
        aa = a[i]
    if tt > a[i] or aa > t[i]:
        print(0)
        exit()
    p = min(t[i],a[i]) - max(tt,aa) + 1
    ans = ans*p%mod

print(ans)

Submission status: Accepted

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

ans = 1
mod = 10**9 + 7
inf = float('inf')

for i in range(n-1):
    if A[i] == A[i+1]:
        A[i] = -A[i]
    if T[n-i-1] == T[n-i-2]:
        T[n-i-1] = -T[n-i-1]

for t,a in zip(T,A):
    if t < 0 and a < 0:
        ans *= min(-t,-a)
        ans %= mod
    elif t < 0:
        if -t < a:
            ans *= 0
    elif a < 0:
        if -a < t:
            ans *= 0
    elif t != a:
        ans *= 0
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
T=list(map(int,input().split()))
A=list(map(int,input().split()))
cand=[-1]*N
cand2=[-1]*N
flag=1
ans=1
p=10**9+7
for i in range(N):
    if i==0:
        cand[i]=T[i]
    else:
        if T[i]!=T[i-1]:
            cand[i]=T[i]
for i in range(N-1,-1,-1):
    if i==N-1:
        cand2[i]=A[i]
    else:
        if A[i]!=A[i+1]:
            cand2[i]=A[i]
#print(cand)
#print(cand2)

ans=1
for i in range(N):
    if (cand[i]==-1)and(cand2[i]==-1):
        ans=(ans*min(T[i],A[i]))%p
    elif (cand[i]==-1):
        if T[i]<cand2[i]:
            ans=0
    elif (cand2[i]==-1):
        if A[i]<cand[i]:
            ans=0
    else:
        if cand[i]!=cand2[i]:
            ans=0
print(ans)


#print(flag,cand)
"""
lmax=[0]*N
rmax=[0]*N
for i in range(N):
    if i==0:
        lmax[i]=cand[i]
        rmax[N-1-i]=cand[N-1-i]
    else:
        if cand[i]==-1:
            lmax[i]=lmax[i-1]
        else:
            lmax[i]=cand[i]

        if cand[N-i-1]==-1:
            rmax[N-i-1]=rmax[N-i]
        else:
            rmax[N-i-1]=cand[N-i-1]
#print(lmax,rmax)
for i in range(N):
    if cand[i]==-1:
        ans=(ans*min(A[i],T[i]))%p
if flag==0:
    print("0")
else:
    print(ans%p)
"""

Submission status: Accepted

Solution code:


n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
a = [[-1,-1] for i in range(n)]
b = [[-1,-1] for i in range(n)]

nowa = 0
nowb = 0
for i in range(n):
    if(aa[i]>nowa):
        a[i] = [aa[i],aa[i]]
        nowa = aa[i]
    else:
        a[i] = [1,aa[i]]
    if(bb[n-1-i]>nowb):
        b[n-1-i] = [bb[n-1-i],bb[n-1-i]]
        nowb = bb[n-1-i]
    else:
        b[n-1-i] = [1,nowb]
#print(a)
#print(b)
for i in range(n):
    a[i][0] = max(a[i][0],b[i][0])
    a[i][1] = min(a[i][1],b[i][1])
    
ans = 1
for i in range(n):
    ans *= max(0, a[i][1]-a[i][0]+1)
    ans%= 1000000007
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
N,*L = map(int, open(0).read().split())
MOD = 10**9+7
T = L[:N]
A = L[N:]
h = [0]*N
p = -1
for i in range(N):
  if p != T[i]:
    p = T[i]
    h[i] = T[i]
p = -1
for i in range(N-1,-1,-1):
  if p!=A[i]:
    if h[i]!=0 and h[i]!=A[i]:
      print(0)
      sys.exit()
    p = A[i]
    h[i] = A[i]
xt = list(accumulate(h,max))
xa = list(accumulate(h[::-1],max))[::-1]
if xt!=T or xa!=A:
  print(0)
  sys.exit()
B = [min(t,a) for t,a in zip(T,A)]
ans = 1
for i in range(N):
  if h[i]==0:
    ans *= B[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()))
exact = [0] * N # 高さが確定した場所
seem = [0] * N # 高さが確定しない場所のあり得る最大値

cur = 0
for i in range(len(T)):
  if cur < T[i]:
    exact[i] = T[i]
    cur = T[i]
  else:
    seem[i] = cur
    
cur = 0
for i in range(len(A)-1,-1,-1):
  if cur < A[i]:
    if exact[i] != 0 and exact[i] != A[i]: # 既に記録された確定数値が今回の値と異なる場合
      print(0)
      exit(0)
    if exact[i] == 0 and seem[i] < exact[i]:# ここで確定させる数値が高橋くん的にあり得るかチェック
      print(0)
      exit(0)
    exact[i] = A[i]
    cur = A[i]
  else:
    # 既に確定している数値が今入れようとしている数値より大きければNG
    if exact[i] != 0 and exact[i] > cur:
      print(0)
      exit(0)
    seem[i] = min(seem[i],cur)
    
DIV = 10 ** 9 + 7
ans = 1
for i in range(N):
  if exact[i] != 0: # 確定数値があれば場合の数は変わらない
    continue
  else:
    ans *= seem[i]
    ans %= DIV

print(ans)

Submission status: Accepted

Solution code:
MOD = 10 **9 + 7
INF = 10 ** 10

def main():
    n = int(input())
    T = list(map(int,input().split()))
    A = list(map(int,input().split()))
    mountainT = [-1] * n
    mountainT[0] = T[0]
    for i in range(1,n):
        if T[i - 1] != T[i]:
            mountainT[i] = T[i]
    
    mountainA = [-1] * n
    mountainA[-1] = A[-1]
    for i in range(n - 1,0,-1):
        if A[i - 1] != A[i]:
            mountainA[i - 1] = A[i - 1]
    
    ans = 1
    for i in range(n):
        if mountainA[i] != -1 and mountainT[i] != -1:
            if mountainT[i] != mountainA[i]:
                ans = 0
                break
        elif mountainA[i] != -1:
            if mountainA[i] > T[i]:
                ans = 0
                break
        elif mountainT[i] != -1:
            if mountainT[i] > A[i]:
                ans = 0
                break
        else:
            ans *= min(T[i],A[i])
            ans %= MOD
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
t=[int(j) for j in input().split()]
a=[int(j) for j in input().split()]
tmp=0
l=[]
for i in t:
    if tmp<i:
        l.append(-i)
        tmp=i
    else:
        l.append(i)
tmp=0
ans=1
mod=10**9+7
for i in range(n)[::-1]:
    if tmp<a[i]:
        tmp=a[i]
        if l[i]<a[i]:
            if l[i]>0 or -l[i]!=a[i]:
                print(0)
                exit()
    else:
        if l[i]>0:
            ans=(ans*min(a[i],l[i]))%mod
print(ans)

Submission status: Accepted

Solution code:
def solve(n, aaa, bbb):
    # 最大値が更新された=その山の高さは決定
    max_heights = [0] * n
    fixed = [False] * n
    MOD = 10 ** 9 + 7

    h = 0
    for i, a in enumerate(aaa):
        if h != a:
            max_heights[i] = a
            fixed[i] = True
        else:
            max_heights[i] = a
        h = a
        
    h = 0
    for i, b in reversed(list(enumerate(bbb))):
        if h != b:
            if max_heights[i] < b:
                return 0
            if fixed[i] and max_heights[i] != b:
                return 0
            max_heights[i] = b
            fixed[i] = True
        else:
            max_heights[i] = min(max_heights[i], b)
        h = b

    ans = 1
    for h, f in zip(max_heights, fixed):
        if f:
            continue
        ans = ans * h % MOD
    return ans


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
print(solve(n, aaa, bbb))

Submission status: Accepted

Solution code:
import sys


input = sys.stdin.readline




def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())



mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N=II()

t=acinput()
a=acinput()

st = [[] for i in range(N)]
st[0]=[t[0],t[0]]
for i in range(1,N):
    if t[i-1]<t[i]:
        st[i]=[t[i],t[i]]
    else:
        st[i]=[1,st[i-1][1]]
        

sa = [[] for i in range(N)]
sa[N-1] = [a[N-1], a[N-1]]
for i in reversed(range(N-1)):
    if a[i] > a[i+1]:
        sa[i] = [a[i], a[i]]
    else:
        sa[i] = [1,sa[i+1][1]]

def diff(x):
    return x[1]-x[0]
res=1
for i in range(N):
    
    x=max(sa[i])-min(st[i])+1
    y=max(st[i])-min(sa[i])+1
    #print(x,y,np.diff(sa))
    if x<=0 or y<=0:
        res=0
        break
    res=res* min(x,y,diff(sa[i])+1,diff(st[i])+1)
    res=res%mod
    
print(res%mod)

#print(st)
#print(sa)

Submission status: Accepted

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

#0:高さ確定 1:高さそれ以下
for i in range(0,N):
    if i==0:
        T[i]=(T[i],0)
    else:
        h,query=T[i-1]
        if h==T[i]:
            T[i]=(T[i],1)
        else:
            T[i]=(T[i],0)

for i in range(0,N):
    if i==0:
        A[-i-1]=(A[-i-1],0)
    else:
        h,query=A[-i]
        if h==A[-i-1]:
            A[-i-1]=(A[-i-1],1)
        else:
            A[-i-1]=(A[-i-1],0)

ans=1
for i in range(0,N):
    h1,q1=T[i]
    h2,q2=A[i]
    if q1==0:
        if q2==0:
            if h1!=h2:
                ans=0
        else:
            if h1>h2:
                ans=0
    else:
        if q2==0:
            if h2>h1:
                ans=0
        else:
            ans=(ans*min(h1,h2))%mod

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
info1=list(map(int,input().split()))
info2=list(map(int,input().split()))
ans=0
if info1[-1]!=info2[0]: #お互いの最高記録が一致していないのは矛盾
    print(ans)
else:
    a=[[0,info1[0]]]
    highest=info1[0]
    for i in range(1,N):
        if highest<info1[i]:
            highest=info1[i]
            a.append([0,info1[i]])
        else:
            a.append([1,highest])
    b=[[0,info2[-1]]]
    highest=info2[-1]
    for i in range(1,N):
        if highest<info2[-(i+1)]:
            highest=info2[-(i+1)]
            b.append([0,info2[-(i+1)]])
        else:
            b.append([1,highest])
    flag=True
    c=[]
    for i in range(N): #二つの範囲を組み合わせる
        if a[i][0]==0 and b[-(i+1)][0]==0:
            if a[i][1]==b[-(i+1)][1]:
                c.append([0,a[i][1]])
            else:
                flag=False
                break
        elif a[i][0]==1 and b[-(i+1)][0]==1:
            c.append([1,min(a[i][1],b[-(i+1)][1])])
        else:
            if a[i][0]==0:
                if a[i][1]<=b[-(i+1)][1]:
                    c.append([0,a[i][1]])
                else:
                    flag=False
                    break
            else:
                if b[-(i+1)][1]<=a[i][1]:
                    c.append([0,b[-(i+1)][1]])
                else:
                    flag=False
                    break
    if flag:
        mod=10**9+7
        ans=1
        for i in range(N):
            if c[i][0]==1:
                ans=(ans*c[i][1])%mod
        print(ans)
    else:
        print(0)

Submission status: Accepted

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

H = [0] * N
_H = [INF] * N
pre_h = 0
for i, h in enumerate(T):
  if h != pre_h:
    H[i] = h
    pre_h = h
  else:
    _H[i] = min(_H[i], h)

pre_h = 0
for i, h in enumerate(A[::-1], 1):
  if h != pre_h:
    if (H[-i] > 0 and H[-i] != h) or _H[-i] < h:
      print(0)
      quit()
    H[-i] = h
    pre_h = h
  else:
    _H[-i] = min(_H[-i], h)

ans = 1
for h, _h in zip(H, _H):
  if h == 0:
    ans *= _h
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = list(map(int, input().split(" ")))
A = list(map(int, input().split(" ")))
h = [0 for i in range(N)]
mod = 10 ** 9 + 7

h[0] = T[0]
for i in range(N - 1):
    if T[i] < T[i + 1]:
        h[i + 1] = T[i + 1]
    else:
        h[i + 1] = -T[i + 1]

if h[N - 1] == 0:
    h[N - 1] = A[N - 1]
else:
    if -h[N - 1] >= A[N - 1]:
        h[N - 1] = A[N - 1]
    elif h[N - 1] != A[N - 1]:
        h[N - 1] = 0

for i in range(1, N):
    if A[i - 1] > A[i]:
        if -h[i - 1] >= A[i - 1]:
            h[i - 1] = A[i - 1]
        elif h[i - 1] != A[i - 1]:
            h[i - 1] = 0
    else:
        if h[i - 1] < 0:
            h[i - 1] = -min(-h[i - 1], A[i - 1])


ans = 1
for hi in h:
    if hi <= 0:
        ans *= -hi
        ans %= mod

print(ans)

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()
for i in range(1, N):
    if T[i-1] != T[i] and T[i] > A[i]:
        print(0)
        exit()
    if A[N-i-1] != A[N-i] and A[N-i-1] > T[N-i-1]:
        print(0)
        exit()
h = [-1] * N
h[0] = T[0]
h[-1] = A[-1]
for i in range(1, N-1):
    if T[i] != T[i-1]:
        h[i] = T[i]
    if A[i] != A[i+1]:
        h[i] = A[i]
ans, mod = 1, 10**9+7
for i in range(1, N-1):
    if h[i] == -1:
        ans = ans * min(A[i], T[i]) % 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
if max(A)!=max(T):
    print(0)
    exit()
l = [True] + [False]*(n-1)
r = [False]*(n-1) + [True]

for i in range(1, n):
    if T[i] != T[i-1]:
        l[i] = True
for i in range(n-1):
    if A[i] != A[i+1]:
        r[i] = True
for i in range(n):
    if r[i] and A[i]>T[i]:
        print(0)
        exit()       
ans = 1
for i in range(n):
    if l[i]==False and r[i]==False:
        ans *= min(T[i], A[i])
        ans %= mod
print(ans%mod)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

tt = []
prev = 0
for e in t:
    if e > prev:
        tt.append([e, e])
        prev = e
    else:
        tt.append([1, e])

aa = []
prev = 0
for e in a[::-1]:
    if e > prev:
        aa.append([e, e])
        prev = e
    else:
        aa.append([1, e])
aa = aa[::-1]

ans = 1
for et, ea in zip(tt, aa):
    mn = max(et[0], ea[0])
    mx = min(et[1], ea[1])
    ans *= max(0, mx - mn + 1)
    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

if max(t) != max(a):
    print(0)
    exit()


def f(li, rev):
    if rev:
        li = li[::-1]

    cnts = [0] * n
    cands = [0] * n
    mx = 0
    cnt = 0
    for i, e in enumerate(li):
        if e > mx:
            cnts[i] = 1
            cands[i] = e
            cnt = e
            mx = e
        else:
            cnts[i] = cnt

    if rev:
        cnts = cnts[::-1]
        cands = cands[::-1]

    return cnts, cands


t_cnt, t_cand = f(t, False)
a_cnt, a_cand = f(a, True)

for e1, e2 in zip(a, t_cand):
    if e2 > e1:
        print(0)
        exit()

ans = 1
for e1, e2 in zip(t_cnt, a_cnt):
    ans *= min(e1, e2)
    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

if max(t) != max(a):
    print(0)
    exit()


def f(li, rev):
    if rev:
        li = li[::-1]

    cnts = [0] * n
    cands = [0] * n
    mx = 0
    cnt = 0
    for i, e in enumerate(li):
        if e > mx:
            cnts[i] = 1
            cands[i] = e
            cnt = e
            mx = e
        else:
            cnts[i] = cnt

    if rev:
        cnts = cnts[::-1]
        cands = cands[::-1]

    return cnts, cands


t_cnt, t_cand = f(t, False)
a_cnt, a_cand = f(a, True)

for e1, e2 in zip(t, a_cand):
    if e2 > e1:
        print(0)
        exit()

ans = 1
for e1, e2 in zip(t_cnt, a_cnt):
    ans *= min(e1, e2)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))


if a[0]>b[0] or b[n-1]>a[n-1]: print(0);sys.exit()
elif n<=2: print(1);sys.exit()

ans=1
for i in range(1,n-1):
    if a[i]==a[i-1] and b[i]==b[i+1]:
        ans=ans*min(a[i],b[i])%mod
    else:
        if a[i]!=a[i-1] and a[i]>b[i]: print(0);sys.exit()
        if b[i]!=b[i+1] and b[i]>a[i]: print(0);sys.exit()
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
T = list(map(int, input().split(' ')))
A = list(map(int, input().split(' ')))


prev = -1
candidates_t = [-1 for _ in range(N)]
for i in range(N):
    if T[i] != prev:
        candidates_t[i] = T[i]

    prev = T[i]


prev = -1
candidates_a = [-1 for _ in range(N)]
for i in range(N-1, -1, -1):
    if A[i] != prev:
        candidates_a[i] = A[i]

    prev = A[i]

ret = 1
for i in range(N):
    if candidates_t[i] == -1 and candidates_a[i] == -1:
        ret *= min(T[i], A[i])
        ret %= 10**9 + 7

    elif candidates_t[i] == -1:
        if T[i] < candidates_a[i]:
            ret *= 0

    elif candidates_a[i] == -1:
        if A[i] < candidates_t[i]:
            ret *= 0

    elif candidates_t[i] != candidates_a[i]:
        ret *= 0


print(ret)

Submission status: Accepted

Solution code:
import sys

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

MOD = 10 ** 9 + 7

t_max = [0] * N
t_min = [1] * N
tmp = -1
for i in range(N):
    t = T[i]
    if t > tmp:
        t_max[i] = t
        t_min[i] = t
    elif t == tmp:
        t_max[i] = t
    else:
        print(0)
        sys.exit(0)
    tmp = t

a_max = [0] * N
a_min = [1] * N
tmp = -1
for i in range(N-1, -1, -1):
    a = A[i]
    if a > tmp:
        a_max[i] = a
        a_min[i] = a
    elif a == tmp:
        a_max[i] = a
    else:
        print(0)
        sys.exit(0)
    tmp = a

answer = 1
for i in range(N):
    tmp = min(t_max[i], a_max[i]) - max(t_min[i], a_min[i])
    if tmp < 0:
        print(0)
        sys.exit(0)
    answer *= tmp + 1
    answer %= MOD

print(answer)

Submission status: Accepted

Solution code:
import sys

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

MOD = 10 ** 9 + 7

t_max = [0] * N
t_min = [1] * N
tmp = -1
for i in range(N):
    t = T[i]
    if t > tmp:
        t_max[i] = t
        t_min[i] = t
    elif t == tmp:
        t_max[i] = t
    else:
        print(0)
        sys.exit(0)
    tmp = t

a_max = [0] * N
a_min = [1] * N
tmp = -1
for i in range(N-1, -1, -1):
    a = A[i]
    if a > tmp:
        a_max[i] = a
        a_min[i] = a
    elif a == tmp:
        a_max[i] = a
    else:
        print(0)
        sys.exit(0)
    tmp = a

answer = 1
for i in range(N):
    tmp = min(t_max[i], a_max[i]) - max(t_min[i], a_min[i])
    if tmp < 0:
        answer = 0
        break
    answer *= tmp + 1
    answer %= MOD

print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
T = LI()
A = LI()
flg = [0] * n
pre = 0
for i in range(n):
    if T[i] > pre:
        flg[i] = 1
        pre = T[i]

pre = 0
for j in range(n - 1, -1, -1):
    if A[j] == pre:
        if flg[j]:
            if T[j] > A[j]:
                print(0)
                exit()
        else:
            T[j] = min(T[j], A[j])
    else:
        if flg[j] and T[j] != A[j]:
            print(0)
            exit()
        else:
            if A[j] > T[j]:
                print(0)
                exit()
            else:
                T[j] = A[j]
                flg[j] = 1
                pre = A[j]

ans = 1
for k in range(n):
    if flg[k] == 0:
        ans = ans * T[k] % 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()))
Tmax = (0,-1)
Amax = (0,-1)
h = [0]*N
not_confirmed = [True]*N
for i in range(N):
    if Tmax[0] < T[i]:
        Tmax = (T[i],i)
        not_confirmed[i] = False
    if Amax[0] < A[N-1-i]:
        Amax = (A[N-1-i],N-1-i)
        not_confirmed[N-1-i] = False
    h[i] = min(T[i],A[i])
if (Amax[1] < Tmax[1]) or (Tmax[0] != Amax[0]):
    print(0)
    exit()

ans = 1
for i in range(N):
    ans *= h[i] if not_confirmed[i] else 1
    ans %= mod
print(ans)