結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー |
![]() |
提出日時 | 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
ソースコード
def f3(n,rs,ls)rs3=n.times.map{0}ls3=n.times.map{0}rs.each{|e|rs3[e[0]]=1rs3[e[1]]=-1}ls.each{|e|ls3[e[1]]=1ls3[e[0]]=-1}rc=0lc=0ans=0n.times{|i|if rs3[i]==0if ls3[i]==1ans+=rcelsif ls3[i]==-1lc-=1endendif ls3[i]==0if rs3[i]==1ans+=lcelsif rs3[i]==-1rc-=1endendif rs3[i]==1 && ls3[i]==1ans+=rc+1+lcrc+=1lc+=1endif rs3[i]==-1 && ls3[i]==-1rc-=1lc-=1end#p [i,rc,lc,ans]}return ansenddef fadd(tree,l,r,p1,p2,add)if r==ltree[p1]+=addelsem=(r+l)/2if (p2<=m)fadd(tree,l,m,p1*2+1,p2,add)elsefadd(tree,m+1,r,p1*2+2,p2,add)endtree[p1]+=addendenddef fsum(tree,l,r,p1,r1)if r1<lreturn 0elsif 0<=l && r<=r1return tree[p1]elseans=0m=(l+r)/2ans+=fsum(tree,l,m,p1*2+1,r1)ans+=fsum(tree,m+1,r,p1*2+2,r1)return ansendreturn 0enddef f(n2,n,ds)tree=n2.times.map{0}n=n-1ans=0while ds.empty? ==false dod1=ds.shiftwhile d1.empty? ==false dod2=d1.shiftd=d2[0]no=d2[1]fadd(tree,0,n,0,no,d)if d==-1t=fsum(tree,0,n,0,no)if t>0ans+=tendendend#p [tree,ans,no,d]endreturn ansendn2=131071#n2=31tree=n2.times.map{0}n=gets.to_ixs=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 dsrs.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-1ls.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