Submission #13393878

---

Source Code Expand

N, M = gets.split.map(&:to_i)
ABCs = N.times.map{gets.split.map(&:to_i)}
DEFs = M.times.map{gets.split.map(&:to_i)}
INF = 10**10

require 'set'

xs, ys = SortedSet.new, SortedSet.new
ABCs.each{ys << _1[2]}
DEFs.each{xs << _1[0]}
ys = [-INF] + ys.to_a + [INF]
xs = [-INF] + xs.to_a + [INF]
n, m = xs.size - 1, ys.size - 1
wx, wy = Array.new(n){Array.new(m, false)}, Array.new(n){Array.new(m, false)}
ABCs.each do |a, b, c|
  x1 = xs.bsearch_index{_1 >= a}
  y1 = ys.bsearch_index{_1 >= c}
  x2 = xs.bsearch_index{_1 > b} - 1
  (x1 ... x2).each{wy[_1][y1] = true}
end
DEFs.each do |d, e, f|
  x1 = xs.bsearch_index{_1 >= d}
  y1 = ys.bsearch_index{_1 >= e}
  y2 = ys.bsearch_index{_1 > f} - 1
  (y1 ... y2).each{wx[x1][_1] = true}
end
cs = Array.new(n){Array.new(m, false)}
cx, cy = xs.bsearch_index{_1 > 0} - 1, ys.bsearch_index{_1 > 0} - 1
cs[cx][cy] = true
q, ans = [[cx, cy]], 0
while !q.empty?
  x, y = q.pop
  (puts 'INF'; exit) if x.zero? || y.zero?
  ans += (xs[x + 1] - xs[x])*(ys[y + 1] - ys[y])
  (cs[x - 1][y] = true; q << [x - 1, y]) if !x.zero? && !wx[x][y] && !cs[x - 1][y]
  (cs[x][y - 1] = true; q << [x, y - 1]) if !y.zero? && !wy[x][y] && !cs[x][y - 1]
  (cs[x + 1][y] = true; q << [x + 1, y]) if x + 1 < n && !wx[x + 1][y] && !cs[x + 1][y]
  (cs[x][y + 1] = true; q << [x, y + 1]) if y + 1 < m && !wy[x][y + 1] && !cs[x][y + 1]
end
puts ans

Submission Info

Judge Result