Problem:
		
C: オセロ

		
問題

		

			オセロの盤面を用意する. 盤面は左上が $(1,1)$ , 右下が $(8,8)$ と表記する. ここで用意する盤面は, 以下のように, $(5,4)$ の黒の石がない.
		

		

........
........
........
...ox...
....o...
........
........
........

		

			黒石:x 白石:o

			8x8の盤面

			この状態から, 黒が先手でオセロを開始する.
		

		

			AORイカちゃんは, 以下のルールで $q$ 回遊ぶ.
		

		

			左上を $a$ 行目 $b$ 列目のマス, 右下を $c$ 行目 $d$ 列目のマスとした, マス目に沿った長方形領域が与えられる.
		

		

			AORイカちゃんは, この長方形領域に含まれる石の数を最大化するように, オセロのルール(参考:Wikipedia　オセロ  )にのっとり黒石と白石を交互に置いていく.

			これ以上石が置けなくなったとき(白石黒石ともにパスするしかない状態やすべての盤面が埋まった状態のとき), ゲームを終了する.
		

		

			それぞれのゲームで, その領域に含まれる石の数を最大化したときの石の数を出力せよ.

			なお, 入力や出力の回数が多くなることがあるため, 入出力には高速な関数を用いることを推奨する.
		

		
制約

		

			
$1 \leq q \leq 10^{5}$

			
$1 \leq a \leq c \leq 8$

			
$1 \leq b \leq d \leq 8$

		

		
入力形式

		
 入力は以下の形式で与えられる. 

		

			$q$

			$a_1\ b_1\ c_1\ d_1$

			$a_2\ b_2\ c_2\ d_2$

			$\vdots$

			$a_q\ b_q\ c_q\ d_q$

		

		
出力

		

			それぞれのゲームで, その領域に含まれる, 石の数を最大化したときの石の数を出力せよ. また, 末尾に改行も出力せよ.
		

		
サンプル

		
サンプル入力 1

		

3
1 1 8 8
2 4 3 8
8 8 8 8

		
サンプル出力 1

		

48
7
1



Sample input:
3
1 1 8 8
2 4 3 8
8 8 8 8


Sample output:
48
7
1

Submission status: Accepted

Solution code:
q = int(input())
li = [input().split() for i in range(q)]
for i in li:
    a, b, c, d = map(int, i)
    ans = 0
    for j in range(a, c+1):
        for k in range(b, d+1):
            ans += 0 if j%2 == 1 and k%2 == 0 else 1
    print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
"""
h,w = LI()
a,b = LI()
y = h//a
x = w//b
ans = h*w-a*y*b*x
print(ans)
"""

#B
"""
def m(x,y):
    if x == y:
        return "T"
    if x == "F":
        return "T"
    return "F"
n = I()
p = input().split()
ans = p[0]
for i in range(1,n):
    ans = m(ans,p[i])
print(ans)
"""

#C
s = [[1]*8 for i in range(4)]
for i in range(4):
    s.insert(2*i,[1,0,1,0,1,0,1,0])
for j in range(8):
    for i in range(1,8):
        s[j][i] += s[j][i-1]
for j in range(8):
    for i in range(1,8):
        s[i][j] += s[i-1][j]
s.insert(0,[0,0,0,0,0,0,0,0,0])
for i in range(1,9):
    s[i].insert(0,0)
q = I()
for _ in range(q):
    a,b,c,d = LI()
    print(s[c][d]-s[c][b-1]-s[a-1][d]+s[a-1][b-1])

#D
"""
n = I()
a = LI()
dp = [float("inf") for i in range(n)]
b = [[] for i in range(n)]
ind = [0 for i in range(100001)]
for i in range(n):
    k = bisect.bisect_left(dp,a[i])
    dp[k] = a[i]
    b[k].append(a[i])
    ind[a[i]] = max(i,ind[a[i]])
for i in range(n):
    if dp[i] == float("inf"):break
    b[i].sort()
    b[i] = b[i][::-1]
i -= 1
ans = b[i][0]
now_ind = ind[b[i][0]]
now_v = b[i][0]
while i >= 0:
    for j in b[i]:
        if ind[j] < now_ind and j < now_v:
            ans += j
            now_ind = ind[j]
            now_v = j
    i -= 1
print(ans)
"""
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))
from collections import defaultdict

G = dict()
for i in range(9):
    G[(i, 9)] = 0
    G[(9, i)] = 0
G[(9, 9)] = 0

for i in range(8)[::-1]:
    a = 8 - i
    b = -(-(8 - i)//2)
    i= i+1
    for j in range(8)[::-1]:
        if j % 2 == 1:
            j = j+1
            G[(i, j)] = G[(i, j+1)] + b
        else:
            j = j+1
            G[(i, j)] = G[(i, j+1)] + a

q = int(input())
for _ in range(q):
    a, b, c, d = inpl()
    print(G[(a, b)] - G[(c+1, b)] - G[(a, d+1)] + G[(c+1), (d+1)])