結果

問題 No.3292 World Map Distance
コンテスト
ユーザー kona0001
提出日時 2025-09-08 02:40:33
言語 Ruby
(3.4.1)
結果
AC  
実行時間 1,089 ms / 3,000 ms
コード長 1,566 bytes
コンパイル時間 520 ms
コンパイル使用メモリ 7,936 KB
実行使用メモリ 55,516 KB
最終ジャッジ日時 2025-09-08 02:40:51
合計ジャッジ時間 16,505 ms
ジャッジサーバーID
（参考情報） 		judge / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:58: warning: assigned but unused variable - left
Syntax OK

ソースコード

diff # 

def assert f
  unless f
    puts "Error!: Constraint Violation"
    exit
  end
end

n,X,Y = gets.split.map(&:to_i)
assert(1 <= n && n <= 200000)
assert(1 <= X && X <= 10**9)
assert(1 <= Y && Y <= 10**9)

xs = []
ys = []
n.times do
  x,y = gets.split.map(&:to_i)
  assert(1 <= x && x <= X)
  assert(1 <= y && y <= Y)
  xs << x
  ys << y
end

def solve(n,a,l)
  a.map!{|v| v-1 }
  a.sort!
  kouho = []
  a.each do |v|
    if l%2 == 0
      kouho << (v + l/2)%l
    else
      kouho << (v + l/2)%l
      kouho << (v + 1 + l/2)%l
    end
  end
  kouho.uniq!
  kouho.sort!
  stack_left = []
  stack_right = []
  now = 0
  i = 0
  while i < n && a[i] <= l/2
    stack_right << a[i]
    now += a[i]
    i += 1
  end
  while i < n
    stack_left << a[i] - l
    now += l-a[i]
    i += 1
  end
  max = now
  kouho_len = kouho.length
  i = 0
  pre = 0
  while i < kouho_len
    pos = kouho[i]
    right = pos + (l-1)/2
    left = pos - l/2

    sub_cnt_left = stack_left.size
    sub_cnt_right = stack_right.size
    while stack_left.empty?.! && stack_left[0]+l <= right
      v = stack_left.shift
      now -= pre - v
      stack_right << v + l
      now += v + l - pos
      sub_cnt_left -= 1
    end
    now += sub_cnt_left * (pos - pre)

    while stack_right.empty?.! && stack_right[0] <= pos
      v = stack_right.shift
      now -= v - pre
      stack_left << v
      now += pos - v
      sub_cnt_right -= 1
    end
    now -= sub_cnt_right * (pos - pre)
    max = now if max < now
    pre = pos
    i += 1
  end
  max
end

ans = solve(n,xs,X) + solve(n,ys,Y)
puts ans
0