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
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self, start, goal):
        grid = self.grid
        cy, cx = start
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        warp = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if (i, j) not in move and (i != 0 or j != 0):
                    warp.append((i, j))
        # print(warp)
        d = deque()
        wd = deque()
        self.set(start[1], start[0], 0)
        d.append((0, cx, cy))
        while (d or wd):
            # print(len(d), len(wd))
            if d:
                cc, cx, cy = d.popleft()
            else:
                cc, cx, cy = wd.popleft()
            # print(cc, cx, cy)
            if self.get(cx, cy) < cc:
                continue
            for dx, dy in move:

                nx, ny = dx + cx, dy + cy
                if self.getgrid(nx, ny) == "#":
                    continue
                if self.get(nx, ny) > cc:
                    self.set(nx, ny, cc)
                    d.append((cc, nx, ny))

            for dx, dy in warp:
                nx, ny = dx + cx, dy + cy
                if nx < 0 or nx > self.w + 1 or ny < 0 or ny > self.h + 1:
                    continue
                if self.getgrid(nx, ny) == "#":
                    continue
                if self.get(nx, ny) > cc + 1:
                    self.set(nx, ny, cc + 1)
                    wd.append((cc + 1, nx, ny))
        # print(warp)
        # self.show()
        # self.showsomejoin(self.grid)
        ans = self.get(goal[1], goal[0])
        if ans == INF:
            print(-1)
            return
        else:
            print(ans)
            return

def solve():
    n = getN()
    anums = getList()
    bnums = getList()
    if n == 1:
        if anums[0] == bnums[0]:
            print(1)
        else:
            print(0)
        return
    fixed = [0 for i in range(n)]
    ans = [INF for i in range(n)]
    fixed[0] = 1
    fixed[-1] = 1
    ans[0] = anums[0]
    ans[-1] = bnums[-1]
    for i in range(n-1):
        if anums[i] != anums[i+1]:
            if fixed[i+1] and ans[i+1] != anums[i+1]:
                print(0)
                return
            if ans[i+1] < anums[i+1]:
                print(0)
                return
            fixed[i+1] = 1
        ans[i+1] = min(ans[i+1], anums[i+1])

    for i in range(n-1):
        if bnums[i] != bnums[i+1]:
            if fixed[i] and ans[i] != bnums[i]:
                print(0)
                return
            if ans[i] < bnums[i]:
                print(0)
                return
            fixed[i] = 1
        ans[i] = min(ans[i], bnums[i])

    a = 1
    for i in range(n):
        if not fixed[i]:
            a *= ans[i]
            a %= MOD

    print(a)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
# 最大値と最小値を調べておいて、それを掛け合わせる

n = int(input())
left_heights = list(map(int, input().split()))
right_heights = list(map(int, input().split()))

minimum = [-1] * n
maximum = [10**10] * n

l_max = 0
for i in range(n):
    if left_heights[i] > l_max:
        maximum[i] = left_heights[i]
        minimum[i] = left_heights[i]
    else:
        maximum[i] = left_heights[i]
        minimum[i] = 1
    l_max = left_heights[i]

r_max = 0
for i in reversed(range(n)):
    if right_heights[i] > r_max:
        if minimum[i] <= right_heights[i] <= maximum[i]:
            maximum[i] = right_heights[i]
            minimum[i] = right_heights[i]
        else:
            print(0)
            exit()
    else:
        if r_max >= minimum[i]:
            maximum[i] = min(right_heights[i], maximum[i])
        else:
            print(0)
            exit()

    r_max = right_heights[i]

mod = 10**9 + 7
ans = 1
for mi, ma in zip(minimum, maximum):
    ans *= ma - mi + 1
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
# 最大値と最小値を調べておいて、それを掛け合わせる

n = int(input())
left_heights = list(map(int, input().split()))
right_heights = list(map(int, input().split()))

minimum = [-1] * n
maximum = [10**10] * n

l_max = 0
for i in range(n):
    if left_heights[i] > l_max:
        maximum[i] = left_heights[i]
        minimum[i] = left_heights[i]
    else:
        maximum[i] = left_heights[i]
        minimum[i] = 1
    l_max = left_heights[i]

r_max = 0
for i in reversed(range(n)):
    if right_heights[i] > r_max:
        if minimum[i] <= right_heights[i] <= maximum[i]:
            maximum[i] = right_heights[i]
            minimum[i] = right_heights[i]
        else:
            print(0)
            exit()
    else:
        if r_max >= minimum[i]:
            maximum[i] = min(right_heights[i], maximum[i])
            minimum[i] = max(1, minimum[i])  # 多分この行は不要
        else:
            print(0)
            exit()

    r_max = right_heights[i]

mod = 10**9 + 7
ans = 1
for mi, ma in zip(minimum, maximum):
    ans *= ma - mi + 1
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    A = read_list()
    B = read_list()
    S = [10 ** 9] * N
    T = [1] * N

    r = 0
    for i ,a in enumerate(A):
        S[i] = min(S[i], a)
        if r < a:
            T[i] = max(T[i], a)
        r = a
    
    r = 0
    for j, b in enumerate(B[::-1]):
        i = N - 1 - j
        S[i] = min(S[i], b)
        if r < b:
            T[i] = max(T[i], b)
        r = b

    res = 1
    for s, t in zip(S, T):
        res *= max(0, s - t + 1)
        res %= mod
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

# 解説AC
if n <= 2:
    print(int(t == a))
    exit()

ans = 1
for i in range(1, n - 1):
    if ((t[i - 1] < t[i] and t[i] > a[i])
        or (a[i] > a[i + 1] and t[i] < a[i])):
            print(0)
            break
    elif t[i - 1] == t[i] and a[i] == a[i + 1]:
        ans = ans * min(t[i], a[i]) % mod
else:
    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, l, r = 1, 0, n - 1
for i in range(1, n):
    if t[i] == t[i - 1]:
        ans = ans * t[i] % mod
    if t[i] == a[i]:
        l = i
        break
for i in range(n - 1)[::-1]:
    if a[i] == a[i + 1]:
        ans = ans * a[i] % mod
    if t[i] == a[i]:
        r = i
        break

if not t[l] == max(t) == max(a) == a[r]:
    print(0)
else:
    print(ans * pow(t[l], max(r - l - 1, 0), mod) % 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

# 解説AC
if n <= 2:
    print(int(t == a))
    exit()

ans = 1
for i in range(1, n - 1):
    ht, ha = 0, 0
    if t[i - 1] < t[i] and a[i] > a[i + 1]:
        if t[i] != a[i]:
            print(0)
            break
    if t[i - 1] < t[i]:
        if t[i] > a[i]:
            print(0)
            break
    elif a[i] > a[i + 1]:
        if t[i] < a[i]:
            print(0)
            break
    else:
        ans = ans * min(t[i], a[i]) % mod
else:
    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:
    print(int(t == a))
    exit()
for i in range(1, n - 1):
    ht, ha = 0, 0
    if t[i - 1] < t[i] and a[i] > a[i + 1]:
        if t[i] != a[i]:
            print(0)
            break
    elif t[i - 1] < t[i]:
        if t[i] > a[i]:
            print(0)
            break
    elif a[i] > a[i + 1]:
        if t[i] < a[i]:
            print(0)
            break
    else:
        ans = ans * min(t[i], a[i]) % mod
else:
    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, l, r = 1, 0, n - 1
for i in range(1, n):
    if t[i] == t[i - 1]:
        ans = ans * t[i] % mod
    if t[i] == a[i]:
        l = i
        break
for i in range(n - 1)[::-1]:
    if a[i] == a[i + 1]:
        ans = ans * a[i] % mod
    if t[i] == a[i]:
        r = i
        break

if t[l] != max(t) or a[r] != max(a) or max(t) != max(a):
    print(0)
else:
    print(ans * pow(t[l], max(r - l - 1, 0), mod) % mod)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n = ni()
    l = na()
    r = na()

    res_l = [[0, False] for _ in range(n)]
    res_r = [[0, False] for _ in range(n)]

    checker = True

    tmp = 0
    for i, li in enumerate(l):
        if li > tmp:
            res_l[i] = li, True
        elif li == tmp:
            res_l[i][0] = tmp
        else:
            checker = False
            break
        tmp = li

    tmp = 0
    for i, ri in enumerate(reversed(r)):
        if ri > tmp:
            res_r[-1 - i] = ri, True
        elif ri == tmp:
            res_r[-1 - i][0] = tmp
        else:
            checker = False
            break
        tmp = ri

    res = [[0, False] for _ in range(n)]

    for i in range(n):
        if res_l[i][1] and res_r[i][1]:
            if res_l[i][0] != res_r[i][0]:
                checker = False
                break
            else:
                res[i] = res_l[i][0], True
        elif res_l[i][1] or res_r[i][1]:
            t_num = res_l[i][0] if res_l[i][1] else res_r[i][0]
            f_num = res_l[i][0] if not res_l[i][1] else res_r[i][0]
            if t_num > f_num:
                checker = False
                break
            else:
                res[i] = t_num, True
        else:
            res[i] = min(res_l[i][0], res_r[i][0]), False

    ans = 1
    for num, flg in res:
        if flg:
            continue
        ans *= num
        ans %= MOD

    print(ans if checker else 0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, 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, insort, insort_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
#from decimal import *

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

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


ma = -1
for i, a in enumerate(A[::-1]):
	if ma < a:
		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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, 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, insort, insort_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
#from decimal import *

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

mountain = [0]*N

h_t = 0
for i in range(N):
	if T[i] != h_t:
		h_t = T[i]
		mountain[i] = T[i]

#print(mountain)
h_a = 0
for i in range(N-1, -1, -1):
	if A[i] != h_a:
		h_a = A[i]
		if mountain[i] == 0:
			mountain[i] = A[i]
		elif mountain[i] != A[i]:
			print(0)
			exit()
	elif h_a < mountain[i]:
		print(0)
		exit()

ans = 1
for i in range(N):
	if mountain[i] == 0:
		ans *= min(T[i], A[i])
		ans %= mod

print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007

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

L1 = [0 for _ in range(N)]
R1 = [0 for _ in range(N)]
L2 = [0 for _ in range(N)]
R2 = [0 for _ in range(N)]

tmp1 = 1
tmp2 = 1

for i in range(N):
    if tmp1 < T[i]:
        L1[i] = T[i]
        R1[i] = T[i]
        tmp1 = T[i]
    elif tmp1 == T[i]:
        L1[i] = 1
        R1[i] = tmp1
    else:
        print(0)
        break
    if tmp2 < A[~i]:
        L2[~i] = A[~i]
        R2[~i] = A[~i]
        tmp2 = A[~i]
    elif tmp2 == A[~i]:
        L2[~i] = 1
        R2[~i] = tmp2
    else:
        print(0)
        break
else:
    res = 1
    for i in range(N):
        res *= max(min(R1[i], R2[i]) - max(L1[i], L2[i]) + 1, 0)
        res %= MOD
    print(res)

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 -> の向きでみて増加している場合と初項は対応するAの要素はa >= t
# 同様に、A <- の向きでみて増加している場合と初項は対応するTの要素はa <= t


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

if max(A) != max(cap) or max(T) != max(cap):
  print(0)
  exit()

capm = max(cap)

cm = cap.count(capm)

ans = 1

if cm > 2:
  for _ in range(cm - 2):
    ans *= capm
    ans %= MOD

for i in range(1, n - 1):
  if cap[i] == capm:
    break
  if cap[i - 1] == cap[i] and cap[i] <= cap[i + 1]:
    if cap[i] < cap[i + 1] or not cap[i + 1] == capm: 
      ans *= cap[i]
      ans %= MOD

for i in reversed(range(1, n - 1)):
  if cap[i] == capm:
    break
  if cap[i + 1] == cap[i] and cap[i] <= cap[i - 1]:
    if cap[i] < cap[i - 1] or not cap[i - 1] == capm: 
      ans *= cap[i]
      ans %= MOD
      
print(ans)

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

kakutei=[-1]*n
kakutei[0]=t[0]
kakutei[-1]=a[-1]
for i in range(n-1):
    if t[i]<t[i+1]:
        kakutei[i+1]=t[i+1]
    if a[-2-i]>a[-1-i]:
        kakutei[-2-i]=a[-2-i]
# print(kakutei)
ans=1
if n==1 and t[0]!=a[0]:
    ans=0
for i in range(n):
    if kakutei[i]>min(t[i],a[i]):
        ans=0

for i in range(n):
    if kakutei[i]==-1:
        ans*=min(t[i],a[i])
    ans%=mod

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())

mod = 10**9 + 7


def main():

    N = in_n()
    A = in_nl()
    T = in_nl()

    if N == 1:
        if A[0] == T[0]:
            print(1)
        else:
            print(0)
        exit()

    yama = [(0, 0)] * N
    yama[0] = (A[0], A[0])

    for i in range(1, N):
        pre_min_h, pre_max_h = yama[i - 1]
        now_h = A[i]

        if pre_max_h < now_h:
            now_min_h = now_h
            now_max_h = now_h
        else:
            now_min_h = 1
            now_max_h = pre_max_h

        yama[i] = (now_min_h, now_max_h)

    yama[-1] = (T[-1], T[-1])

    for i in range(N - 2, -1, -1):

        now_min_h, now_max_h = yama[i]
        pre_h = T[i + 1]
        now_h = T[i]

        if now_h > pre_h:
            if now_min_h <= now_h <= now_max_h:
                now_min_h = now_h
                now_max_h = now_h
            else:
                print(0)
                exit()
        else:
            now_max_h = min(now_max_h, now_h)

        yama[i] = (now_min_h, now_max_h)

    ans = 1
    for i in range(N):
        ans *= (yama[i][1] - yama[i][0] + 1)
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

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
mountain = [T[0]]
for i in range(1, N):
    if T[i] > T[i - 1]:
        mountain.append(T[i])
    else:
        mountain.append(-T[i])
ans = 1
if N == 1:
    if T[0] != A[0]:
        print(0)
        exit()
for i in range(N - 1, -1, -1):
    if i == N - 1:
        if (A[i] > mountain[i]) & (mountain[i] > 0):
            ans = 0
            break
        mountain[i] = A[i]
    elif mountain[i] <= 0:
        if A[i] > A[i + 1]:
            if - mountain[i] >= A[i]:            
                mountain[i] = A[i]
            else:
                ans = 0
                break
        else:
            mountain[i] = -min(A[i], -mountain[i])
    else:
        if A[i] >= mountain[i]:
            continue
        else:
            ans = 0
            break
    if mountain[i] < 0:
        ans = (- ans * mountain[i]) % mod
print(ans)

Submission status: Accepted

Solution code:
# 単調増加したらそこの山の高さは決まる。それ以外ならある高さ以内で自由に取れる。t,aで矛盾したら0
# 一人ずつ考えた
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 1
MOD = 10**9 + 7
a_fixed = [-1] * n
t_fixed = [-1] * n

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

a_fixed[-1] = a[-1]
for i in range(n - 2, -1, -1):
    if a[i] > a[i + 1]:
        a_fixed[i] = a[i]


for i in range(n):
    if t_fixed[i] != -1 and a_fixed[i] != -1:
        if t_fixed[i] != a_fixed[i]:
            print(0)
            exit()

    # 片方の制約を満たしているか
    elif t_fixed[i] != -1:
        if t_fixed[i] > a[i]:
            print(0)
            exit()
    elif a_fixed[i] != -1:
        if a_fixed[i] > t[i]:
            print(0)
            exit()
    else:
        ans *= min(a[i], t[i])
        ans %= MOD
# print(fixed)
print(ans)

Submission status: Accepted

Solution code:
# 単調増加したらそこの山の高さは決まる。それ以外ならある高さ以内で自由に取れる。t,aで矛盾したら0
# 一人ずつ考えた
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 1
MOD = 10**9 + 7
a_fixed = [-1] * n
t_fixed = [-1] * n

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

a_fixed[-1] = a[-1]
for i in range(n - 2, -1, -1):
    if a[i] > a[i + 1]:
        a_fixed[i] = a[i]


for i in range(n):
    if t_fixed[i] != -1 and a_fixed[i] != -1:
        if t_fixed[i] != a_fixed[i]:
            print(0)
            exit()
    elif t_fixed[i] != -1:
        if t_fixed[i] > a[i]:
            print(0)
            exit()
    elif a_fixed[i] != -1:
        if a_fixed[i] > t[i]:
            print(0)
            exit()
    else:
        ans *= min(a[i], t[i])
        ans %= MOD
# print(fixed)
print(ans)

# if t[-1] != a[0]:
#     print(0)
#     exit()
# # # 最初の山チェック
# # if t[0] > a[0]:
# #     print(0)
# #     exit()
# # 最後の山の照合
# if fixed[-1] != -1:
#     if fixed[-1] != a[-1]:
#         print(0)
#         exit()
# fixed[-1] = a[-1]

# for i in range(n - 2, -1, -1):
#     if a[i] > a[i + 1]:  # この状況下でしか照合されないので最初の山の照合を取り逃している！
#         if fixed[i] == -1:
#             fixed[i] = a[i]
#         else:
#             if fixed[i] != a[i]:
#                 print(0)
#                 exit()
# for i in range(n):
#     if fixed[i] != -1:
#         continue
#     else:
#         ans *= min(a[i], t[i])
#         ans %= MOD
# # print(fixed)
# print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    r = [[1, 10 ** 9 + 1] for _ in range(n)]
    r[0][0], r[0][1] = t[0], t[0]

    for i, x in enumerate(t[1:], 1):
        if t[i - 1] < t[i]:
            r[i][0], r[i][1] = t[i], t[i]
        else:
            r[i][0], r[i][1] = 1, t[i]

    s = [[1, 10 ** 9 + 1] for _ in range(n)]
    a_rev = a[::-1]
    s[0][0], s[0][1] = a[0], a[0]

    for i, x in enumerate(a_rev[1:], 1):
        if a_rev[i - 1] < a_rev[i]:
            s[i][0], s[i][1] = a_rev[i], a_rev[i]
        else:
            s[i][0], s[i][1] = 1, a_rev[i]

    s = s[::-1]
    ans = 1

    for i in range(n):
        lower = max(r[i][0], s[i][0])
        upper = min(r[i][1], s[i][1])
        d = max(upper - lower + 1, 0)
        ans *= d
        ans %= MOD

    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()))
k = [-1 for i in range(n)]
now = 0
if t[-1] != a[0]:
    print(0)
    exit()
for i in range(n):
    if t[i] > now:
        k[i] = t[i]
        now = t[i]

now = 0
for i in reversed(range(n)):
    if k[i] == -1:
        if a[i] > now:
            k[i] = a[i]
            now = a[i]
    if k[i] != -1:
        if a[i] > now:
            now = a[i]
        if k[i] > now:
            print(0)
            exit()

ans = 1
l = 0
cou = 0
mod = 10**9 + 7
for i in range(n):
    if k[i] != -1 and l == 0:
        l = k[i]
    elif k[i] != -1 and l != 0:
        ans *= pow(min(l,k[i]),cou,mod)
        ans %= mod
        l = k[i]
        cou = 0
    elif k[i] == -1:
        cou += 1
print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
rec,cer=tuple(map(int,input().split())),tuple(map(int,input().split()))
table=[-1]*n#確定した山ならば、その高さ。-1は未確定
table[0]=rec[0]
table[-1]=cer[-1]
if rec[-1]!=cer[0]:print(0);exit()#同じ山々を踏破してるので全体の最大値が違うのは矛盾
for i in range(1,n):
    if rec[i]>rec[i-1]:
        if table[i]!=-1 and table[i]!=rec[i]:print(0);exit()
        table[i]=rec[i]
        if cer[i]<table[i]:print(0);exit()
    if cer[n-i-1]>cer[n-i]:
        if table[n-i-1]!=-1 and table[n-i-1]!=cer[n-i-1]:print(0);exit()
        table[n-i-1]=cer[n-i-1]
        if rec[n-i-1]<table[n-i-1]:print(0);exit()
#各人について、「記録が真に増加したなら、その山の高さは確定する」は真。もう一人の情報と矛盾しないかも見る。
start,f=0,0
now=0
won=0
for i in range(n):
    now=max(now,table[i])
    won=max(won,table[-i-1])
    if now!=rec[i] or won!=cer[-i-1]:print(0);exit()
if now!=won:print(0);exit()
#念のため二人の情報と矛盾しないかシミュレーションしておく
ans=1
for i,v in enumerate(table):
    if v==-1 and f==0:
        start=i
        f=1    #[start,?)に連続して高さ未定義の山が続く
    if v!=-1 and f:
        kosuu=i-start #[start,v)であることがわかったので個数は左
        f=0
        ans=ans*pow(min(v,table[start-1]),kosuu,mod)%mod
        #高さ未定義の山が続く群に対して、そいつらは両隣に高さを抑えられるので、場合の数はこうなる
        #table[0]とtable[n-1]については高さが必ず確定するので、両隣に確定済みの山は必ず存在する

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mt = [1]*n
Mt = [None]*n
ma = [1]*n
Ma = [None]*n
v = -1
for i,h in enumerate(t):
    if h>v:
        mt[i] = Mt[i] = h
    else:
        Mt[i] = h
    v = h
v = -1
for i,h in enumerate(reversed(a)):
    if h>v:
        ma[n-1-i] = Ma[n-1-i] = h
    else:
        Ma[n-1-i] = h
    v = h
ans = 1
M = 10**9+7
for i in range(n):
    val = min(Mt[i], Ma[i]) - max(mt[i], ma[i]) + 1
    if val<=0:
        ans = 0
        break
    ans *= val
    ans %= M
print(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    T=LI()
    A=LI()
    inf=10**9+1
    M1=[inf]*N
    M2=[inf]*N
    m1=[1]*N
    m2=[1]*N
    
    now=1
    for i in range(N):
        t=T[i]
        if t>now:
            m1[i]=t
            M1[i]=t
            now=t
        else:
            M1[i]=now
            
    now=1
    for i in range(N-1,-1,-1):
        t=A[i]
        if t>now:
            m2[i]=t
            M2[i]=t
            now=t
        else:
            M2[i]=now
            
    ans=1
    for i in range(N):
        M=min(M1[i],M2[i])
        m=max(m1[i],m2[i])
        if m>M:
            ans=0
            break
        else:
            ans=(ans*(M-m+1))%mod
            
    print(ans)
        
    
main()