Submission #719812

#	Time	Username	Problem	Language	Result	Execution time	Memory
719812		Boomyday	Fancy Fence (CEOI20_fancyfence)	Pypy 3	100 / 100	272 ms	42776 KiB

fancyfence

from collections import deque

MOD = 1000000007
inv2 = pow(2, MOD-2, MOD)

def calc_num(w, h):
    return w*(w+1)*h*(h+1)*inv2*inv2 % MOD


sc = 0
N = int(input())

h, w = [],[]

h += list(map(int, input().split())) +[0]
w += list(map(int, input().split())) +[0]

st = deque([[0,0]])
# H, W
for i in range(N+1):
    st.append([h[i], w[i]])
    while True:
        #print(st, sc)

        try:
            if st[-1][0] > st[-2][0]:
                break
            elif st[-1][0] == st[-2][0]:
                st[-2][1] += st[-1][1]
                st.pop()
            else:
                if min(st[-1][0], st[-3][0])== st[-3][0]:
                    sc += calc_num(st[-2][1], st[-2][0]) - calc_num(st[-2][1], st[-1][0])
                    sc %= MOD
                    st[-2][0] = st[-1][0]
                else:
                    sc += calc_num(st[-2][1], st[-2][0]) - calc_num(st[-2][1], st[-3][0])
                    sc %= MOD
                    strd = st.pop()
                    st[-2][1] += st[-1][1]
                    st.pop()
                    st.append(strd)

        except:
            break

print(sc)

• 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