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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@mt
def slv(N, T, A):

    ft = [False] * N
    ft[0] = True

    for i in range(1, N):
        if T[i-1] < T[i]:
            ft[i] = True

    fa = [False] * N
    fa[-1] = True
    for i in range(N-2, 0, -1):
        if A[i] > A[i+1]:
            fa[i] = True
    
    H = []
    for i in range(N):
        if ft[i] and fa[i]:
            if T[i] != A[i]:
                return 0
        elif ft[i]:
            if T[i] > A[i]:
                return 0
        elif fa[i]:
            if T[i] < A[i]:
                return 0
        else:
            H.append(min(T[i], A[i]))

    M = Mod(10**9+7)
    ans = 1
    for h in H:
        ans = M.mul(ans, h)
    return ans


def main():
    N = read_int()
    T = read_int_n()
    A = read_int_n()
    print(slv(N, T, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Min = [1] * N
Max = [float("inf")] * N
tp = 0
for i, t in enumerate(T):
    if t != tp:
        Min[i] = max(Min[i], t)
    Max[i] = min(Max[i], t)
    tp = t
ap = 0
for i, a in zip(range(N-1, -1, -1), A[::-1]):
    if a != ap:
        Min[i] = max(Min[i], a)
    Max[i] = min(Max[i], a)
    ap = a
ans = 1
for mi, ma in zip(Min, Max):
    ans = ans * max(ma-mi+1, 0) % mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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

ans = 1
for i in range(1, n - 1):
    x = t[i] if t[i] > t[i - 1] else 1
    y = a[i] if a[i] > a[i + 1] else 1
    ans = ans * max(0, min(t[i], a[i]) - max(x, y) + 1) % mod

print(ans if a[0] == t[-1] else 0)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

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

if n == 1:
    if t[0] != a[0]:
        print(0)
    else:
        print(1)
    exit()

max_list = [10**9+1] * n
min_list = [0] * n

max_list[0] = t[0]
min_list[0] = t[0]
for i in range(1, n):
    if t[i] > t[i-1]:
        max_list[i] = t[i]
        min_list[i] = t[i]
    else:
        max_list[i] = t[i]
        min_list[i] = 1

max_list[n-1] = a[n-1]
min_list[n-1] = a[n-1]
for i in range(n-2, -1, -1):
    if a[i] > a[i+1]:
        if min_list[i] <= a[i] <= max_list[i]:
            max_list[i] = a[i]
            min_list[i] = a[i]
        else:
            print(0)
            exit()
    else:
        if max_list[i] == min_list[i]:
            if max_list[i] > a[i]:
                print(0)
                exit()
        else:
            max_list[i] = min(max_list[i], a[i])

ans = 1
for i in range(n):
    ans = (ans * (max_list[i] - min_list[i] + 1)) % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
free = [0] * N
f = 0
if N == 1:
  if t[0] == a[0]:
    print(1)
  else:
    print(0)
  exit(0)
if max(a) != max(t):
  print(0)
  exit(0)
for i in range(1, N - 1):
  if t[i - 1] == t[i]:
    free[i] = t[i]
  if t[i - 1] != t[i]:
    if t[i] > a[i]:
      f = 1
      break
  if a[i] != a[i + 1]:
    if a[i] > t[i]:
      f = 1
      break
for i in range(N - 2, 0, -1):
  if a[i + 1] == a[i] and t[i - 1] == t[i]:
    free[i] = min(t[i], a[i])
  else:
    free[i] = 0
res = 1
if f:
  print(0)
  exit(0)
for i in range(N):
  res *= max(1, free[i])
  res %= mod
print(res)

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()))
mod = 10**9+7

decided = [False for _ in range(N)]
H = [0 for _ in range(N)]

pre = -1
for i, t in enumerate(T):
    if t != pre:
        decided[i] = True
    H[i] = t
    pre = t

ok = True
pre = -1
for i in reversed(range(N)):
    a = A[i]
    if a != pre:
        if decided[i] and H[i] != a:
            ok = False
            break
        decided[i] = True
    elif decided[i]:
        if H[i] > a:
            ok = False
            break
    if not decided[i]:
        H[i] = min(H[i], a)
    pre = a

if ok:
    ans = 1
    for i in range(N):
        if not decided[i]:
            ans = ans * H[i] % mod
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    T = list(map(int, input().split()))
    A = list(map(int, input().split()))
    if T[0] <= A[0] and A[N-1] <= T[N-1]:
        ans = 1
    else:
        return 0
    MOD = int(1e9) + 7
    for i in range(1, N-1):
        t = (T[i] == T[i-1])
        a = (A[i] == A[i+1])
        if not(t) and not(a):
           if T[i] != A[i]:
               return 0
        elif not(t) and a:
            if A[i] < T[i]:
                return 0
        elif t and not(a):
            if T[i] < A[i]:
                return 0
        else:
            ans *= min(T[i], A[i])
            ans %= MOD
    
    return ans

if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:

def main():
    n = int(input())
    t= list(map(int,input().split()))
    a= list(map(int,input().split()))


    maxh = t[:]
    minflag = [0 for _ in range(n)]

    if t[-1] != a[0]:
        return 0
    else:
        maxflag = t[-1]
    maxh[0] = t[0]
    minflag[0] = 1

    for i in range(1,n):
        if t[i] > t[i-1]:
            minflag[i] = 1

    maxh[-1] = a[-1]
    minflag[-1] = 1
    if a[-1] != t[-1]:
        for i in range(n-2,-1,-1):
            if a[i] > t[i]:
                return 0
            elif a[i] == t[i]:
                if a[i] != maxflag:
                    return 0
                else:
                    minflag[i] = 1
                    break
            maxh[i] = a[i]
            if a[i] > a[i+1]:
                minflag[i] = 1

    res = 1
    for i in range(n):
        if not minflag[i]:
            res *= maxh[i]
            res %= (10**9+7)
    return res % (10**9+7)

print(main())

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
result = 1
for i in range(n):
    h_max, h_min = min(t[i], a[i])+1, 1
    if i != 0:
        if t[i-1] < t[i]:
            h_min = t[i]
    else:
        h_min = t[0]

    if i != n-1:
        if a[i] > a[i+1]:
            h_min = max(a[i], h_min)
    else:
        h_min = max(a[i], h_min)
    result = result * max(h_max - h_min, 0) % (10**9+7)
print(result)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
result = 1
for i in range(n):
    h_max, h_min = min(t[i], a[i])+1, 1

    if i != 0:
        if t[i-1] < t[i]:
            h_min = t[i]
    else:
        h_min = t[0]

    if i != n-1:
        if a[i] > a[i+1]:
            h_min = a[i]
    else:
        h_min = max(a[n-1], h_min)


    result = result * max(h_max - h_min, 0) % (10**9+7)
print(result)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
result = 1
for i in range(n):
    h_max, h_min = min(t[i], a[i])+1, 1

    if i != n-1:
        if a[i] > a[i+1]:
            h_min = a[i]
    else:
        h_min = a[n-1] 

    if i != 0:
        if t[i-1] < t[i]:
            h_min = t[i]
    else:
        h_min = t[0]


    result = result * max(h_max - h_min, 0) % (10**9+7)
print(result)

Submission status: Accepted

Solution code:
n=int(input())
s=list(map(int,input().split()))
a=list(map(int,input().split()))
uselist=[0 for _ in range(n)]
cnt=0
for i in range(n):
    if cnt!=s[i]:
        cnt=s[i]
        uselist[i]=cnt
    else:
        continue

###
uselist1=[0 for _ in range(n)]
count=0
for i in range(n):
    if count!=a[n-1-i]:
        count=a[n-1-i]
        uselist1[n-1-i]=count
    else:
        continue

###
flag=True
anslist=[0 for _ in range(n)]
for i in range(n):
    if uselist[i]!=0 and uselist1[i]!=0:
        if uselist[i]!=uselist1[i]:
            flag=False
            break
        else:
            anslist[i]=uselist[i]
    elif uselist[i]!=0 and uselist1[i]==0:
        anslist[i]=uselist[i]
    elif uselist[i]==0 and uselist1[i]!=0:
        anslist[i]=uselist1[i]
    else:
        continue
for i in range(n):
    if anslist[n-1-i]>a[n-1-i]:
        flag=False
        break

        
        
ans=1
checker=0
index=0
i=1
if flag:
    anslist.append(0)
    anslist.insert(0,0)
    while i<=n:
        if index==0 and anslist[i]!=0:
            checker=anslist[i]
            i+=1
            
        elif index==0 and anslist[i]==0:
            index+=1
            i+=1
            
        elif index!=0 and anslist[i]!=0:
            checker=min(checker,anslist[i])
            use=1
            for _ in range(index):
                use=(use*checker)%(10**9+7)
            ans=(ans*(use))%(10**9+7)
            checker=anslist[i]
            index=0
            i+=1
        elif index!=0 and anslist[i]==0:
            index+=1
            i+=1
    print(ans%(10**9+7))
if not flag:
    print(0)

Submission status: Accepted

Solution code:
n = int(input())
tn = [0]+[int(i) for i in input().split()]+[0]
an = [0]+[int(i) for i in input().split()]+[0]
ans = 1
mod = 10**9+7

for i in range(1,n+1):
  if tn[i-1] < tn[i] and an[i] > an[i+1]:
    ans *= int(tn[i] == an[i])
  elif tn[i-1] < tn[i] and an[i] == an[i+1]:
    ans *= int(tn[i] <= an[i])
  elif tn[i-1] == tn[i] and an[i] > an[i+1]:
    ans *= int(tn[i] >= an[i])
  else:
    ans *= min(an[i],tn[i])
    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()))

B=[]
C=[]
B.append([0,T[0],T[0]])
C.append([N-1,A[-1],A[-1]])

if N>1:
  for i in range(1,N):
    B.append([i,T[i],T[i] if T[i]>T[i-1] else 1])
  for i in range(N-2,-1,-1):
    C.append([i,A[i],A[i] if A[i]>A[i+1] else 1])
C.sort()
#print(B)
#print(C)

ans=1
for i in range(N):
  d=min(B[i][1],C[i][1])-max(B[i][2],C[i][2])+1
  ans*=d if d>=0 else 0
  ans%=mod
print(ans)

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()))
t=[0]+t+[t[-1]]
a=[a[0]]+a+[0]
ans=1
#print(t,a)
for i in range(n):
    if t[i]<t[i+1]:
        if a[i+1]<t[i+1]:
            ans=0
            break
    if a[i]>a[i+1]:
        if t[i]<a[i]:
            ans=0
            break
    if t[-2]!=a[1]:
        ans=0
        break
    if t[i]==t[i+1] and a[i+1]==a[i+2]:
        ans=(ans*(min(t[i+1],a[i+1])))%(10**9+7)
print(ans)

Submission status: Accepted

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

h = [min(t[i],a[i]) for i in range(n)]
fixed = [False] * n
fixed[0] = True; fixed[n-1] = True

if a[n-1] > t[n-1] or t[0] > a[0]:
    print(0)
    sys.exit(0)
# takahashi check
for i in range(1,n):
    if t[i] > t[i-1]: 
        fixed[i] = True
        if t[i] > a[i]:
            print(0)
            sys.exit(0)
# aoki check
for i in range(n-2, -1, -1):
    if a[i] > a[i+1]:
        fixed[i] = True
        if a[i] > t[i]:
            print(0)
            sys.exit(0)

# calc ans
ans = 1
for i in range(n):
    if not fixed[i]:
        ans = ans * h[i] % (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()))


x = [1 for _ in range(N)]
for i in range(1, N):
    if i == 0:
        x[i] = 1
    elif T[i - 1] < T[i]:
        x[i] = 1
    else:
        x[i] = T[i]

y = [1 for _ in range(N)]
for i in range(N - 2, -1, -1):
    if i == N - 1:
        y[i] == 1
    if A[i] > A[i + 1]:
        y[i] = 1
    else:
        y[i] = A[i]

ans = 1

for i in range(N):
    ans = ans * min(x[i], y[i]) % int(1e9 + 7)


for x,y,t,a in zip(x,y,T,A):
    if x == 1 and t > a:
        ans = 0
    if y == 1 and t < a:
        ans = 0


print(ans)

Submission status: Accepted

Solution code:
n = int(input())
qs1 = list(map(int,input().split(" ")))
qs2 = list(map(int,input().split(" ")))
qs2.reverse()
ans = 1
MOD = 10** 9 + 7
num1 = 0
num2  = 0
qss = [[],[]]
for i,qs in enumerate([qs1,qs2]):
    qss[i].append((qs[0], 1))
    for t1,t2 in zip(qs[0:n-1],qs[1:n]):
        if t1 >t2:
            ans *= 0
        elif t1 == t2:
            qss[i].append((t2,0))
        else:
            qss[i].append((t2, 1))
# print(qss)
qss[1].reverse()
# print(qss)
for q1,q2 in zip(qss[0],qss[1]):
    qt1 = q1[1]
    qt2 = q2[1]
    num1 = q1[0]
    num2 = q2[0]
    if qt1 == 0 and qt2 == 0: #
        ans *= min(num1, num2)


    elif qt1 == 0 and qt2 == 1:
        if num1 >= num2:
            ans *= 1
        else:
            ans *= 0

    elif qt1 == 1 and qt2 == 0:
        if num2 >= num1:
            ans *= 1
        else:
            ans *= 0
    else:
        if num1 != num2:
            ans *= 0
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = list(map(int,input().split()))
A = list(map(int,input().split()))
T_min = [1]*N
T_min[0] = T[0]
for i in range(1,N):
  if T[i-1]<T[i]:
    T_min[i] = T[i]
A_min = [1]*N
A_min[N-1] = A[N-1]
for i in range(N-2,-1,-1):
  if A[i+1]<A[i]:
    A_min[i] = A[i]
M = [0]*N
M_min = [0]*N
for i in range(N):
  M[i] = min(T[i],A[i])
  M_min[i] = max(T_min[i],A_min[i])
ans = 1
mod = 10**9+7
for i in range(N):
  if M[i]<M_min[i]:
    ans = 0
  else:
    ans*=M[i]+1-M_min[i]
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
def init(lst):
    l = [lst[0]]
    r = [lst[0]]
    for i in range(1, len(lst)):
        if lst[i - 1] < lst[i]:
            l.append(lst[i])
            r.append(lst[i])
        else:
            l.append(1)
            r.append(lst[i])
    return l, r

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

l1, r1 = init(t)
a.reverse()
l2, r2 = init(a)
l2.reverse()
r2.reverse()

l3 = []
r3 = []
for i in range(n):
    if l2[i] <= r1[i] and l1[i] <= r2[i]:
        l = max(l1[i], l2[i])
        r = min(r1[i], r2[i])
        l3.append(l)
        r3.append(r)
    else:
        print(0)
        exit(0)

ans = 1
for i in range(n):
    ans *= r3[i] - l3[i] + 1
    ans %= 10 ** 9 + 7
print(ans)

Submission status: Accepted

Solution code:
def end():
    print(0)
    exit()

mod = 10**9+7
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
t1 = [0]*n
a1 = [0]*n
t1[0] = a1[-1] = 1

for i in range(1, n):
    if t[i-1] != t[i]:
        t1[i] = 1
    if a[n-1-i] != a[n-i]:
        a1[n-1-i] = 1

ans = 1
for i in range(n):
    if t1[i] and a1[i]:
        if t[i] != a[i]:
            end()
    elif t1[i]:
        if t[i] > a[i]:
            end()
    elif a1[i]:
        if t[i] < a[i]:
            end()
    else:
        ans *= min(t[i], a[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()))

H = [[1,10 ** 9] for _ in range(N)]

for i in range(N):
  if i == 0:
    hmin = T[i]
    hmax = T[i]
  elif T[i-1] < T[i]:
    hmin = T[i]
    hmax = T[i]
  else:
    hmin = 1
  H[i][0] = hmin
  H[i][1] = hmax
  #print(H)
for i in range(N-1,-1,-1):
  if i == N-1:
    hmin = A[i]
    hmax = A[i]
  elif A[i] > A[i+1]:
    hmax = A[i]
    hmin = A[i]
  else:
    hmin = 1
  H[i][0] = max(hmin,H[i][0])
  H[i][1] = min(hmax,H[i][1])
  #print(H)

#print(H)
ans = 1
for i in range(N):
  if H[i][1] < H[i][0]:
    print(0)
    exit()
  ans *= (H[i][1] - H[i][0] + 1)
  ans %= 10 ** 9 + 7
print(ans)

Submission status: Accepted

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

MOD = 10**9 + 7

fixed = [False] * N
fixed[0] = True

for i in range(1, N):
    if T[i] > T[i-1]:
        fixed[i] = True

ans = 1
for i in range(N-1, -1, -1):
    if A[i] > A[i+1] and A[i] > T[i]:
        print(0)
        exit()
    if fixed[i] is True and A[i] < T[i]:
        print(0)
        exit()
    if fixed[i] is False and A[i] == A[i+1]:
        ans *= min(A[i], T[i])
        ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Ts = list(map(int, input().split()))
As = list(map(int, input().split()))
c = 0
Hmax = [0]*N
Hmin = [1]*N
for i in range(N):
  T = Ts[i]
  Hmax[i] = T
  if T > c:
    Hmin[i] = T
    c = T
c = 0
for i in reversed(range(N)):
  A = As[i]
  Hmax[i] = min(Hmax[i], A)
  if A > c:
    Hmin[i] = max(Hmin[i], A)
    c = A
#print(Hmax)
#print(Hmin)
r = 1
for i in range(N):
  d = Hmax[i]-Hmin[i]+1
  if d < 0: d = 0
  r = r*d%1000000007
print(r)

Submission status: Accepted

Solution code:
def main():

    N = int(input())
    T = list(map(int, input().split()))
    A = list(map(int, input().split()))
    mod = pow(10, 9) + 7

    heightT = []
    for i in range(N):
        if i == 0:
            heightT.append([T[i], "exact"])
        else:
            if T[i] > T[i-1]:
                heightT.append([T[i], "exact"])
            elif T[i] == T[i-1]:
                heightT.append([T[i], "bound"])
            else:
                return 0
    heightA = []
    for i in range(N-1, -1, -1):
        if i == N-1:
            heightA.append([A[i], "exact"])
        else:
            if A[i+1] < A[i]:
                heightA.append([A[i], "exact"])
            elif A[i+1] == A[i]:
                heightA.append([A[i], "bound"])
            else:
                return 0
    heightA = heightA[::-1]

    ans = 1
    for i in range(N):
        if heightT[i][1] == "exact" and heightA[i][1] == "exact":
            if heightT[i][0] != heightA[i][0]:
                return 0
        elif heightT[i][1] == "exact" and heightA[i][1] == "bound":
            if heightT[i][0] > heightA[i][0]:
                return 0
        elif heightT[i][1] == "bound" and heightA[i][1] == "exact":
            if heightT[i][0] < heightA[i][0]:
                return 0
        else:
            ans *= min(heightT[i][0], heightA[i][0])
            ans %= mod
    return ans


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data1 = list(map(int, input().split()))
    data2 = list(map(int, input().split()))

    dp1 = [0 for i in range(num)]
    dp2 = [0 for i in range(num)]

    dp1[0] = 1
    for i in range(1, num):
        if data1[i] > data1[i - 1]:
            dp1[i] = 1
        # else:
        #     dp1[i] = data1[i]

    data2 = data2[::-1]
    dp2[0] = 1
    for i in range(1, num):
        if data2[i] > data2[i - 1]:
            dp2[i] = 1
        # else:
        #     dp1[i] = data1[i]
    dp2 = dp2[::-1]
    data2 = data2[::-1]

    ans = 1
    mod = 10 ** 9 + 7
    for i in range(num):
        if dp1[i] and dp2[i]:
            if data1[i] == data2[i]:
                pass
            else:
                ans *= 0
        elif dp1[i]:
            if data1[i] <= data2[i]:
                pass
            else:
                ans *= 0
        elif dp2[i]:
            if data2[i] <= data1[i]:
                pass
            else:
                ans *= 0
        else:
            ans *= min(data1[i], data2[i])
        ans %= mod

    print(ans)






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

t_list = [ int(v) for v in input().split() ]
a_list = [ int(v) for v in input().split() ]
a_list_reverse = list(reversed(a_list))

t_confirm_list = [t_list[0]] + [None for i in range(n-1)]
a_confirm_list = [a_list_reverse[0]] + [None for i in range(n-1)]


for i in range(n-1):
    if t_list[i]  < t_list[i+1]:
        t_confirm_list[i+1] = t_list[i+1]
    if a_list_reverse[i]  < a_list_reverse[i+1]:
        a_confirm_list[i+1] = a_list_reverse[i+1]

a_confirm_list.reverse()


mod = 10**9+7
ans = 1
for i in range(n):
    if a_confirm_list[i] != None and t_confirm_list[i] != None:
        if a_confirm_list[i] != t_confirm_list[i]:
            ans = 0
    elif a_confirm_list[i] == None and t_confirm_list[i] == None:
        ans *= min(a_list[i],t_list[i])
        ans %= mod
    elif a_confirm_list[i] is not None and a_confirm_list[i] > t_list[i]:
            ans = 0
    elif t_confirm_list[i] is not None and t_confirm_list[i] > a_list[i]:
            ans = 0

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#CODEFESTIVAL2016 qualC C

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
t = LI()
a = LI()
x = [0]*n
y = [0]*n
if a[0] != t[-1]:
    print(0)
    quit()
for i in range(1,n):
    if t[i] > t[i-1]:
        x[i] = 1
for i in range(1,n)[::-1]:
    if a[i] < a[i-1]:
        y[i-1] = 1
ans = 1
for i in range(1,n-1):
    if x[i] == 1 and y[i] == 1:
        if t[i] != a[i]:
            print(0)
            quit()
    elif x[i] == 1:
        if a[i] < t[i]:
            print(0)
            quit()
    elif y[i] == 1:
        if a[i] > t[i]:
            print(0)
            quit()
    else:
        ans *= min(t[i],a[i])
        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#CODEFESTIVAL2016 qualC C

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
t = LI()
a = LI()
x = [0]*n
y = [0]*n
if a[0] != t[-1]:
    print(0)
    quit()
for i in range(1,n):
    if t[i] > t[i-1]:
        x[i] = 1
for i in range(1,n)[::-1]:
    if a[i] < a[i-1]:
        y[i-1] = 1
ans = 1
for i in range(1,n-1):
    if x[i] == 1 and y[i] == 1:
        if t[i] != a[i]:
            print(0)
            quit()
        continue
    elif x[i] == 1:
        if a[i] >= t[i]:
            continue
        else:
            print(0)
            quit()
    elif y[i] == 1:
        if a[i] <= t[i]:
            continue
        else:
            print(0)
            quit()
    ans *= min(t[i],a[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 = [False]*N

height = [0]*N
height[0] = T[0]
exact[0] = True

for i in range(1,N):
    height[i] = T[i]
    exact[i] = T[i]>T[i-1]

if (exact[-1] and A[-1]!=height[-1]) or A[-1]>height[-1]:
    print(0)
    exit()

height[-1] = A[-1]
exact[-1] = True

for i in range(N-1):
    if A[i]>A[i+1]:
        if (exact[i] and A[i]!=height[i]) or A[i]>height[i]:
            print(0)
            exit()
        height[i]=A[i]
        exact[i]=True
    else:
        if exact[i] and A[i]<height[i]:
            print(0)
            exit()
        else:
            height[i]=min(height[i], A[i])

ans=1
mod=10**9+7
for e,h in zip(exact, height):
    if not e:
        ans=(ans*h)%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[-1] != A[0]:
    print(0)
    exit()

max_h = [1] * N

#max_h[0] = T[0]
#max_h[-1] = A[-1]

h = [None] * N
#Tから見ていく
for i in range(1,N-1):

        ht = ha = None
        if T[i] > T[i-1]:
            ht = T[i]
        if A[i] > A[i+1]:
            ha = A[i]

        if ht != None and ha != None:
            if ht == ha:
                h[i] = ht
            else:
                print(0) # 矛盾するので終わり
                exit()
        
        elif ht != None:
            if A[i] < ht:
                print(0) # 矛盾するので終わり
                exit()
            #h[i] = ht
        elif ha != None:
            if T[i] < ha:
                print(0) # 矛盾するので終わり
                exit()
            #h[i] = ha
        

        elif ht == None and ha == None:
            max_h[i] = min(T[i], A[i])


MOD = 10**9 + 7
def mul(a, b):
    return ((a % MOD) * (b % MOD)) % MOD
ans = 1
for i in range(N):
    ans = mul(ans, max_h[i])
    #ans *= max_h[i]

print(ans)

Submission status: Accepted

Solution code:
N=int(input());*T,=map(int,input().split());*A,=map(int,input().split());a=int(A[0]==T[-1])
for p,q,r,s in zip(T,T[1:],A[1:],A[2:]):
 if(p==q)&(r==s):a=a*min(q,r)%(10**9+7)
 elif(p!=q)&(q>r)|(r!=s)&(q<r):a*=0
print(a)

Submission status: Accepted

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

def f(s1, s2):
  a = s1[0]
  b = s1[1]
  c = s2[0]
  d = s2[1]
  if a>c:
    a,b,c,d = c,d,a,b
  if b<c:
    return [-1, -1]
  return [c, min(b,d)]

Mlist_T = [[1, 1] for i in range(N)]#第一要素は最小値、第二要素は最大値のリスト
Mlist_A = [[1, 1] for i in range(N)]
Mlist_T[0][0]=T[0]
Mlist_T[0][1]=T[0]
Mlist_A[N-1][0]=A[N-1]
Mlist_A[N-1][1]=A[N-1]
for i in range(1,N):
  if T[i-1] != T[i]:
    Mlist_T[i][0] = T[i]
  Mlist_T[i][1] = T[i]
for i in range(1,N):
  if A[N-1-(i-1)] != A[N-1-i]:
    Mlist_A[N-1-i][0] = A[N-1-i]
  Mlist_A[N-1-i][1] = A[N-1-i]
fl = True
M = []
for i in range(N):
  m = f(Mlist_T[i],Mlist_A[i])
  if m == [-1, -1]:
    fl = False
    print(0)
    break
  M.append(m)

if fl:

  r = 1000000007
  ss = 1

  for m in M:
    ss = (ss * (m[1]-m[0]+1))%r
  print(ss)

Submission status: Accepted

Solution code:
N=int(input())
T=list(map(int,input().split()))
A=list(map(int,input().split()))
Tr,Ar=[0]*N,[0]*N

ct,ca=0,0
for i in range(N):
    if T[i] > ct:
        ct=T[i]
        Tr[i]=[ct,ct]
    else:
        Tr[i]=[1,ct]

    if A[N-1-i] > ca:
        ca=A[N-1-i]
        Ar[N-1-i]=[ca,ca]
    else:
        Ar[N-1-i]=[1,ca]

MOD=1000000007
ans=1
for tr,ar in zip(Tr,Ar):
    l = max(tr[0],ar[0])
    r = min(tr[1],ar[1])
    if r<l:
        print(0)
        exit()
    ans = (ans*(r-l+1))%MOD
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N = int(input())
T = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

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

HA = [False] * N
for i in range(N - 1):
    if A[i] > A[i + 1]:
        HA[i] = True
HA[-1] = True

ans = 1
for ht, ha, t, a in zip(HT, HA, T, A):
    if ht and ha:
        ans *= 1 if t == a else 0
    elif ht:
        ans *= 1 if t <= a else 0
    elif ha:
        ans *= 1 if t >= a else 0
    else:
        ans = (ans * min(t, a)) % mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N = int(input())
T = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

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

HA = [False] * N
for i in range(N - 1):
    if A[i] > A[i + 1]:
        HA[i] = True
HA[-1] = True

ans = 1
for i in range(N):
    if HT[i] and HA[i]:
        ans *= 1 if T[i] == A[i] else 0
    elif HT[i]:
        ans *= 1 if T[i] <= A[i] else 0
    elif HA[i]:
        ans *= 1 if T[i] >= A[i] else 0
    else:
        ans = (ans * min(T[i], A[i])) % mod
    if ans == 0:
        break
print(ans)