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 |
|
|
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 |