Problem:
 Score : 500 points    Problem Statement AtCoDeer is thinking of painting an infinite two-dimensional grid in a checked pattern of side K .
Here, a checked pattern of side K is a pattern where each square is painted black or white so that each connected component of each color is a K  ×  K square.
Below is an example of a checked pattern of side 3 :     AtCoDeer has N desires.
The i -th desire is represented by x_i , y_i and c_i .
If c_i is B , it means that he wants to paint the square (x_i,y_i) black; if c_i is W , he wants to paint the square (x_i,y_i) white.
At most how many desires can he satisfy at the same time?      Constraints  1  ≤  N  ≤  10^5  1  ≤  K  ≤  1000  0  ≤  x_i  ≤  10^9  0  ≤  y_i  ≤  10^9  If i  ≠  j , then (x_i,y_i)  ≠  (x_j,y_j) .  c_i is B or W .  N , K , x_i and y_i are integers.         Input Input is given from Standard Input in the following format:  N  K  x_1  y_1  c_1  x_2  y_2  c_2  :  x_N  y_N  c_N       Output Print the maximum number of desires that can be satisfied at the same time.        Sample Input 1 4 3
0 1 W
1 2 W
5 3 B
5 4 B      Sample Output 1 4  He can satisfy all his desires by painting as shown in the example above.       Sample Input 2 2 1000
0 0 B
0 1 W      Sample Output 2 2       Sample Input 3 6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W      Sample Output 3 4

Solution (Python):
sc = iter(open(0).read().split())
ni = lambda: int(next(sc))
ns = lambda: next(sc)

N, K = ni(), ni()

K2 = K * 2
A = [[0] * K2 for _ in range(K2)]
for _ in range(N):
    x, y, c = ni(), ni(), ns()
    if c == "W":
        y += K
    A[y % K2][x % K2] += 1

S = [[0] * (K2 + 1) for _ in range(K2 + 1)]
for i in range(K2):
    for j in range(K2):
        S[i + 1][j + 1] = (
            A[i][j]
            + S[i + 1][j]
            + S[i][j + 1]
            - S[i][j]
        )

ans = 0
for i in range(K, K2 + 1):
    for j in range(K, K2 + 1):
        res = (
            S[i][j] + S[i - K][j - K] - S[i - K][j] - S[i][j - K]
            + S[i - K][j - K]
            + S[K2][j - K] - S[i][j - K]
            + S[i - K][K2] - S[i - K][j]
            + S[K2][K2] + S[i][j] - S[i][K2] - S[K2][j]
        )
        ans = max(ans, res, N - res)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def accumrate(h,w,acc,A):
  for i in range(1,h+1):
    for j in range(1,w+1):
      acc[i][j] = acc[i][j-1] + A[i-1][j-1]
  for i in range(1,h+1):
    for j in range(1,w+1):
      acc[i][j] += acc[i-1][j]
      
def cal(i,j,g,r,acc):
  return acc[g][r] + acc[i][j] - acc[g][j] - acc[i][r]

n,k = map(int,input().split())
K = 2*k
cw = [[0]*K for i in range(K)]
cb = [[0]*K for i in range(K)]
sw = 0
sb = 0
for i in range(n):
  x,y,c = input().split()
  if c == 'B':
    cb[int(x)%K][int(y)%K] += 1
    sb += 1
  else:
    cw[int(x)%K][int(y)%K] += 1
    sw += 1
    
acw = [[0]*(K+1) for i in range(K+1)]
acb = [[0]*(K+1) for i in range(K+1)]
accumrate(K,K,acb,cb)
accumrate(K,K,acw,cw)

ans = 0
for i in range(k):
  for j in range(k):
    chk_b = cal(0,0,i,j,acb)+cal(i,j,i+k,j+k,acb)+cal(i+k,j+k,K,K,acb)+cal(0,j+k,i,K,acb)+cal(i+k,0,K,j,acb)
    chk_w = cal(0,0,i,j,acw)+cal(i,j,i+k,j+k,acw)+cal(i+k,j+k,K,K,acw)+cal(0,j+k,i,K,acw)+cal(i+k,0,K,j,acw)
    ans = max(ans,max(chk_b+sw-chk_w,chk_w+sb-chk_b))
    
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
MX = 2*K
A = [[0]*MX for _ in range(MX)]
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == "W":
        y += K
    A[y%MX][x%MX] += 1
S = [[0]*(MX+1) for _ in range(MX+1)]
for y in range(MX):
    for x in range(MX):
        S[y+1][x+1] = S[y+1][x] + S[y][x+1] - S[y][x] + A[y][x]
ans = 0
for y in range(K, MX+1):
    for x in range(K, MX+1):
        s = S[y][x] - S[y-K][x] - S[y][x-K] + S[y-K][x-K]
        s += S[y-K][x-K]
        s += S[MX][x-K] - S[y][x-K]
        s += S[y-K][MX] - S[y-K][x]
        s += S[MX][MX] - S[y][MX] - S[MX][x] + S[y][x]
        ans = max(ans, s, N-s)
print(ans)

Solution (Python):
n,k=map(int,input().split())
xyc_=[list(input().split()) for _ in range(n)]
xyc=[]
for x,y,c in xyc_:
  x=int(x)%(2*k)
  y=int(y)%(2*k)
  if x>=k and y>=k:
    x%=k
    y%=k
  elif x>=k:
    x%=k
    c='W' if c=='B' else 'B'
  elif y>=k:
    y%=k
    c='W' if c=='B' else 'B'
  xyc.append([x,y,c])

wmap=[[0]*k for _ in range(k)]
bmap=[[0]*k for _ in range(k)]
for x,y,c in xyc:
  if c=='B':
    bmap[x][y]+=1
  else:
    wmap[x][y]+=1
for i in range(k):
  for j in range(k-1):
    bmap[i][j+1]+=bmap[i][j]
    wmap[i][j+1]+=wmap[i][j]
for i in range(k):
  for j in range(k-1):
    bmap[j+1][i]+=bmap[j][i]
    wmap[j+1][i]+=wmap[j][i]






def func(x,y):
  bret,wret=0,0
  bret=bmap[-1][-1]
  wret=wmap[-1][-1]
  if x==0 and y==0:
    pass
  elif x==0:
    bret-=bmap[-1][y-1]
    wret-=wmap[-1][y-1]
  elif y==0:
    bret-=bmap[x-1][-1]
    wret-=wmap[x-1][-1]
  else:
    bret-=bmap[-1][y-1]
    wret-=wmap[-1][y-1]
    bret-=bmap[x-1][-1]
    wret-=wmap[x-1][-1]
    bret+=2*bmap[x-1][y-1]
    wret+=2*wmap[x-1][y-1]
  return max(wmap[-1][-1]-wret+bret,bmap[-1][-1]-bret+wret)
ans=0
for i in range(k):
  for j in range(k):
    ans=max(ans,func(i,j))
print(ans)

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))



N, K = lr()
table = [[0] * 2*K for _ in range(K)]
for _ in range(N):
    x, y, c = sr().split()
    x = int(x); y = int(y)
    if c == 'B':
        x -= K  
    x %= 2 * K; y %= 2 * K
    if x >= K and y >= K:
        x -= K; y -= K
    elif y >= K:
        x += K; y -= K
    
    table[y][x] += 1

table = np.array(table, dtype=np.int32)
table = np.concatenate([table, table], axis=1)
table2 = np.roll(table, K, axis=1)
table = np.concatenate([table, table2], axis=0)
table_cum = table.cumsum(axis=1).cumsum(axis=0)
prev = table_cum.copy()
table_cum[:, K:] -= prev[:, :-K]
table_cum[K:, :] -= prev[:-K, :]
table_cum[K:, K:] += prev[:-K, :-K]
answer = table_cum.max()
print(answer)

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, K = map(int, input().split())
X, Y, C = [[0] * N for _ in range(3)]

mem = [[0] * (4 * K + 1) for _ in range(4 * K + 1)]

for i in range(N):
    S = input().split()
    X[i], Y[i], C[i] = int(S[0]), int(S[1]), S[2]
    x, y = X[i] % (2 * K) + 1, (Y[i] + (K if C[i] == "W" else 0)) % (2 * K) + 1
    mem[x][y] += 1
    mem[x + K][y] -= 1
    mem[x][y + K] -= 1
    mem[x + K][y + K] += 1

for h in range(1, 4 * K + 1):
    for w in range(1, 4 * K + 1):
        mem[h][w] += mem[h - 1][w] + mem[h][w - 1] - mem[h - 1][w - 1]

ans = 0
for h in range(K + 1):
    for w in range(K + 1):
        s = mem[h][w] + mem[h + 2 * K][w] + mem[h][w + 2 * K] + mem[h + K][w + K] + mem[h + 2 * K][w + 2 * K]
        ans = max(ans, s)

for h in range(K + 1):
    for w in range(K, 2 * K + 1):
        s = mem[h][w] + mem[h + 2 * K][w] + mem[h + K][w - K] + mem[h + K][w + K]
        ans = max(ans, s)


print(ans)

Solution (Python):
n, k = map(int, input().split())
d = [[0 for _ in range(k+1)] for _ in range(k+1)]
e = [[0 for _ in range(k+1)] for _ in range(k+1)]
cnt_d, cnt_e = 0, 0

for _ in range(n):
    x, y, c = input().split()
    x, y = int(x), int(y)

    res = (x // k + y // k) % 2
    if (res == 0 and c == 'B') or (res == 1 and c == 'W'):
        d[x%k+1][y%k+1] += 1
        cnt_d += 1
    else:
        e[x%k+1][y%k+1] += 1
        cnt_e += 1

for i in range(k+1):
    for j in range(k):
        d[i][j+1] += d[i][j]
        e[i][j+1] += e[i][j]

for j in range(k+1):
    for i in range(k):
        d[i+1][j] += d[i][j]
        e[i+1][j] += e[i][j]


ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        res_d = d[-1][-1] - d[i-1][-1] - d[-1][j-1] + 2 * d[i-1][j-1]
        res_e = e[-1][-1] - e[i-1][-1] - e[-1][j-1] + 2 * e[i-1][j-1]
        ans = max(ans,res_d + cnt_e - res_e, res_e + cnt_d - res_d)

print(ans)

Solution (Python):
N,K=map(int,input().split())
XYC=[input().split() for i in range(N)]
d=[[[0]*K for i in range(K)] for i in range(2)]
for x,y,c in XYC:
    x,y=int(x),int(y)
    z=(x//K%2)^(y//K%2)^(c=='B')
    d[z][x%K][y%K]+=1
a=[[[0]*(K+1) for i in range(K+1)] for i in range(2)]
for k in range(2):
    for i in range(K):
        for j in range(K):
            a[k][i+1][j+1]=a[k][i+1][j]+a[k][i][j+1]-a[k][i][j]+d[k][i][j]
r=0
for k in range(2):
    for i in range(K):
        for j in range(K):
            r=max(r,a[k][-1][-1]-a[k][i][-1]-a[k][-1][j]+a[k][i][j]*2\
                +a[k^1][i][-1]+a[k^1][-1][j]-a[k^1][i][j]*2)
print(r)

Solution (Python):
def main():
    n,k = map(int,input().split())
    e = [[0]*(2*k) for i in range(2*k)]
    mod = 2*k
    for i in range(n):
        x,y,c = input().split()
        if c == "W":
            x = int(x)%mod
            y = (int(y)+k)%mod
        else:
            x = int(x)%mod
            y = int(y)%mod
        e[x][y] += 1

    for i in range(mod):
        for j in range(mod):
            if i != 0 and j != 0:
                e[i][j] -= e[i-1][j-1]
            if i != 0:
                e[i][j] += e[i-1][j]
            if j != 0:
                e[i][j] +=e[i][j-1]

    ans = 0
    for i in range(k+1):
        for j in range(k+1):
            count = e[-1][-1]+2*e[i+k-1][j+k-1]-e[-1][j+k-1]-e[i+k-1][-1]
            if i != 0 and j != 0:
                count += 2*e[i-1][j-1]
            if i != 0:
                count += e[i-1][-1]-2*e[i-1][j+k-1]
            if j != 0:
                count += e[-1][j-1]-2*e[i+k-1][j-1]
            ans = max(ans,count,n-count)
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n,k = map(int,input().split())
    e = [[0]*(2*k+1) for i in range(2*k+1)]
    mod = 2*k
    for i in range(n):
        x,y,c = input().split()
        if c == "W":
            x = int(x)%mod
            y = (int(y)+k)%mod
        else:
            x = int(x)%mod
            y = int(y)%mod
        e[x+1][y+1] += 1
    
    for i in range(mod):
        for j in range(mod):
            e[i+1][j+1] += e[i][j+1]+e[i+1][j]-e[i][j]
    
    def count(ax,ay,bx,by):
        return e[ax][ay] +e[bx][by] - e[ax][by]-e[bx][ay]
    ans = 0
    for i in range(k+1):
        for j in range(k+1):
            c = count(2*k,2*k,i+k,j+k)+count(2*k,j,i+k,0)+count(i,2*k,0,j+k)+count(i,j,0,0)+count(i+k,j+k,i,j)
            ans = max(ans,c,n-c)
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):


import sys






























def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def fill_2d_accum(accum, command):
        for x, y in command:
            accum[x+1][y+1] += 1
        for i in range(1,2*k+1):
            for j in range(1, 2*k+1):
                accum[i][j] += accum[i][j-1]
        for j in range(1, 2*k+1):
            for i in range(1, 2*k+1):
                accum[i][j] += accum[i-1][j]

    def calc_accum(accum, sx, tx, sy, ty):
        """[sx:tx], [sy:ty] で囲まれる領域に含まれる個数を accum を用いて計算する"""
        return accum[tx][ty] - (accum[sx][ty] + accum[tx][sy]) + accum[sx][sy]

    
    def calc_max():
        ans = -1
        for kx in range(k):
            for ky in range(k):
                b = 0
                b += calc_accum(black_2d_accum, kx, kx+k, ky, ky+k)
                b += calc_accum(black_2d_accum, 0, kx, 0, ky)
                b += calc_accum(black_2d_accum, kx+k, 2*k, 0, ky)
                b += calc_accum(black_2d_accum, 0, kx, ky+k, 2*k)
                b += calc_accum(black_2d_accum, kx+k, 2*k, ky+k, 2*k)
                w = 0
                w += calc_accum(white_2d_accum, kx, kx+k, ky, ky+k)
                w += calc_accum(white_2d_accum, 0, kx, 0, ky)
                w += calc_accum(white_2d_accum, kx+k, 2*k, 0, ky)
                w += calc_accum(white_2d_accum, 0, kx, ky+k, 2*k)
                w += calc_accum(white_2d_accum, kx+k, 2*k, ky+k, 2*k)                
                ans = max(ans, b, w)
        return ans

    
    n, k = mi()
    command = [input().split() for _ in range(n)]
    
    black_command = []
    for x, y, c in command:
        x = int(x) % (2*k)
        y = int(y) % (2*k) if c == 'B' else (int(y) + k) % (2*k)
        black_command.append((x, y))
    
    white_command = []
    for x, y, c in command:
        x = int(x) % (2*k)
        y = int(y) % (2*k) if c == 'W' else (int(y) + k) % (2*k)
        white_command.append((x, y))    


    black_2d_accum = [[0] * (2*k+1) for _ in range(2*k+1)]
    fill_2d_accum(black_2d_accum, black_command)
    white_2d_accum = [[0] * (2*k+1) for _ in range(2*k+1)]
    fill_2d_accum(white_2d_accum, white_command)    
    
    

    print(calc_max())





if __name__ == "__main__":
    main()

Solution (Python):
from itertools import accumulate
N, K = map(int, input().split())
grid = [[0] * (4 * K + 1) for _ in range(4 * K + 1)]
for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == "B":
        x += K
    x %= (2 * K)
    y %= (2 * K)
    grid[x+1][y+1] += 1
    grid[x+2*K+1][y+1] += 1
    grid[x+1][y+2*K+1] += 1
    grid[x+2*K+1][y+2*K+1] += 1

for i in range(4 * K):
    grid[i + 1] = list(accumulate(grid[i + 1]))

for i in range(4 * K):
    for j in range(1, 4 * K + 1):
        grid[i+1][j] += grid[i][j]


ans = 0
for i in range(2 * K):
    for j in range(2 * K):
        x = i
        y = j
        A = grid[x][y] - grid[x + K][y] - grid[x][y + K] + grid[x + K][y + K]
        x += K
        y += K
        B = grid[x][y] - grid[x + K][y] - grid[x][y + K] + grid[x + K][y + K]
        ans = max(ans, A + B)
print(ans)

Solution (Python):
class Accumulate2D: 
    def __init__(self, a):
        self.height = len(a)
        self.width = len(a[0])
        self.acc = self.accumulate(a)

    def accumulate(self,a):
        b = [[0]*(self.width+1) for i in range(self.height+1)]
        b[1][1] = a[0][0]
        for i in range(self.height):
            for j in range(self.width):
                b[i+1][j+1] = b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
        return b

    def sum(self, p, q):
        y1,x1 = p
        y2,x2 = q
        b = self.acc
        if y1>y2 or x1>x2:
            return 0
        else:
            return b[y2+1][x2+1]-b[y2+1][x1]-b[y1][x2+1]+b[y1][x1]


n,k = map(int, input().split())

kk = k*2

z = [[0]*kk for i in range(kk)]

for i in range(n):
    x,y,c = input().split()
    x = (int(x) + (k if c=='W'else 0)) % kk
    y = int(y) % kk
    z[x][y]+=1

z = Accumulate2D(z)

ans = 0
for i in range(k):
    for j in range(k):
        a = z.sum([0,0],[i-1,j-1])\
            + z.sum([i,j],[i+k-1,j+k-1])\
            + z.sum([0,j+k],[i-1,kk-1])\
            + z.sum([i+k,0],[kk-1,j-1])\
            + z.sum([i+k,j+k],[kk-1,kk-1])
        ans = max(ans,a,n-a)

print(ans)

Solution (Python):
import gc
n, k = map(int, input().split())
k2 = k * 2
b = [[0] * (k * 3) for _ in range(k * 3)]
for i in range(n):
    x, y, c = input().split()
    x = int(x) % k2
    y = int(y) % k2
    if c == 'W':
        x = (x + k) % k2

    b[x][y] += 1
    if x < k:
        b[x + k2][y] += 1
    if y < k:
        b[x][y + k2] += 1
    if x < k and y < k:
        b[x + k2][y + k2] += 1

b_cs = [[0] * (k * 3 + 1) for _ in range(k * 3 + 1)]
for i in range(k * 3):
    for j in range(k * 3):
        b_cs[i + 1][j +
                    1] = b_cs[i + 1][j] + b_cs[i][j + 1] - b_cs[i][j] + b[i][j]


def func_b(x, y):
    return b_cs[x + k][y + k] - b_cs[x + k][y] - b_cs[x][y + k] + b_cs[x][y]






ans = 0
for i in range(k):
    for j in range(k):
        cand = 0
        cand += func_b(i, j)
        cand += func_b(i + k, j + k)
        
        ans = max(ans, cand)

        cand = 0
        cand += func_b(i + k, j)
        cand += func_b(i, j + k)
        
        ans = max(ans, cand)

print(ans)

Solution (Python):
import numpy as np

n, k = map(int, input().split())
xyc = [list(input().split()) for _ in range(n)]

b = np.zeros((2 * k, k), np.int32)

for x, y, c in xyc:
    x = int(x)
    y = int(y)

    q, r = divmod(x, k)
    if q % 2:
        y += k
    x = r

    if c == "W":
        y += k

    y %= 2 * k

    b[y][x] += 1

b = np.vstack([b, b])
b = np.hstack([b, np.roll(b, k, axis=0)])

b = np.pad(b, (1, 0), "constant")
b = np.cumsum(b, axis=0)
b = np.cumsum(b, axis=1)

cnt = b[k:, k:] - b[k:, :-k] - b[:-k, k:] + b[:-k, :-k]
ans = cnt.max()
print(ans)

Solution (Python):
N,K = list(map(int,input().split()))

B = [[0]*(2*K) for i in range(2*K)]
W = [[0]*(2*K) for i in range(2*K)]

for i in range(N):
    x,y,c = input().split()
    x,y = int(x)%(2*K),int(y)%(2*K)
    if c=="B":
        B[x][y]+=1
    else:
        W[x][y]+=1

BS = [[0]*(2*K+1) for i in range(2*K+1)]
WS = [[0]*(2*K+1) for i in range(2*K+1)]

for i in range(2*K):
    for j in range(2*K):
        BS[i+1][j+1] = BS[i][j+1] + BS[i+1][j] - BS[i][j] + B[i][j]
        WS[i+1][j+1] = WS[i][j+1] + WS[i+1][j] - WS[i][j] + W[i][j]

def BOX(x1,y1,x2,y2,S):
    return S[x2][y2]-S[x1][y2]-S[x2][y1]+S[x1][y1]

def smax(a,b):
    if a<b:
        return b
    else:
        return a

ans = 0
for i in range(K):
    for j in range(K):
        count = 0
        count += BOX(0,0,i,j,WS) + BOX(i,0,i+K,j,BS) + BOX(i+K,0,2*K,j,WS)
        count += BOX(0,j,i,j+K,BS) + BOX(i,j,i+K,j+K,WS) + BOX(i+K,j,2*K,j+K,BS)
        count += BOX(0,j+K,i,2*K,WS) + BOX(i,j+K,i+K,2*K,BS) + BOX(i+K,j+K,2*K,2*K,WS)
        ans = smax(smax(count,N-count),ans)
print(ans)

Solution (Python):
import numpy as np

n, k = map(int, input().split())
xyc = [list(input().split()) for _ in range(n)]

b = np.zeros((3 * k - 1, 2 * k - 1), np.int64)

for x, y, c in xyc:
    x = int(x)
    y = int(y)

    q, r = divmod(x, k)
    if q % 2:
        y += k
    x = r

    if c == "W":
        y += k

    y %= 2 * k

    b[y][x] += 1

b[:k, k:] = b[k:2*k, :k-1]
b[k:2*k, k:] = b[:k, :k-1]
b[2*k:, :] = b[:k-1, :]

b = np.pad(b, (1, 0), "constant")

b = np.cumsum(b, axis=0)
b = np.cumsum(b, axis=1)

cnt = b[k:, k:] - b[k:, :-k] - b[:-k, k:] + b[:-k, :-k]
ans = cnt.max()
print(ans)

Solution (Python):
N, K = map(int, input().split())

Map = [[[0]*K for i in range(K)] for j in range(2)]
for i in range(N):
  x, y, c = input().split()
  x, y = int(x), int(y)
  if c == 'B':
    c = 0
  else:
    c = 1
  nx, ny = x//K, y//K
  if (nx + ny) % 2:
    c = 1 - c
  x %= K
  y %= K
  Map[c][x][y] += 1

def get_v(c, x, y):
  global Map
  if x < 0 or y < 0:
    return 0
  else:
    return Map[c][x][y]

for c in range(2):
  for x in range(K):
    for y in range(K):
      Map[c][x][y] += get_v(c, x-1, y) + get_v(c, x, y-1) - get_v(c, x-1, y-1)

ans = 0
for x in range(K+1):
  for y in range(K+1):
    b2 = get_v(0, x-1, K-1) + get_v(0, K-1, y-1) - 2*get_v(0, x-1, y-1)
    w1 = get_v(1, x-1, K-1) + get_v(1, K-1, y-1) - 2*get_v(1, x-1, y-1)
    b1 = Map[0][K-1][K-1] - b2
    w2 = Map[1][K-1][K-1] - w1
    ans = max(ans, b1+w1, b2+w2)

print(ans)

Solution (Python):
class Accumulate2D:
    def __init__(self, a):
        self.height = len(a)
        self.width = len(a[0])
        self.acc = self.accumulate(a)

    def accumulate(self,a):
        b = [[0]*(self.width+1) for i in range(self.height+1)]
        b[1][1] = a[0][0]
        for i in range(self.height):
            for j in range(self.width):
                b[i+1][j+1] = b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
        return b

    def sum(self, p, q):
        y1,x1 = p
        y2,x2 = q
        b = self.acc
        if y1>y2 or x1>x2:
            return 0
        else:
            return b[y2+1][x2+1]-b[y2+1][x1]-b[y1][x2+1]+b[y1][x1]


n,k = map(int, input().split())

kk = k*2

z = [[0]*kk for i in range(kk)]

for i in range(n):
    x,y,c = input().split()
    x = (int(x) + (k if c=='W'else 0)) % kk
    y = int(y) % kk
    z[x][y]+=1

z = Accumulate2D(z)

ans = 0
for i in range(k):
    for j in range(k):
        a = z.sum([0,0],[i-1,j-1])\
            + z.sum([i,j],[i+k-1,j+k-1])\
            + z.sum([0,j+k],[i-1,kk-1])\
            + z.sum([i+k,0],[kk-1,j-1])\
            + z.sum([i+k,j+k],[kk-1,kk-1])
        ans = max(ans,a,n-a)

print(ans)

Solution (Python):
class Accumulate2D:
    def __init__(self, a):
        self.height = len(a)
        self.width = len(a[0])
        self.acc = self.accumulate(a)

    def accumulate(self,a):
        b = [[0]*(self.width+1) for i in range(self.height+1)]
        b[1][1] = a[0][0]
        for i in range(self.height):
            for j in range(self.width):
                b[i+1][j+1] = b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
        return b

    def sum(self, p, q):
        y1,x1 = p
        y2,x2 = q
        b = self.acc
        if y1>y2 or x1>x2:
            return 0
        else:
            return b[y2+1][x2+1]-b[y2+1][x1]-b[y1][x2+1]+b[y1][x1]


n,k = map(int, input().split())

kk = k*2

z = [[0]*kk for i in range(kk)]

for i in range(n):
    x,y,c = input().split()
    x = int(x) % kk
    y = int(y) % kk
    if c=='W':
        x = (x+k)%kk
    z[x][y]+=1

z = Accumulate2D(z)

ans = 0
for i in range(k):
    for j in range(k):
        a = z.sum([0,0],[i-1,j-1])\
            + z.sum([i,j],[i+k-1,j+k-1])\
            + z.sum([0,j+k],[i-1,kk-1])\
            + z.sum([i+k,0],[kk-1,j-1])\
            + z.sum([i+k,j+k],[kk-1,kk-1])
        ans = max(ans,a,n-a)

print(ans)

Solution (Python):
N, K = map(int, input().split())
X = [input().split() for _ in range(N)]

grid = [[0] * (2 * K + 1) for _ in range(2 * K + 1)]
for x, y, c in X:
    x, y = map(int, [x, y])
    if c == "W":
        y += K
    grid[x % (2 * K) + 1][y % (2 * K) + 1] += 1
        
for i in range(2 * K):
    for j in range(2 * K):
        grid[i + 1][j + 1] += grid[i][j + 1]

for i in range(2 * K):
    for j in range(2 * K):
        grid[i + 1][j + 1] += grid[i + 1][j]

def count(x, y, i, j):
    return grid[x][y] + grid[i][j] - grid[x][j] - grid[i][y]

ans = 0
for i in range(K + 1):
    for j in range(K + 1):
        tmp = 0
        tmp += count(i + K, j + K, i, j)
        tmp += count(i, j, 0, 0)
        tmp += count(i, 2 * K, 0, j + K)
        tmp += count(2 * K, j, i + K, 0)
        tmp += count(2 * K, 2 * K, i + K, j + K)
        ans = max(ans, tmp, N - tmp)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
INF = float("inf")


class Acc2D:
    def __init__(self, grid):
        self.h, self.w = len(grid), len(grid[0])
        self.acc2D = self._build(self.h, self.w, grid)

    def _build(self, h, w, grid):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + grid[r][c]
        return ret

    def get(self, r1, r2, c1, c2):
        if r1 < 0:
            r1 = 0
        if r2 >= self.h:
            r2 = self.h
        if c1 < 0:
            c1 = 0
        if c2 >= self.w:
            c2 = self.w
        cnt = self.acc2D
        return cnt[r2][c2] - cnt[r1][c2] - cnt[r2][c1] + cnt[r1][c1]


def main():
    n, k = map(int, input().split())
    g = [[0] * (2 * k) for _ in range(2 * k)]
    for _ in range(n):
        x, y, c = input().split()
        x = int(x) % (2 * k)
        y = int(y) % (2 * k)
        if c == 'B':
            y = (y + k) % (2 * k)
        g[y][x] += 1
    acc2d = Acc2D(g)
    ans = 0
    for r in range(k):
        for c in range(k):
            tmp = acc2d.get(0, r, 0, c)
            tmp += acc2d.get(0, r, c + k, c + k * 2)
            tmp += acc2d.get(r, r + k, c, c + k)
            tmp += acc2d.get(r + k, r + k * 2, 0, c)
            tmp += acc2d.get(r + k, r + k * 2, c + k, c + k * 2)
            ans = max(ans, tmp, n - tmp)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
class Acc2D:
    def __init__(self, a):
        h, w = len(a), len(a[0])
        self.acc2D = self._build(h, w, a)
        self.H = len(self.acc2D)
        self.W = len(self.acc2D[0])

    def _build(self, h, w, a):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + a[r][c]
                
        return ret

    def get(self, r1, r2, c1, c2):
        
        if r1 < 0: r1 = 0
        if r2 >= self.H: r2 = self.H - 1
        if c1 < 0: c1 = 0
        if c2 >= self.W: c2 = self.W - 1
        acc2D = self.acc2D
        return acc2D[r2][c2] - acc2D[r1][c2] - acc2D[r2][c1] + acc2D[r1][c1]


def main():
    import sys
    input = sys.stdin.readline

    N, K = map(int, input().split())

    g = [[0] * (K * 2) for _ in range(K * 2)]
    for _ in range(N):
        x, y, c = input().split()
        x = int(x) % (K * 2)
        y = (int(y) - (K if c == 'B' else 0)) % (K * 2)
        g[x][y] += 1  

    acc2d = Acc2D(g)
    ans = -1
    for r in range(K):
        for c in range(K):
            t = acc2d.get(0, r, 0, c)
            t += acc2d.get(0, r, c + K, c + K * 2)
            t += acc2d.get(r, r + K, c, c + K)
            t += acc2d.get(r + K, r + K * 2, 0, c)
            t += acc2d.get(r + K, r + K * 2, c + K, c + K * 2)
            ans = max(ans, t, N - t)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
class Acc2D:
    def __init__(self, a, K):
        h, w = len(a), len(a[0])
        self.acc2D = self._build(h, w, a)
        self.K = K

    def _build(self, h, w, a):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + a[r][c]
                
        return ret

    def get(self, r1, r2, c1, c2):
        
        if r1 < 0: r1 = 0
        if r2 >= self.K * 2: r2 = self.K * 2
        if c1 < 0: c1 = 0
        if c2 >= self.K * 2: c2 = self.K * 2
        acc2D = self.acc2D
        return acc2D[r2][c2] - acc2D[r1][c2] - acc2D[r2][c1] + acc2D[r1][c1]


def main():
    import sys
    input = sys.stdin.readline

    N, K = map(int, input().split())

    g = [[0] * (K * 2) for _ in range(K * 2)]
    for _ in range(N):
        x, y, c = input().split()
        x = int(x) % (K * 2)
        y = (int(y) - (K if c == 'B' else 0)) % (K * 2)
        g[x][y] += 1  

    acc2d = Acc2D(g, K)
    ans = -1
    for r in range(K):
        for c in range(K):
            t = acc2d.get(0, r, 0, c)
            t += acc2d.get(0, r, c + K, c + K * 2)
            t += acc2d.get(r, r + K, c, c + K)
            t += acc2d.get(r + K, r + K * 2, 0, c)
            t += acc2d.get(r + K, r + K * 2, c + K, c + K * 2)
            ans = max(ans, t, N - t)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

n, k = map(int,input().split())
C = [list(input().split()) for i in range(n)]
D = [[0] * (2*k) for i in range(2*k)]

E = []
for i in range(n):
    x = int(C[i][0]) % (2*k)
    y = int(C[i][1]) % (2*k)
    if C[i][2] == "W":
        x = (x+k) % (2*k)
    E.append([x, y])
    x = (x+k) % (2*k)
    y = (y+k) % (2*k)
    E.append([x, y])

for i in range(2*n):
    xx = 0
    yy = 0
    x = E[i][0]
    y = E[i][1]

    D[x][y] += 1
    if x+k > 2*k:
        xx = 1
    if y+k > 2*k:
        yy = 1
    if xx == 1 and yy == 1:
        D[0][0] += 1
        D[x-k][0] -= 1
        D[0][y-k] -= 1
        D[x-k][y-k] += 1

        D[x][0] += 1
        D[x][y-k] -= 1

        D[0][y] += 1
        D[x-k][y] -= 1

    elif xx == 1:
        D[0][y] += 1
        D[x-k][y] -= 1
        if y != k:
            D[x][y+k] -= 1
            D[0][y+k] -= 1
            D[x-k][y+k] += 1
    elif yy == 1:
        D[x][0] += 1
        D[x][y-k] -= 1
        if x != k:
            D[x+k][y] -= 1
            D[x+k][0] -= 1
            D[x+k][y-k] += 1
    else:
        if x != k:
            D[x+k][y] -= 1
        if y != k:
            D[x][y+k] -= 1
        if x != k and y != k:
            D[x+k][y+k] += 1
    
    
for i in range(1, 2*k):
    D[0][i] += D[0][i-1]
    D[i][0] += D[i-1][0]

for i in range(1, 2*k):
    for j in range(1, 2*k):
        D[i][j] += D[i-1][j] + D[i][j-1] - D[i-1][j-1]

print(max([max(D[i]) for i in range(2*k)]))

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
ws = [[0] * K for _ in range(K)]
bs = [[0] * K for _ in range(K)]
for _ in range(N):
  x, y, c = input().split()
  x = int(x)
  y = int(y)
  t = x // K + y // K
  if t % 2:
    if c == "W": c = "B"
    elif c == "B": c = "W"
  ws[y % K][x % K] += int(c == "W")
  bs[y % K][x % K] += int(c == "B")
csw = [[0] * (K + 1) for _ in range(K + 1)]
csb = [[0] * (K + 1) for _ in range(K + 1)]
for i in range(K):
  for j in range(K):
    csw[i + 1][j + 1] = csw[i + 1][j] + csw[i][j + 1] - csw[i][j] + ws[i][j]
    csb[i + 1][j + 1] = csb[i + 1][j] + csb[i][j + 1] - csb[i][j] + bs[i][j]
res = 0
for i in range(K + 1):
  for j in range(K + 1):
    u = csw[-1][-1] - csw[i][-1] - csw[-1][j] + csw[i][j] * 2
    v = csb[i][-1] + csb[-1][j] - csb[i][j] * 2
    res = max(res, u + v)
    u = csb[-1][-1] - csb[i][-1] - csb[-1][j] + csb[i][j] * 2
    v = csw[i][-1] + csw[-1][j] - csw[i][j] * 2
    res = max(res, u + v)
print(res)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    a=[[[0]*K*2 for _ in range(K*2)] for _ in range(2)]
    for _ in range(N):
        x,y,c=input().split()
        x,y=int(x)%(K*2),int(y)%(K*2)
        if c=='W':
            a[0][y][x]+=1
        else:
            a[1][y][x]+=1
    S=[[[0]*(K*2+1) for _ in range(K*2+1)] for _ in range(2)]
    for k in range(2):
        for i in range(K*2):
            for j in range(K*2):
                S[k][i+1][j+1]=S[k][i][j+1]+S[k][i+1][j]-S[k][i][j]+a[k][i][j]
    def getsum(k,y1,y2,x1,x2):
        return S[k][x2][y2]-S[k][x1][y2]-S[k][x2][y1]+S[k][x1][y1]
    ans=0
    for k in range(2):
        for i in range(K+1):
            for j in range(K+1):
                tmp=0
                tmp+=getsum(k,0,i,0,j)+getsum(k,i+K,K*2,0,j)+getsum(k,0,i,j+K,K*2)+getsum(k,i+K,K*2,j+K,K*2)+getsum(k,i,i+K,j,j+K)
                tmp+=getsum(not k,i,i+K,0,j)+getsum(not k,i,i+K,j+K,K*2)+getsum(not k,0,i,j,j+K)+getsum(not k,i+K,K*2,j,j+K)
                ans=max(ans,tmp)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import io

nime, mike = map(int, input().split())
mod = 2*mike
array = [[0]*(2*mike+1) for _ in range(2*mike+1)]

def gen_pattern(x):
    if x < mike-1:
        return [[0, x+1], [x+mike+1, 2*mike]]
    else:
        return [[x-mike+1, x+1]]

for _ in range(nime):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W':
        y += mike
    x %= mod
    y %= mod
    for tmp in [0, mike]:
        for l, r in gen_pattern((x+tmp) % mod):
            for b, t in gen_pattern((y+tmp) % mod):
                array[l][b] += 1
                array[l][t] -= 1
                array[r][b] -= 1
                array[r][t] += 1
print(np.max(np.cumsum(np.cumsum(array, axis=0), axis=1)))