Submission #909537


Source Code Expand

class UnionFind:
    def __init__(self,size):
        self.parent=range(size)
        self.tree_num=size
        self.tree_w=[1]*size
        self.rank=[0]*size

    def findset(self,x):
        if self.parent[x]==x:
            return x
        else:
            self.parent[x]=self.findset(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x=self.findset(x)
        y=self.findset(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.parent[x]=y
            self.tree_num-=1
            self.tree_w[y]+=self.tree_w[x]
        else:
            self.parent[y]=x
            self.tree_num-=1
            self.tree_w[x]+=self.tree_w[y]
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def tree_weight(self,x):
        return self.tree_w[self.findset(x)]

n=int(raw_input())
a=map(int,raw_input().split())
p=[0]*(n+1)
for i in xrange(n):
    p[a[i]]=i

uf=UnionFind(n+1)
ans=0
for j in xrange(n,0,-1):
    i=p[j]
    tmp=1
    if i>=1 and a[i]<a[i-1]:
        tmp*=uf.tree_weight(a[i-1])+1
        uf.unite(a[i],a[i-1])
    if i<n-1 and a[i]<a[i+1]:
        tmp*=uf.tree_weight(a[i+1])+1
        uf.unite(a[i],a[i+1])
    ans+=j*tmp
print(ans)

Submission Info

Submission Time
Task B - Minimum Sum
User roto_37
Language Python (2.7.6)
Score 400
Code Size 1298 Byte
Status AC
Exec Time 742 ms
Memory 25116 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 13
Set Name Test Cases
Sample example0, example1, example2
All corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2
Case Name Status Exec Time Memory
corner0 AC 669 ms 25116 KB
corner1 AC 666 ms 25116 KB
corner2 AC 16 ms 2696 KB
corner3 AC 667 ms 25116 KB
example0 AC 16 ms 2696 KB
example1 AC 16 ms 2696 KB
example2 AC 16 ms 2696 KB
maxrand0 AC 728 ms 25116 KB
maxrand1 AC 731 ms 25116 KB
maxrand2 AC 742 ms 25116 KB
rand0 AC 17 ms 2696 KB
rand1 AC 16 ms 2696 KB
rand2 AC 16 ms 2696 KB