\(f(k)\) を以下を満たす \((x,y)\) の個数とします．

• \(\max(|x|,|y|)\leq k\) かつ \(L\leq x\leq R\) かつ \(D\leq y\leq U\)．

\(L,R,D,U\) の絶対値は \(10^6\) 以下であることに注意すると，元の問題の答えは \(\displaystyle\sum_{k=0}^{10^6}(-1)^kf(k)\) です．

• \(f(0)+(f(2)-f(1))+(f(4)-f(3))+\cdots+(f(10^6)-f(10^6-1))\) と変形すればよいです．

ここで \(\max(|x|,|y|)\leq k\) は \(-k\leq x\leq k\) かつ \(-k\leq y\leq k\) と同値であることに注意すれば各 \(k\) に対し \(f(k)\) は \(O(1)\) 時間で求められます．

実装例(Python)

L, R, D, U = map(int, input().split())

ans = 0
for k in range(1000001):
    dx = max(0, min(R, k) - max(L, -k) + 1)
    dy = max(0, min(U, k) - max(D, -k) + 1)
    v = dx * dy
    if k % 2 == 0:
        ans += v
    else:
        ans -= v
print(ans)