Masha and two friends (Codeforces 1080C)
Tags: Implement, implementation

Recently, Masha was presented with a chessboard with a height of $$$n$$$ and a width of $$$m$$$.The rows on the chessboard are numbered from $$$1$$$ to $$$n$$$ from bottom to top. The columns are numbered from $$$1$$$ to $$$m$$$ from left to right. Therefore, each cell can be specified with the coordinates $$$(x,y)$$$, where $$$x$$$ is the column number, and $$$y$$$ is the row number (do not mix up).Let us call a rectangle with coordinates $$$(a,b,c,d)$$$ a rectangle lower left point of which has coordinates $$$(a,b)$$$, and the upper right one — $$$(c,d)$$$.The chessboard is painted black and white as follows:   An example of a chessboard. Masha was very happy with the gift and, therefore, invited her friends Maxim and Denis to show off. The guys decided to make her a treat — they bought her a can of white and a can of black paint, so that if the old board deteriorates, it can be repainted. When they came to Masha, something unpleasant happened: first, Maxim went over the threshold and spilled white paint on the rectangle $$$(x_1,y_1,x_2,y_2)$$$. Then after him Denis spilled black paint on the rectangle $$$(x_3,y_3,x_4,y_4)$$$.To spill paint of color $$$color$$$ onto a certain rectangle means that all the cells that belong to the given rectangle become $$$color$$$. The cell dyeing is superimposed on each other (if at first some cell is spilled with white paint and then with black one, then its color will be black).Masha was shocked! She drove away from the guests and decided to find out how spoiled the gift was. For this, she needs to know the number of cells of white and black color. Help her find these numbers!

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.Each of them is described in the following format:The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^9$$$) — the size of the board.The second line contains four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ ($$$1 \le x_1 \le x_2 \le m, 1 \le y_1 \le y_2 \le n$$$) — the coordinates of the rectangle, the white paint was spilled on.The third line contains four integers $$$x_3$$$, $$$y_3$$$, $$$x_4$$$, $$$y_4$$$ ($$$1 \le x_3 \le x_4 \le m, 1 \le y_3 \le y_4 \le n$$$) — the coordinates of the rectangle, the black paint was spilled on.

Output: Output $$$t$$$ lines, each of which contains two numbers — the number of white and black cells after spilling paint, respectively.

Note: Explanation for examples:The first picture of each illustration shows how the field looked before the dyes were spilled. The second picture of each illustration shows how the field looked after Maxim spoiled white dye (the rectangle on which the dye was spilled is highlighted with red). The third picture in each illustration shows how the field looked after Denis spoiled black dye (the rectangle on which the dye was spilled is highlighted with red).In the first test, the paint on the field changed as follows:  In the second test, the paint on the field changed as follows:  In the third test, the paint on the field changed as follows:  In the fourth test, the paint on the field changed as follows:  In the fifth test, the paint on the field changed as follows:  

Sample Inputs:
5
2 2
1 1 2 2
1 1 2 2
3 4
2 2 3 2
3 1 4 3
1 5
1 1 5 1
3 1 5 1
4 4
1 1 4 2
1 3 4 4
3 4
1 2 4 2
2 1 3 3

Sample Outputs:
0 4
3 9
2 3
8 8
4 8

Solution (Python):
def ww(x, y):
    return (x * y + 1) // 2

def bb(x, y):
    return x * y - ww(x, y)

def w(x1, y1, x2, y2):
    return ww(x2, y2) - ww(x1 - 1, y2) - ww(x2, y1 - 1) + ww(x1 - 1, y1 - 1)

def b(x1, y1, x2, y2):
    return (x2 - x1 + 1) * (y2 - y1 + 1) - w(x1, y1, x2, y2)
for _ in range(int(input().strip())):
    (n, m) = map(int, input().split())
    (x1, y1, x2, y2) = map(int, input().split())
    (x3, y3, x4, y4) = map(int, input().split())
    (nw, nb) = (ww(m, n), bb(m, n))
    x = b(x1, y1, x2, y2)
    nw += x
    nb -= x
    y = w(x3, y3, x4, y4)
    nw -= y
    nb += y
    if not (x3 > x2 or x4 < x1 or y4 < y1 or (y2 < y3)):
        (X1, Y1) = (max(x1, x3), max(y1, y3))
        (X2, Y2) = (min(x2, x4), min(y2, y4))
        c = b(X1, Y1, X2, Y2)
        nw -= c
        nb += c
    print(nw, nb)

Solution (Python):
import os
from bisect import bisect_left, insort, bisect
import sys
from heapq import heappop, heappush, heapify
from io import BytesIO, IOBase
from math import ceil, log2, gcd
from collections import defaultdict
INF = 10 ** 18
MOD = 998244353

def lcm(a, b):
    (a, b) = (max(a, b), min(a, b))
    return a // gcd(a, b) * b

def modFact(n, p):
    if n >= p:
        return 0
    result = 1
    for i in range(1, n + 1):
        result = result * i % p
    return result

def main():

    def func(x1, y1, x2, y2):
        numsquare1 = (abs(x1 - x2) + 1) * (abs(y1 - y2) + 1)
        if abs(x1 - x2 + 1) % 2 and abs(y1 - y2 + 1) % 2:
            if (x1 + y1) % 2:
                black1 = (numsquare1 + 1) // 2
            else:
                black1 = numsquare1 // 2
        else:
            black1 = numsquare1 // 2
        white1 = numsquare1 - black1
        return (black1, white1)

    def intersection(x1, y1, x2, y2, x3, y3, x4, y4):
        x5 = max(x1, x3)
        y5 = max(y1, y3)
        x6 = min(x2, x4)
        y6 = min(y2, y4)
        if x5 > x6 or y5 > y6:
            return (0, 0)
        x7 = x5
        y7 = y6
        x8 = x6
        y8 = y5
        return func(x7, y7, x8, y8)
    for i in range(int(input())):
        (n, m) = map(int, input().split())
        (x1, y1, x2, y2) = map(int, input().split())
        (x3, y3, x4, y4) = map(int, input().split())
        (tot_black, tot_white) = func(1, 1, n, m)
        whitadd = func(x1, y1, x2, y2)
        blackadd = func(x3, y3, x4, y4)
        tot_black -= whitadd[0]
        tot_white += whitadd[0]
        tot_black += blackadd[1]
        tot_white -= blackadd[1]
        func3 = intersection(x1, y1, x2, y2, x3, y3, x4, y4)
        tot_white -= func3[0]
        tot_black += func3[0]
        print(tot_white, tot_black)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
import os
from bisect import bisect_left, insort, bisect
import sys
from heapq import heappop, heappush, heapify
from io import BytesIO, IOBase
from math import ceil, log2, gcd
from collections import defaultdict
INF = 10 ** 18
MOD = 998244353

def lcm(a, b):
    (a, b) = (max(a, b), min(a, b))
    return a // gcd(a, b) * b

def modFact(n, p):
    if n >= p:
        return 0
    result = 1
    for i in range(1, n + 1):
        result = result * i % p
    return result

def main():

    def func(x1, y1, x2, y2):
        numsquare1 = (abs(x1 - x2) + 1) * (abs(y1 - y2) + 1)
        if (abs(x1 - x2) + 1) % 2 and (abs(y1 - y2) + 1) % 2:
            if (x1 + y1) % 2:
                black1 = (numsquare1 + 1) // 2
            else:
                black1 = numsquare1 // 2
        else:
            black1 = numsquare1 // 2
        white1 = numsquare1 - black1
        return (black1, white1)

    def intersection(x1, y1, x2, y2, x3, y3, x4, y4):
        x5 = max(x1, x3)
        y5 = max(y1, y3)
        x6 = min(x2, x4)
        y6 = min(y2, y4)
        if x5 > x6 or y5 > y6:
            return ((0, 0), 0)
        return (func(x5, y5, x6, y6), (abs(x5 - x6) + 1) * (abs(y5 - y6) + 1))
    for i in range(int(input())):
        (n, m) = map(int, input().split())
        (x1, y1, x2, y2) = map(int, input().split())
        (x3, y3, x4, y4) = map(int, input().split())
        (tot_black, tot_white) = func(1, 1, n, m)
        whitadd = func(x1, y1, x2, y2)
        blackadd = func(x3, y3, x4, y4)
        func3 = intersection(x1, y1, x2, y2, x3, y3, x4, y4)
        tot_white += whitadd[0]
        tot_black -= whitadd[0]
        tot_white -= blackadd[1]
        tot_black += blackadd[1]
        tot_white -= func3[0][0]
        tot_black += func3[0][0]
        print(tot_white, tot_black)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()