結果

問題 No.742 にゃんにゃんにゃん 猫の挨拶
ユーザー horiesinitihoriesiniti
提出日時 2018-02-26 08:45:14
言語 Ruby
(3.4.1)
結果
AC  
実行時間 597 ms / 2,500 ms
コード長 1,692 bytes
コンパイル時間 54 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 24,320 KB
最終ジャッジ日時 2024-10-12 13:54:18
合計ジャッジ時間 4,104 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:99: warning: assigned but unused variable - tree
Syntax OK

ソースコード

diff #
プレゼンテーションモードにする

def f3(n,rs,ls)
rs3=n.times.map{0}
ls3=n.times.map{0}
rs.each{|e|
rs3[e[0]]=1
rs3[e[1]]=-1
}
ls.each{|e|
ls3[e[1]]=1
ls3[e[0]]=-1
}
rc=0
lc=0
ans=0
n.times{|i|
if rs3[i]==0
if ls3[i]==1
ans+=rc
elsif ls3[i]==-1
lc-=1
end
end
if ls3[i]==0
if rs3[i]==1
ans+=lc
elsif rs3[i]==-1
rc-=1
end
end
if rs3[i]==1 && ls3[i]==1
ans+=rc+1+lc
rc+=1
lc+=1
end
if rs3[i]==-1 && ls3[i]==-1
rc-=1
lc-=1
end
#p [i,rc,lc,ans]
}
return ans
end
def fadd(tree,l,r,p1,p2,add)
if r==l
tree[p1]+=add
else
m=(r+l)/2
if (p2<=m)
fadd(tree,l,m,p1*2+1,p2,add)
else
fadd(tree,m+1,r,p1*2+2,p2,add)
end
tree[p1]+=add
end
end
def fsum(tree,l,r,p1,r1)
if r1<l
return 0
elsif 0<=l && r<=r1
return tree[p1]
else
ans=0
m=(l+r)/2
ans+=fsum(tree,l,m,p1*2+1,r1)
ans+=fsum(tree,m+1,r,p1*2+2,r1)
return ans
end
return 0
end
def f(n2,n,ds)
tree=n2.times.map{0}
n=n-1
ans=0
while ds.empty? ==false do
d1=ds.shift
while d1.empty? ==false do
d2=d1.shift
d=d2[0]
no=d2[1]
fadd(tree,0,n,0,no,d)
if d==-1
t=fsum(tree,0,n,0,no)
if t>0
ans+=t
end
end
end
#p [tree,ans,no,d]
end
return ans
end
n2=131071
#n2=31
tree=n2.times.map{0}
n=gets.to_i
xs=n.times.map{gets.to_i-1}
xs2=n.times.map{|i|
[i,xs[i]]
}
rs=xs2.select{|e|
e[0]<=e[1]
}
ls=xs2.select{|e|
e[1]<=e[0]
}
rs2=xs2.select{|e|
e[0]<e[1]
}
ls2=xs2.select{|e|
e[1]<e[0]
}
ds=n.times.map{[]}
i=0
#p ds
rs.each{|e|
ds[e[0]]<<[1,i]
ds[e[1]]<<[-1,i]
i+=1
}
ans1=f(n2,n,ds)
ds=n.times.map{[0,0]}
s1=ls.size-1
ls.each{|e|
ds[e[0]]<<[1,s1]
ds[e[1]]<<[-1,s1]
s1-=1
}
ds.reverse!
ans2=f(n2,n,ds)
ans3=f3(n,rs2,ls2)
puts ans1+ans2+ans3
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0