Submission #659586

#	Time	Username	Problem	Language	Result	Execution time	Memory
659586		beaconmc	Fancy Fence (CEOI20_fancyfence)	Pypy 3	100 / 100	170 ms	44284 KiB

fancyfence

n = int(input())
h = list(map(int, input().split()))
w = list(map(int, input().split()))


sussies = [list(i) for i in zip(h,w)]
stack = []

def rect(a,b):
    return a*(a+1)*b*(b+1)//4

def comb():
    if len(stack)>1 and stack[-1][0] == stack[-2][0]:
        a = stack.pop()[1]
        stack[-1][1] += a

ans = 0
for i in sussies:
    if not stack:
        stack.append(i)
    else:
        while stack[-1][0] > i[0]:
            
            if len(stack)==1:
                ans += rect(stack[-1][0],stack[-1][1])-rect(i[0],stack[-1][1])
                stack[-1][0] = i[0]
            else:
                sus = max(stack[-2][0], i[0])
                ans += rect(stack[-1][0],stack[-1][1])-rect(sus,stack[-1][1])
                stack[-1][0] = sus
                comb()
        stack.append(i)
        comb()

while len(stack) != 1:
    sus = stack[-2][0]
    ans += rect(stack[-1][0],stack[-1][1])-rect(sus,stack[-1][1])
    stack[-1][0] = sus
    comb()

ans += rect(stack[0][0], stack[0][1])

print(ans%1000000007)
                

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27