Submission #13413181


Source Code Expand

Copy
# Studying https://atcoder.jp/contests/abc168/tasks/abc168_f

N,M = gets.split.map(&:to_i)
縦線 = N.times.map{ gets.split.map(&:to_i) }
横線 = M.times.map{ gets.split.map(&:to_i) }

経線 = 縦線.map{|_,_,c| c }.uniq.sort
緯線 = 横線.map{|d,| d }.uniq.sort

GW = 経線.size+1 # 大外で壁になる線分の外側に1マス確保する。牛さんがそこにいる可能性もある。
GH = 緯線.size+1
HI = lambda{|横,下げ=false| # 0 番目のマス目の右側に 0 番目の縦線が配置される関係から、基本的に線分の座標は右へ、下へ切り上げられる。
	i = 経線.bsearch_index{|_| 横<=_ }||経線.size
	i1 = 下げ && 経線[i] != 横 ? 1 : 0
	next i-i1
}
VI = lambda{|縦,下げ=false|
	j = 緯線.bsearch_index{|_| 縦<=_ }||緯線.size
	j1 = 下げ && 緯線[j] != 縦 ? 1 : 0
	next j-j1
}
GI = lambda{|横,縦,下げ=false|
	next VI[縦,下げ]*GW + HI[横,下げ]
}

面積 = lambda{|gi|
	b,r = gi.divmod(GW)
	next Float::INFINITY unless (1...経線.size).include?(r) && (1...緯線.size).include?(b)
	next (経線[r]-経線[r-1]) * (緯線[b]-緯線[b-1])
}

縦線 = 縦線.inject(Array.new(経線.size){ [] }){|_,(a,b,c)|
	_[HI[c]] << [VI[a],VI[b,true]]
	next _
}
横線 = 横線.inject(Array.new(緯線.size){ [] }){|_,(d,e,f)|
	_[VI[d]] << [HI[e],HI[f,true]]
	next _
}

右? = lambda{|gi|
	b,r = gi.divmod(GW)
	next r+1 < GW && ! 縦線[r].any?{|s,e| b-1 < e && s < b }
}
左? = lambda{|gi|
	b,r = gi.divmod(GW)
	next 0 < r && ! 縦線[r-1].any?{|s,e| b-1 < e && s < b }
}
下? = lambda{|gi|
	b,r = gi.divmod(GW)
	next b+1 < GH && ! 横線[b].any?{|s,e| r-1 < e && s < r }
}
上? = lambda{|gi|
	b,r = gi.divmod(GW)
	next 0 < b && ! 横線[b-1].any?{|s,e| r-1 < e && s < r }
}

area = 0
Cow = GI[0,0]
Qd = [false]*(GW*GH)
Qd[Cow] = true;
Q = [Cow]
while at = Q.shift
	area += 面積[at]
	(puts'INF'; exit) if area.infinite?

	(Q<<at+1;  Qd[at+1]  = true) if 右?[at] && ! Qd[at+1]
	(Q<<at-1;  Qd[at-1]  = true) if 左?[at] && ! Qd[at-1]
	(Q<<at+GW; Qd[at+GW] = true) if 下?[at] && ! Qd[at+GW]
	(Q<<at-GW; Qd[at-GW] = true) if 上?[at] && ! Qd[at-GW]
end

p area

Submission Info

Submission Time
Task F - . (Single Dot)
User ds14050
Language Ruby (2.7.1)
Score 600
Code Size 2217 Byte
Status
Exec Time 1460 ms
Memory 22892 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
Subtask1 600 / 600 sample_01.txt, sample_02.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub1_26.txt, sub1_27.txt, sub1_28.txt, sub1_29.txt, sub1_30.txt, sub1_31.txt, sub1_32.txt, sub1_33.txt, sub1_34.txt, sub1_35.txt, sub1_36.txt, sub1_37.txt, sub1_38.txt, sub1_39.txt, sub1_40.txt, sub1_41.txt, sub1_42.txt, sub1_43.txt, sub1_44.txt, sub1_45.txt, sub1_46.txt, sub1_47.txt, sub1_48.txt, sub1_49.txt, sub1_50.txt, sub1_51.txt, sub1_52.txt, sub1_53.txt, sub1_54.txt, sub1_55.txt, sub1_56.txt, sub1_57.txt, sub1_58.txt, sub1_59.txt, sub1_60.txt, sub1_61.txt, sub1_62.txt, sub1_63.txt, sub1_64.txt, sub1_65.txt, sub1_66.txt, sub1_67.txt, sub1_68.txt, sub1_69.txt, sub1_70.txt, sub1_71.txt, sub1_72.txt, sub1_73.txt, sub1_74.txt, sub1_75.txt, sub1_76.txt, sub1_77.txt, sub1_78.txt, sub1_79.txt, sub1_80.txt, sub1_81.txt, sub1_82.txt, sub1_83.txt, sub1_84.txt, sub1_85.txt, sub1_86.txt, sub1_87.txt, sub1_88.txt, sub1_89.txt, sub1_90.txt, sub1_91.txt, sub1_92.txt, sub1_93.txt, sub1_94.txt
Case Name Status Exec Time Memory
sample_01.txt 53 ms 14524 KB
sample_02.txt 52 ms 14300 KB
sub1_01.txt 59 ms 16888 KB
sub1_02.txt 60 ms 15728 KB
sub1_03.txt 54 ms 15308 KB
sub1_04.txt 56 ms 14764 KB
sub1_05.txt 66 ms 19812 KB
sub1_06.txt 58 ms 15508 KB
sub1_07.txt 55 ms 15640 KB
sub1_08.txt 54 ms 14348 KB
sub1_09.txt 57 ms 15564 KB
sub1_10.txt 63 ms 20296 KB
sub1_11.txt 54 ms 14472 KB
sub1_12.txt 56 ms 14408 KB
sub1_13.txt 54 ms 14264 KB
sub1_14.txt 54 ms 14552 KB
sub1_15.txt 51 ms 14312 KB
sub1_16.txt 54 ms 14480 KB
sub1_17.txt 66 ms 22488 KB
sub1_18.txt 674 ms 22828 KB
sub1_19.txt 692 ms 22548 KB
sub1_20.txt 198 ms 22736 KB
sub1_21.txt 136 ms 22300 KB
sub1_22.txt 519 ms 22544 KB
sub1_23.txt 133 ms 22812 KB
sub1_24.txt 554 ms 22872 KB
sub1_25.txt 186 ms 22700 KB
sub1_26.txt 736 ms 22880 KB
sub1_27.txt 152 ms 21844 KB
sub1_28.txt 199 ms 21752 KB
sub1_29.txt 97 ms 21920 KB
sub1_30.txt 155 ms 22124 KB
sub1_31.txt 64 ms 21388 KB
sub1_32.txt 142 ms 21620 KB
sub1_33.txt 186 ms 21776 KB
sub1_34.txt 243 ms 22044 KB
sub1_35.txt 475 ms 21760 KB
sub1_36.txt 212 ms 21876 KB
sub1_37.txt 711 ms 22892 KB
sub1_38.txt 97 ms 15080 KB
sub1_39.txt 79 ms 14720 KB
sub1_40.txt 610 ms 22728 KB
sub1_41.txt 105 ms 15012 KB
sub1_42.txt 52 ms 14560 KB
sub1_43.txt 52 ms 14384 KB
sub1_44.txt 51 ms 14224 KB
sub1_45.txt 54 ms 14384 KB
sub1_46.txt 52 ms 14384 KB
sub1_47.txt 58 ms 14752 KB
sub1_48.txt 80 ms 14636 KB
sub1_49.txt 55 ms 14828 KB
sub1_50.txt 79 ms 14748 KB
sub1_51.txt 57 ms 14584 KB
sub1_52.txt 59 ms 14684 KB
sub1_53.txt 59 ms 14744 KB
sub1_54.txt 83 ms 14532 KB
sub1_55.txt 769 ms 22820 KB
sub1_56.txt 686 ms 22764 KB
sub1_57.txt 153 ms 22804 KB
sub1_58.txt 654 ms 22880 KB
sub1_59.txt 672 ms 22580 KB
sub1_60.txt 117 ms 22880 KB
sub1_61.txt 284 ms 17200 KB
sub1_62.txt 642 ms 22144 KB
sub1_63.txt 56 ms 14364 KB
sub1_64.txt 103 ms 20104 KB
sub1_65.txt 69 ms 14612 KB
sub1_66.txt 425 ms 19184 KB
sub1_67.txt 81 ms 14784 KB
sub1_68.txt 185 ms 15800 KB
sub1_69.txt 95 ms 16224 KB
sub1_70.txt 82 ms 16220 KB
sub1_71.txt 53 ms 14372 KB
sub1_72.txt 54 ms 14252 KB
sub1_73.txt 54 ms 14472 KB
sub1_74.txt 58 ms 17064 KB
sub1_75.txt 54 ms 15120 KB
sub1_76.txt 65 ms 22224 KB
sub1_77.txt 61 ms 14240 KB
sub1_78.txt 58 ms 14500 KB
sub1_79.txt 76 ms 14520 KB
sub1_80.txt 73 ms 14344 KB
sub1_81.txt 75 ms 14304 KB
sub1_82.txt 93 ms 14880 KB
sub1_83.txt 51 ms 14504 KB
sub1_84.txt 75 ms 14476 KB
sub1_85.txt 94 ms 14792 KB
sub1_86.txt 52 ms 14260 KB
sub1_87.txt 54 ms 14516 KB
sub1_88.txt 51 ms 14300 KB
sub1_89.txt 1450 ms 22792 KB
sub1_90.txt 1460 ms 22728 KB
sub1_91.txt 1450 ms 22856 KB
sub1_92.txt 1460 ms 22616 KB
sub1_93.txt 1446 ms 22696 KB
sub1_94.txt 55 ms 14412 KB