Submission #13454965


Source Code Expand

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

N,M = gets.split.map(&:to_i)
縦線,横線 = [[N,0,1,2],[M,1,2,0]].map{|n,*va|
	n.times.map{ gets.split.map(&:to_i).values_at(*va) }.group_by{_3}
}
経線,緯線 = [縦線,横線].map{|l|
	[-Float::INFINITY] + l.keys.sort + [Float::INFINITY]
}
右?,下? = [[縦線,経線,緯線],[横線,緯線,経線]].map{|l1,l2,l3|
	Hash.new{|h,k|
		h[k] = l1[l2[k+1]].inject([true]*(l3.size-2)){|a,(b,c,_)|
			l = l3.bsearch_index{|_| b<=_ }
			r = l3.bsearch_index{|_| c<_ }-1
			next a.fill(false,l...r)
		}
	}
}

area = 0
cow = [経線,緯線].map{|l| l.bsearch_index{|_| 0<_ }-1 }
Q = [cow]
Qd = Array.new(経線.size-1){ [false]*(緯線.size-1) }
Qd[cow[0]][cow[1]] = true
until Q.empty?
	横,縦 = Q.pop

	area += (経線[横+1]-経線[横])*(緯線[縦+1]-緯線[縦])
	break if area.infinite?

	(Q << [横+1,縦]; Qd[横+1][縦] = true) if ! Qd[横+1][縦] && 右?[横][縦]
	(Q << [横-1,縦]; Qd[横-1][縦] = true) if ! Qd[横-1][縦] && 右?[横-1][縦]
	(Q << [横,縦+1]; Qd[横][縦+1] = true) if ! Qd[横][縦+1] && 下?[縦][横]
	(Q << [横,縦-1]; Qd[横][縦-1] = true) if ! Qd[横][縦-1] && 下?[縦-1][横]
end

puts(area.finite? ? area : 'INF')

Submission Info

Submission Time
Task F - . (Single Dot)
User ds14050
Language Ruby (2.7.1)
Score 600
Code Size 1336 Byte
Status
Exec Time 474 ms
Memory 43092 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 50 ms 14440 KB
sample_02.txt 55 ms 14400 KB
sub1_01.txt 56 ms 17044 KB
sub1_02.txt 58 ms 16748 KB
sub1_03.txt 54 ms 15008 KB
sub1_04.txt 55 ms 14656 KB
sub1_05.txt 62 ms 20028 KB
sub1_06.txt 57 ms 15336 KB
sub1_07.txt 54 ms 15704 KB
sub1_08.txt 56 ms 14472 KB
sub1_09.txt 53 ms 15420 KB
sub1_10.txt 61 ms 20300 KB
sub1_11.txt 52 ms 14456 KB
sub1_12.txt 54 ms 14620 KB
sub1_13.txt 52 ms 14456 KB
sub1_14.txt 53 ms 14356 KB
sub1_15.txt 54 ms 14236 KB
sub1_16.txt 52 ms 14268 KB
sub1_17.txt 63 ms 23556 KB
sub1_18.txt 247 ms 40600 KB
sub1_19.txt 252 ms 43092 KB
sub1_20.txt 110 ms 36416 KB
sub1_21.txt 93 ms 33140 KB
sub1_22.txt 211 ms 40236 KB
sub1_23.txt 94 ms 32788 KB
sub1_24.txt 217 ms 42368 KB
sub1_25.txt 103 ms 35840 KB
sub1_26.txt 264 ms 41136 KB
sub1_27.txt 93 ms 30152 KB
sub1_28.txt 109 ms 31036 KB
sub1_29.txt 76 ms 27224 KB
sub1_30.txt 97 ms 29380 KB
sub1_31.txt 63 ms 21972 KB
sub1_32.txt 92 ms 31276 KB
sub1_33.txt 101 ms 30688 KB
sub1_34.txt 121 ms 31696 KB
sub1_35.txt 186 ms 35852 KB
sub1_36.txt 113 ms 31796 KB
sub1_37.txt 253 ms 41868 KB
sub1_38.txt 67 ms 16424 KB
sub1_39.txt 64 ms 15112 KB
sub1_40.txt 219 ms 41116 KB
sub1_41.txt 70 ms 16536 KB
sub1_42.txt 52 ms 14352 KB
sub1_43.txt 55 ms 14348 KB
sub1_44.txt 52 ms 14268 KB
sub1_45.txt 53 ms 14236 KB
sub1_46.txt 51 ms 14296 KB
sub1_47.txt 53 ms 14680 KB
sub1_48.txt 63 ms 15480 KB
sub1_49.txt 54 ms 14808 KB
sub1_50.txt 63 ms 15888 KB
sub1_51.txt 53 ms 14764 KB
sub1_52.txt 55 ms 14668 KB
sub1_53.txt 58 ms 15756 KB
sub1_54.txt 66 ms 15696 KB
sub1_55.txt 271 ms 40588 KB
sub1_56.txt 253 ms 40564 KB
sub1_57.txt 127 ms 36700 KB
sub1_58.txt 243 ms 39820 KB
sub1_59.txt 252 ms 40208 KB
sub1_60.txt 97 ms 34360 KB
sub1_61.txt 125 ms 23816 KB
sub1_62.txt 232 ms 38512 KB
sub1_63.txt 52 ms 14380 KB
sub1_64.txt 73 ms 27116 KB
sub1_65.txt 59 ms 14784 KB
sub1_66.txt 172 ms 31260 KB
sub1_67.txt 64 ms 15756 KB
sub1_68.txt 91 ms 20040 KB
sub1_69.txt 64 ms 18428 KB
sub1_70.txt 61 ms 18404 KB
sub1_71.txt 54 ms 14428 KB
sub1_72.txt 51 ms 14224 KB
sub1_73.txt 53 ms 14308 KB
sub1_74.txt 58 ms 17144 KB
sub1_75.txt 52 ms 15068 KB
sub1_76.txt 61 ms 22636 KB
sub1_77.txt 54 ms 14452 KB
sub1_78.txt 56 ms 14508 KB
sub1_79.txt 57 ms 14368 KB
sub1_80.txt 58 ms 14348 KB
sub1_81.txt 56 ms 14476 KB
sub1_82.txt 63 ms 14428 KB
sub1_83.txt 53 ms 14312 KB
sub1_84.txt 60 ms 14472 KB
sub1_85.txt 55 ms 14672 KB
sub1_86.txt 54 ms 14448 KB
sub1_87.txt 51 ms 14328 KB
sub1_88.txt 57 ms 14344 KB
sub1_89.txt 446 ms 38452 KB
sub1_90.txt 454 ms 38276 KB
sub1_91.txt 474 ms 38468 KB
sub1_92.txt 453 ms 38316 KB
sub1_93.txt 451 ms 38164 KB
sub1_94.txt 52 ms 14176 KB