# AtCoder Regular Contest 084

URL: https://atcoder.jp/contests/arc084 (opens new window)

# C

n = gets.chomp.to_i
a_arr = gets.chomp.split(" ").map(&:to_i).sort_by{|x| x} + [10 ** 9 + 1]
b_arr = gets.chomp.split(" ").map(&:to_i).sort_by{|x| x}
c_arr = gets.chomp.split(" ").map(&:to_i).sort_by{|x| x} + [10 ** 9 + 1]

result = 0
a_i = 0
c_i = 0
b_arr.each do |b|
  # bよりも小さいaを全部拾う
  (a_i..n).each do |i|
    if a_arr[i] >= b
      # 先頭から(a_i - 1)までが対象
      a_i = i
      break
    end
  end
  # bよりも大きいcを全部拾う
  (c_i..n).each do |i|
    if c_arr[i] > b
      # c_iから末尾までが対象
      c_i = i
      break
    end
  end
  result += a_i * (n - c_i)
end

puts result

別解。二分探索。

n = gets.chomp.to_i
a_arr = gets.chomp.split(" ").map(&:to_i).sort_by{|x| x}
b_arr = gets.chomp.split(" ").map(&:to_i)
c_arr = gets.chomp.split(" ").map(&:to_i).sort_by{|x| -x}

result = 0
b_arr.each do |b|
  a_num = a_arr.bsearch_index {|a| a >= b} || n
  c_num = c_arr.bsearch_index {|c| c <= b} || n
  result += a_num * c_num
end

puts result
Last Updated: 2020/08/29 17:41