Submission #639825

#	Time	Username	Problem	Language	Result	Execution time	Memory
639825		Joshc	Fancy Fence (CEOI20_fancyfence)	Pypy 3	100 / 100	652 ms	59916 KiB

fancyfence

import sys, collections
input = sys.stdin.readline

n = int(input())
h = [*map(int, input().split())]
w = [*map(int, input().split())]
parent = [i for i in range(n)]
sz = [1] * n
ans = 0

def root(x):
    if x == parent[x]:
        return parent[x]
    parent[x] = root(parent[x])
    return parent[x]

def join(x, y):
    global ans
    x, y = root(x), root(y)
    if x == y:
        return
    ans += w[x]*w[y]
    if sz[x] > sz[y]:
        x, y = y, x
    parent[x] = y
    sz[y] += sz[x]
    w[y] += w[x]

d = collections.defaultdict(list)
for i in range(n):
    d[h[i]].append(i)

res = 0
added = [False]*n
heights = sorted(d.keys(), reverse=True) + [0]
for height, nextheight in zip(heights, heights[1:]):
    for i in d[height]:
        ans += w[i]*(w[i]+1)//2
        added[i] = True
        if i and added[i-1]:
            join(i-1, i)
        if i+1 < n and added[i+1]:
            join(i, i+1)
    res += ans * (height*(height+1)//2 - nextheight*(nextheight+1)//2)
    res %= 1000000007
print(res)
        

• 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