Submission #13454965

Source Code Expand

# 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 AC
Exec Time 474 ms
Memory 43092 KiB

Judge Result

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