Submission #1167417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167417		kiennguyendinh	Fancy Fence (CEOI20_fancyfence)	Pypy 3	100 / 100	190 ms	92640 KiB

fancyfence

MOD = 10**9 + 7

def solve():
    import sys
    input = sys.stdin.readline
    N = int(input().strip())
    h = list(map(int, input().split()))
    w = list(map(int, input().split()))
    h = [0] + h
    w = [0] + w
    P = [0]*(N+1)
    for i in range(1, N+1):
        P[i] = P[i-1] + w[i]
    L = [0]*(N+1)
    stack = []
    for i in range(1, N+1):
        while stack and h[stack[-1]] >= h[i]:
            stack.pop()
        L[i] = stack[-1] if stack else 0
        stack.append(i)
    R = [0]*(N+1)
    stack = []
    for i in range(N, 0, -1):
        while stack and h[stack[-1]] > h[i]:
            stack.pop()
        R[i] = stack[-1] if stack else N+1
        stack.append(i)
    
    ans = 0
    for i in range(1, N+1):
        L_sum = P[i] - (P[L[i]] if L[i] >= 0 else 0)
        R_sum = P[R[i]-1] - P[i-1]
        H_i = (L_sum * R_sum - (w[i]*w[i]) + (w[i]*(w[i]+1)//2)) % MOD
        F_h = (h[i] * (h[i] + 1) // 2) % MOD
        ans = (ans + F_h * H_i) % MOD
        
    print(ans % MOD)

if __name__ == '__main__':
    solve()

Compilation message (stdout)

Compiling 'fancyfence.py'...

=======
  adding: __main__.pyc (deflated 40%)

=======

• 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