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):
n, k = map(int, input().split())
s = [[0] * k for _ in range(2 * k + 1)]
for _ in range(n):
    x, y, c = input().split()
    x, y = int(x), int(y)
    x -= (x // (2 * k)) * (2 * k)
    y -= (y // (2 * k)) * (2 * k)
    if x >= k and y >= k:
        x -= k
        y -= k
    elif y >= k:
        x += k
        y -= k
    if c == "B":
        if x >= k:
            x -= k
        else:
            x += k
    s[x + 1][y] += 1
for i in range(2 * k):
    for j in range(k):
        s[i + 1][j] += s[i][j]
ans = 0
for i in range(k):
    cnt = 0
    for j in range(k):
        cnt += (s[i + k][j] - s[i][j])
    ans = max(ans, cnt, n - cnt)
    for j in range(k):
        cnt -= (2 * (s[i + k][j] - s[i][j]))
        cnt += s[2 * k][j]
        ans = max(ans, cnt, n - cnt)
print(ans)

Solution (Python):
import sys
import array
input = sys.stdin.readline
N,K = map(int,input().split())
xyc = []
for i in range(N):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    xyc.append([x % (2*K), y % (2*K), c])

wmap = [array.array('I',[0]*3*K) for i in [0]*3*K]
hmap = [array.array('I',[0]*3*K) for i in [0]*3*K]
for x,y,c in xyc:
    if c == 'W':
        wmap[y][x] += 1
        if y < K:
            wmap[y+2*K][x] += 1
        if x < K:
            wmap[y][x+2*K] += 1
        if x < K and y < K:
            wmap[y+2*K][x+2*K] += 1
    else:
        hmap[y][x] += 1
        if x < K:
            hmap[y][x+2*K] += 1
        if y < K:
            hmap[y+2*K][x] += 1
        if x < K and y < K:
            hmap[y+2*K][x+2*K] += 1

def accum(L):
    res = [0]*(len(L)+1)
    res[1] = L[0]
    for i in range(2,len(L)+1):
        res[i] = res[i-1] + L[i-1]
    return res
wcumsum = [array.array('I',[0]*(3*K+1))] + [array.array('I',accum(row)) for row in wmap]
hcumsum = [array.array('I',[0]*(3*K+1))] + [array.array('I',accum(row)) for row in hmap]

for y in range(1,3*K+1):
    for x in range(3*K+1):
        wcumsum[y][x] += wcumsum[y-1][x]
        hcumsum[y][x] += hcumsum[y-1][x]

def cs2(m, ltx, lty, rbx, rby):
    S = m[rby-1][rbx-1]
    S -= m[rby-1][ltx-1]
    S -= m[lty-1][rbx-1]
    S += m[lty-1][ltx-1]
    return S

ans = 0
for y in range(1,K+1):
    for x in range(1,K+1):
        ltw = cs2(wcumsum,x,y,x+K, y+K)
        rbw = cs2(wcumsum,x+K,y+K,x+2*K, y+2*K)
        lbh = cs2(hcumsum,x,y+K,x+K, y+2*K)
        rth = cs2(hcumsum,x+K,y,x+2*K, y+K)
        temp = ltw + rbw + lbh + rth
        ans = max(ans,temp)

        ltw = cs2(hcumsum,x,y,x+K, y+K)
        rbw = cs2(hcumsum,x+K,y+K,x+2*K, y+2*K)
        lbh = cs2(wcumsum,x,y+K,x+K, y+2*K)
        rth = cs2(wcumsum,x+K,y,x+2*K, y+K)
        temp = ltw + rbw + lbh + rth
        ans = max(ans,temp)

print(ans)

Solution (Python):
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


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

ww=[[0]*(2*k+1) for i in range(2*k+1)]
bb=[[0]*(2*k+1) for i in range(2*k+1)]

for i in range(n):
    x,y,c=xyc[i]
    x,y=int(x),int(y)
    if c=="W":
        ww[x%(2*k)+1][y%(2*k)+1]+=1
    else:
        bb[x%(2*k)+1][y%(2*k)+1]+=1

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


def cnt(i1,i2,j1,j2,lst):
    return lst[i2+1][j2+1]-lst[i1+1][j2+1]-lst[i2+1][j1+1]+lst[i1+1][j1+1]

ans=0
for i in range(k+1):
    for j in range(k+1):
        w,b=0,0
        
        w+=cnt(-1, i-1, -1, j-1, ww)
        
        w+=cnt(i-1, i+k-1, j-1, j+k-1, ww)
        
        w+=cnt(-1, i-1, j+k-1, 2*k-1, ww)
        
        w+=cnt(i+k-1, 2*k-1, -1, j-1, ww)
        
        w+=cnt(i+k-1, 2*k-1, j+k-1, 2*k-1, ww)

        b+=cnt(-1, i-1, j-1, j+k-1, bb)
        b+=cnt(i-1, i+k-1, -1, j-1, bb)
        b+=cnt(i+k-1, 2*k-1, j-1, j+k-1, bb)
        b+=cnt(i-1, i+k-1, j+k-1, 2*k-1, bb)
        
        ans=max(ans,w+b)
ww,bb=copy.deepcopy(bb),copy.deepcopy(ww)
for i in range(k+1):
    for j in range(k+1):
        w,b=0,0
        
        w+=cnt(-1, i-1, -1, j-1, ww)
        
        w+=cnt(i-1, i+k-1, j-1, j+k-1, ww)
        
        w+=cnt(-1, i-1, j+k-1, 2*k-1, ww)
        
        w+=cnt(i+k-1, 2*k-1, -1, j-1, ww)
        
        w+=cnt(i+k-1, 2*k-1, j+k-1, 2*k-1, ww)

        b+=cnt(-1, i-1, j-1, j+k-1, bb)
        b+=cnt(i-1, i+k-1, -1, j-1, bb)
        b+=cnt(i+k-1, 2*k-1, j-1, j+k-1, bb)
        b+=cnt(i-1, i+k-1, j+k-1, 2*k-1, bb)
        
        ans=max(ans,w+b)
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



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

for i 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
    v[x][y] += 1



def cumsum2(v):
    
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
cumsum2(v)

def sub(c, i, j):
    i %= 2*k
    j %= 2*k
    l = []
    if i<=k and j<=k:
        l = [[i,i+k,j,j+k]]
    elif i>k and j<=k:
        l = [[i,2*k,j,j+k], [0,i-k,j,j+k]]
    elif i<=k and j>k:
        l = [[i,i+k,j,2*k], [i,i+k,0,j-k]]
    else:
        l = [[i,2*k,j,2*k], [0,i-k,j,2*k], [i,2*k,0,j-k], [0,i-k,0,j-k]]
    return sum((c[z][w] - c[z][y] - c[x][w] + c[x][y]) for x,z,y,w in l)
ans = -1
for i in range(2*k):
    for j in range(2*k-i):
        val0 = sub(v, i,j) + sub(v, i+k, j+k)


        ans = max(ans, val0)
print(ans)

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

A = [[ 0 for _ in range(K2) ] for _ in range(K2)]
for _ in range(N):
  x,y,c = input().split()
  x,y = int(x) % (K2), int(y) % (K2)
  if c == 'W':
    y = (y+K) % (K2)
  
  
  A[x][y] += 1

for i in range(K2):
  A[i] = A[i]  + A[i][:K-1]
  
for i in range(K-1):
  A.append(A[i])
  




B = [[ 0 for _ in range(K2+K) ] for _ in range(K2+K)]
for i in range(K2+K-1):
  for j in range(K2+K-1):
    B[i+1][j+1] = B[i+1][j] + B[i][j+1] - B[i][j] + A[i][j]
    
ans = 0
for i in range(K):
  for j in range(K):
    
    wk = 0
    wk += B[i+K][j+K] - B[i][j+K] - B[i+K][j] + B[i][j]
    wk += B[i+K2][j+K2] - B[i+K][j+K2] - B[i+K2][j+K] + B[i+K][j+K]
    
    ans = max(wk,N-wk,ans) 


  
print(ans)

Solution (Python):
import sys
import numpy as np

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  wb={'W':1,'B':0}
  n,k=map(int,readline().split())
  xyc=[l.split() for l in read().splitlines()]
  xy=[[int(lst[0]) % (2*k),(int(lst[1])+k*wb[lst[2]]) % (2*k)] for lst in xyc]
  mat=np.zeros((k+1,2*k+1),dtype='int64')
  cand=np.zeros((k+1,k+1),dtype='int64')
  for e in xy:
    f0=e[0]>=k
    f1=e[1]>=k
    mat[e[0]-f0*k+1,e[1]+(-1)**f1*f0*k+1]+=1
  mat=np.cumsum(mat,axis=0)
  mat=np.cumsum(mat,axis=1)
  cand=mat[k,2*k]-mat[k,k:2*k+1]+mat[k,:k+1]\
       -np.reshape(mat[:k+1,2*k],(k+1,1))+2*mat[:,k:2*k+1]-2*mat[:,:k+1]
  print(max(np.max(cand),mat[k,2*k]-np.min(cand)))
  
if __name__=='__main__':
  main()

Solution (Python):
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((4 * K + 1, 4 * K + 1), dtype=np.int64)
for x, y, c in zip(XYC[::3], XYC[1::3], XYC[2::3]):
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K
    x = x % (2 * K)
    y = y % (2 * K)
    board[x, y] += 1
    board[(x + K) % (2 * K), (y + K) % (2 * K)] += 1
board[1 + 2 * K:, 1 + 2 * K:] = board[:2 * K, :2 * K]
board[1:1 + 2 * K, 1 + 2 * K:] = board[1 + 2 * K:, 1 + 2 * K:]
board[1 + 2 * K:, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[1:1 + 2 * K, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[0, :] = 0
board[:, 0] = 0
for j in range(1, 3 * K):
    board[:, j] += board[:, j - 1]
for j in range(1, 3 * K):
    board[j, :] += board[j - 1, :]
ans = np.max(board[K:3 * K, K:3 * K] + board[:2 * K, :2 * K] -
             board[:2 * K, K:3 * K] - board[K:3 * K, :2 * K])
print(ans)

Solution (Python):
import itertools
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((4 * K + 1, 4 * K + 1), dtype=np.uint16)
for x, y, c in zip(XYC[::3], XYC[1::3], XYC[2::3]):
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K
    x = x % (2 * K)
    y = y % (2 * K)
    board[x, y] += 1
    board[(x + K) % (2 * K), (y + K) % (2 * K)] += 1
board[1 + 2 * K:, 1 + 2 * K:] = board[:2 * K, :2 * K]
board[1:1 + 2 * K, 1 + 2 * K:] = board[1 + 2 * K:, 1 + 2 * K:]
board[1 + 2 * K:, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[1:1 + 2 * K, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[0, :] = 0
board[:, 0] = 0
for j in range(1, 3 * K):
    board[:, j] += board[:, j - 1]
for j in range(1, 3 * K):
    board[j, :] += board[j - 1, :]
ans = np.max(board[K:3 * K, K:3 * K] + board[:2 * K, :2 * K] -
             board[:2 * K, K:3 * K] - board[K:3 * K, :2 * K])
print(ans)

Solution (Python):
import itertools
import numpy as np
N, K, *XYC = open(0).read().split()
N = int(N)
K = int(K)
board = np.zeros((4 * K + 1, 4 * K + 1), dtype=np.uint16)
for x, y, c in zip(XYC[::3], XYC[1::3], XYC[2::3]):
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K
    x = x % (2 * K)
    y = y % (2 * K)
    board[x, y] += 1
    board[(x + K) % (2 * K), (y + K) % (2 * K)] += 1
board[1 + 2 * K:, 1 + 2 * K:] = board[:2 * K, :2 * K]
board[1:1 + 2 * K, 1 + 2 * K:] = board[1 + 2 * K:, 1 + 2 * K:]
board[1 + 2 * K:, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[1:1 + 2 * K, 1:1 + 2 * K] = board[1 + 2 * K:, 1 + 2 * K:]
board[0, :] = 0
board[:, 0] = 0
for j in range(1, 1 + 4 * K):
    board[:, j] += board[:, j - 1]
for j in range(1, 1 + 4 * K):
    board[j, :] += board[j - 1, :]
ans = np.max(board[K:3 * K, K:3 * K] + board[:2 * K, :2 * K] -
             board[:2 * K, K:3 * K] - board[K:3 * K, :2 * K])
print(ans)

Solution (Python):
from numpy import*;N,K=map(int,input().split());m=zeros((3*K,3*K),dtype=int);L=2*K;o=0
for _ in[0]*N:x,y,c=input().split();t=c=='W';m[int(x)%L,int(y)%L]+=2*t-1;o+=t
for _ in[0,0]:m[L:]=m[:K];m=cumsum(m,axis=0);m[:L]-=m[K:];m=m.T
m=m[:L,:L];print(o-int((m+roll(roll(m,K,axis=0),K,axis=1)).min()))

Solution (Python):
n,k=map(int,input().split());m=2*k;a=[(m+1)*[0]for _ in[0]*(m+1)];z=lambda i,j:(a[i][j]-a[i-k][j]-a[i][j-k]+a[i-k][j-k])*2+a[m][m]-a[i][m]-a[m][j]+a[i-k][m]+a[m][j-k]
for _ in[0]*n:x,y,c=input().split();x=int(x);y=int(y)+k*(c=="B");a[x%m+1][y%m+1]+=1
for i in range(m):
  for j in range(m):a[i+1][j+1]+=a[i][j+1]+a[i+1][j]-a[i][j]
print(max(max(max(z(i,j),n-z(i,j))for j in range(k,m+1))for i in range(k,m+1)))

Solution (Python):
n,k=map(int,input().split())
a=[(2*k+1)*[0]for _ in range(2*k+1)]
for _ in range(n):
  x,y,c=input().split()
  x=int(x)
  y=int(y)
  if c=="B":y+=k
  x%=2*k
  y%=2*k
  a[x+1][y+1]+=1
ans=0
for i in range(1,2*k+1):
  for j in range(1,2*k+1):a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]
for i in range(k,2*k+1):
  for j in range(k,2*k+1):
    t=a[i][j]-a[i-k][j]-a[i][j-k]+a[i-k][j-k]
    t+=a[i-k][j-k]
    t+=a[2*k][j-k]-a[i][j-k]
    t+=a[i-k][2*k]-a[i-k][j]
    t+=a[2*k][2*k]-a[i][2*k]-a[2*k][j]+a[i][j]
    ans=max(ans,t,n-t)
print(ans)

Solution (Python):
def cumsum_2d(arr, cumsum_from='top_left'):
    K = len(arr)  
    ret = [[0 for _ in range(K)] for _ in range(K)]
    
    for y in range(K):
        v = 0
        for x in range(K):
            if 'right' in cumsum_from:
                x = K - 1 - x
            v += arr[y][x]
            ret[y][x] = v
    
    for y in range(1, K):
        before_y = y - 1
        if 'bottom' in cumsum_from:
            y = K - 1 - y
            before_y = y + 1
        for x in range(K):
            ret[y][x] += ret[before_y][x]
    return ret


def main():
    N, K = list(map(int, input().split()))
    
    field_even = [[0 for _ in range(K)] for _ in range(K)]
    field_odd = [[0 for _ in range(K)] for _ in range(K)]
    for _ in range(N):
        X, Y, C = input().split()
        X = int(X) - 1
        Y = int(Y) - 1
        white_flag = 1 if C == 'W' else 0
        score = X // K + Y // K + white_flag
        if score % 2 == 0:
            field_even[Y % K][X % K] += 1
        else:
            field_odd[Y % K][X % K] += 1
    
    even_tr = cumsum_2d(field_even, 'top_right')
    even_br = cumsum_2d(field_even, 'bottom_right')
    even_tl = cumsum_2d(field_even, 'top_left')
    even_bl = cumsum_2d(field_even, 'bottom_left')
    odd_tr = cumsum_2d(field_odd, 'top_right')
    odd_br = cumsum_2d(field_odd, 'bottom_right')
    odd_tl = cumsum_2d(field_odd, 'top_left')
    odd_bl = cumsum_2d(field_odd, 'bottom_left')
    
    
    ans = 0
    for y in range(-1, K):
        for x in range(-1, K):
            
            c = 0
            if y >= 0 and x >= 0:
                c += even_tl[y][x]
            if y + 1 < K and x + 1 < K:
                c += even_br[y + 1][x + 1]
            if y + 1 < K and x >= 0:
                c += odd_bl[y + 1][x]
            if y >= 0 and x + 1 < K:
                c += odd_tr[y][x + 1]
            ans = max(ans, c)
            
            c = 0
            if y >= 0 and x >= 0:
                c += odd_tl[y][x]
            if y + 1 < K and x + 1 < K:
                c += odd_br[y + 1][x + 1]
            if y + 1 < K and x >= 0:
                c += even_bl[y + 1][x]
            if y >= 0 and x + 1 < K:
                c += even_tr[y][x + 1]
            ans = max(ans, c)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,K=map(int, input().split())
A=[[0]*(2*K) for j in range(2*K)]
for i in range(N):
  x,y,a=input().split()
  x,y=int(x),int(y)
  if a=='B':
    y+=K
  x=x%(2*K)
  y=y%(2*K)
  A[y][x]+=1
def da_generate(h,w,a):
    da = [[0]*w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1,w):
        da[0][i] = da[0][i-1]+a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i-1][j]+cnt_w
    return da


def da_calc(p,q,x,y):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y]-da[x][q-1]
    if q == 0:
        return da[x][y]-da[p-1][y]
    return da[x][y]-da[p-1][y]-da[x][q-1]+da[p-1][q-1]
f=2*K
da=da_generate(f,f,A)
ans=0
for i in range(K+1):
  for j in range(K+1):
    a=da_calc(j,i,j+K-1,i+K-1)   
    y1,y2,x1,x2=i,i+K-1,j,j+K-1
    if x1>0 and y1>0:
      a+=da_calc(0,0,x1-1,y1-1)
    if x1>0 and y2<f:
      a+=da_calc(0,y2+1,x1-1,f-1)
    if x2<f and y1>0:
      a+=da_calc(x2+1,0,f-1,y1-1)
    if x2<f and y2<f:
      a+=da_calc(x2+1,y2+1,f-1,f-1)
    ans=max(ans,a,N-a)
print(ans)

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()

N,K = MI()

black = [[0]*K for _ in range(K)]
white = [[0]*K for _ in range(K)]
for _ in range(N):
    x,y,c = map(str,S().split())
    x,y = int(x),int(y)
    if ((x//K + y//K) % 2 == 0 and c == 'B') or ((x//K + y//K) % 2 == 1 and c == 'W'):
        black[x % K][y % K] += 1
    else:
        white[x % K][y % K] += 1

black_accumulate = [[0]*(K+1)] + [[0]+black[i] for i in range(K)]  
white_accumulate = [[0]*(K+1)] + [[0]+white[i] for i in range(K)]  
for i in range(1,K+1):
    for j in range(1,K+1):
        black_accumulate[i][j] += black_accumulate[i][j-1]
        white_accumulate[i][j] += white_accumulate[i][j-1]
for i in range(1,K+1):
    for j in range(1,K+1):
        black_accumulate[i][j] += black_accumulate[i-1][j]
        white_accumulate[i][j] += white_accumulate[i-1][j]

def f(s,t,u,v):  
    return black_accumulate[t][v]-black_accumulate[t][u]-black_accumulate[s][v]+black_accumulate[s][u]
def g(s,t,u,v):  
    return white_accumulate[t][v]-white_accumulate[t][u]-white_accumulate[s][v]+white_accumulate[s][u]

ans = 0
for i in range(1,K+1):  
    for j in range(1,K+1):  
        ans = max(ans,f(0,i,0,j) + f(i,K,j,K) + g(0,i,j,K) + g(i,K,0,j))
        ans = max(ans,g(0,i,0,j) + g(i,K,j,K) + f(0,i,j,K) + f(i,K,0,j))
print(ans)

Solution (Python):
import numpy as np
 
N,K=map(int, input().split())
p=[list(input().split()) for _ in range(N)]
grid = [[[0]*2 for j in range(K)] for i in range(K)]

for i in range(N):
  x, y, c = p[i]
  x, y = int(x), int(y)
  mx, my = x%K, y%K
  f = False
  if (x//K)%2 != (y//K)%2:
    f = not f
  if c == "W":
    f = not f
  if f:
    grid[0][0][0] += 1
    grid[mx][0][0] -= 1
    grid[0][my][0] -= 1
    grid[mx][my][0] += 2
  else:
    grid[0][my][0] += 1
    grid[mx][0][0] += 1
    grid[mx][my][0] -= 2
  f = False
  if (x//K)%2 != (y//K)%2:
    f = not f
  if c == "B":
    f = not f
  if f:
    grid[0][0][1] += 1
    grid[mx][0][1] -= 1
    grid[0][my][1] -= 1
    grid[mx][my][1] += 2
  else:
    grid[0][my][1] += 1
    grid[mx][0][1] += 1
    grid[mx][my][1] -= 2
grid = np.array(grid)
grid = np.cumsum(grid, axis=0)
grid = np.cumsum(grid, axis=1)
print(int(np.max(grid)))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





n, k = getNM()
imos = [[0 for i in range(k)] for j in range(k)]
white = 0
for i in range(n):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == "W":
        c = 1
    else:
        c = 0
    x %= 2*k
    y %= 2*k

    if x > k-1:
        x -= k
        c += 1
    if y > k-1:
        y -=k
        c += 1
    c %= 2

    if c == 1:
        white += 1
        imos[x][y] -= 1
    else:
        imos[x][y] += 1

for i in range(k):
    for j in range(k-1):
        imos[i][j+1] += imos[i][j]

for j in range(k):
    for i in range(k-1):
        imos[i+1][j] += imos[i][j]

ans = 0
for i in range(k):
    for j in range(k):
        exp = imos[k-1][k-1] - imos[k-1][j] - imos[i][k-1] + 2 * imos[i][j] + white
        ans = max(ans, max(exp, n - exp))

print(ans)

Solution (Python):
n,k=map(int,input().split())
g=[[[0,0] for i in range(k)] for j in range(k)]

for i in range(n):
    x,y,c=input().split()
    x,y=int(x),int(y)
    if y%(2*k)<k and x%(2*k)<k:
        g[y%(2*k)][x%(2*k)][c=="W"]+=1
    elif y%(2*k)<k:
        g[y%(2*k)][x%(2*k)-k][c=="B"]+=1
    elif x%(2*k)<k:
        g[y%(2*k)-k][x%(2*k)][c=="B"]+=1
    else:
        g[y%(2*k)-k][x%(2*k)-k][c=="W"]+=1

ac=[[[0]*(k+1) for i in range(k+1)] for l in range(2)]
for l in range(2):
    for i in range(k):
        for j in range(k):
            ac[l][i+1][j+1]=ac[l][i][j+1]+ac[l][i+1][j]-ac[l][i][j]+g[i][j][l]

ans=0
for i in range(k):
    for j in range(k):
        ans=max(ac[0][k][k]-ac[0][i][k]-ac[0][k][j]+2*ac[0][i][j]+ac[1][i][k]+ac[1][k][j]-2*ac[1][i][j],ans)
        ans=max(ac[1][k][k]-ac[1][i][k]-ac[1][k][j]+2*ac[1][i][j]+ac[0][i][k]+ac[0][k][j]-2*ac[0][i][j],ans)
print(ans)

Solution (Python):
n,k = map(int, input().split())
square = [[0 for i in range(k*2)] for j in range(k*2)]
 
for i in range(n):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c=='W':
        y += k
    x = x%(k*2)
    y = y%(k*2)
    square[x][y] += 1
 
class CumulativeSum2d():
    def __init__(self, collection_2d):
        yl = len(collection_2d)
        xl = len(collection_2d[0])
        self.data = [[0] * (xl+1) for _ in range(yl+1)]
        for y in range(1, yl+1):
            for x in range(1, xl+1):
                top_sum         = self.data[y-1][x]
                left_sum        = self.data[y][x-1]
                dup_sum         = self.data[y-1][x-1]
                self.data[y][x] = top_sum + left_sum - dup_sum
                self.data[y][x] += collection_2d[y-1][x-1]
 
    def query(self, x, y, x1, y1):
        return self.data[y1][x1] - self.data[y-1][x1] - self.data[y1][x-1] + self.data[y-1][x-1]
 
cs = CumulativeSum2d(square)
 
"""
xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx
 
oxxxoo
oxxxoo
oxxxoo
xoooxx
xoooxx
xoooxx
 
0xxxoo
x000xx
x000xx
x000xx
0xxxoo
0xxxoo
 
xoooxx
oxxxoo
oxxxoo
oxxxoo
xoooxx
xoooxx
 
1 k  2k
xxxooo
xxxooo
xxxooo
000xxx
000xxx
000xxx
 
          1xk  2k
         10xxxoo
         yx000xx
         kx000xx
          x000xx
          0xxxoo
        2k0xxxoo
 
left top position determine everything
"""
ans = 0
for x in range(1,k*2+1):
    for y in range(1,k*2+1):
        sumd = 0
        
        sumd += cs.query(x, y, min(k*2, x+k-1), min(k*2, y+k-1))
        """
        """
        if x-k>1:
            
            sumd += cs.query(1, y, x-k-1, min(k*2, y+k-1))
        if y-k>1:
            
            sumd += cs.query(x, 1, min(k*2, x+k-1), y-k-1)
        if x>1 and y>1:
            
            sumd += cs.query(max(1, x-k), max(1, y-k), x-1, y-1)
        if x>1 and y-k<1:
            
            sumd += cs.query(max(1, x-k), y+k, x-1, k*2)
        if x-k<1 and y>1:
            
            sumd += cs.query(x+k, max(1, y-k), k*2, y-1)
        if x-k<1 and y-k<1:
            
            sumd += cs.query(x+k, y+k, k*2, k*2)
        ans = max(sumd, ans)
 
print(ans , flush=True)

Solution (Python):
n,k = map(int, input().split())
square = [[0]*k*2 for _ in range(k*2)]

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

class CumulativeSum2d():
    def __init__(self, collection_2d):
        yl = len(collection_2d)
        xl = len(collection_2d[0])
        self.data = [[0] * (xl+1) for _ in range(yl+1)]
        for y in range(1, yl+1):
            for x in range(1, xl+1):
                top_sum         = self.data[y-1][x]
                left_sum        = self.data[y][x-1]
                dup_sum         = self.data[y-1][x-1]
                self.data[y][x] = top_sum + left_sum - dup_sum
                self.data[y][x] += collection_2d[y-1][x-1]

    def query(self, x, y, x1, y1):
        return self.data[y1][x1] - self.data[y-1][x1] - self.data[y1][x-1] + self.data[y-1][x-1]

cs = CumulativeSum2d(square)

"""
xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx

oxxxoo
oxxxoo
oxxxoo
xoooxx
xoooxx
xoooxx

0xxxoo
x000xx
x000xx
x000xx
0xxxoo
0xxxoo

xoooxx
oxxxoo
oxxxoo
oxxxoo
xoooxx
xoooxx

1 k  2k
xxxooo
xxxooo
xxxooo
000xxx
000xxx
000xxx

          1xk  2k
         10xxxoo
         yx000xx
         kx000xx
          x000xx
          0xxxoo
        2k0xxxoo

left top position determine everything
"""
ans = 0



























s = cs.data
for y in range(k, k*2+1):
    for x in range(k, k*2+1):
        d = cs.query(x-k+1, y-k+1, x, y)
        d += s[y-k][x-k]
        d += s[k*2][x-k] - s[y][x-k]
        d += s[y-k][k*2] - s[y-k][x]
        d += cs.query(x+1,y+1,k*2,k*2)
        ans = max(ans, d, n-d)

print(ans , flush=True)

Solution (Python):
import numpy as np

def main():
    n, k = map(int, input().split())
    p = [list(map(str, input().split())) for _ in range(n)]
    arr = [[[0]*2 for j in range(k)] for i in range(k)]
    for i in range(n):
        x, y, c = p[i]
        x, y = int(x), int(y)
        mx, my = x%k, y%k
        f = False
        if (x//k)%2 != (y//k)%2:
            f = not f
        if c == "W":
            f = not f
        if f:
            arr[0][0][0] += 1
            arr[mx][0][0] -= 1
            arr[0][my][0] -= 1
            arr[mx][my][0] += 2
        else:
            arr[0][my][0] += 1
            arr[mx][0][0] += 1
            arr[mx][my][0] -= 2
        f = False
        if (x//k)%2 != (y//k)%2:
            f = not f
        if c == "B":
            f = not f
        if f:
            arr[0][0][1] += 1
            arr[mx][0][1] -= 1
            arr[0][my][1] -= 1
            arr[mx][my][1] += 2
        else:
            arr[0][my][1] += 1
            arr[mx][0][1] += 1
            arr[mx][my][1] -= 2
    np_arr = np.array(arr)
    np_arr = np.cumsum(np_arr, axis=0)
    np_arr = np.cumsum(np_arr, axis=1)
    print(int(np.max(np_arr)))

if __name__ == "__main__":
    main()

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
k2 = k*2

a = [[0]*k2 for i in range(k2)]
for i in range(n):
    x,y,c = input().split()
    xx = int(x)%k2
    yy = (int(y)+(k if c=='B' else 0))%k2
    
    a[xx][yy] += 1


racc = [[0]*k2 for i in range(k2)]
rx = [[0]*k2 for i in range(k2)]
for i in range(k2):
    
    
    for j in range(k2):
        racc[i][j] = (0 if j==0 else racc[i][j-1])+a[i][j]
    rsum = sum(a[i])
    for j in range(k):
        rx[i][j] = racc[i][j+k-1]-(0 if j==0 else racc[i][j-1])
    for j in range(k,k2):
        rx[i][j] = rsum-rx[i][j-k]

cacc = [[0]*k2 for i in range(k2)]
cx = [[0]*k2 for i in range(k2)]
for i in range(k2):
    
    
    for j in range(k2):
        cacc[j][i] = (0 if j==0 else cacc[j-1][i])+rx[j][i]
if False and DBG:
    for i in range(k2):
        ddprint(a[i])
    ddprint('')
    for i in range(k2):
        ddprint(rx[i])
    ddprint('')
    for i in range(k2):
        ddprint(cacc[i])

mx = 0
for i in range(k2):
    
    
    for j in range(k2):
        ii = (i+k)%k2
        if j<k:
            v1 = cacc[j+k-1][i]-(0 if j==0 else cacc[j-1][i])
            v2 = cacc[k2-1][ii] - (cacc[j+k-1][ii]- \
                   (0 if j==0 else cacc[j-1][ii]))
        else:
            jj = j-k
            v1 = cacc[k2-1][i] - (cacc[jj+k-1][i]- \
                   (0 if jj==0 else cacc[jj-1][i]))
            v2 = cacc[jj+k-1][ii]- \
                   (0 if jj==0 else cacc[jj-1][ii])
        mx = max(mx,v1+v2)
print(mx)

Solution (Python):
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


def main():
    n, k = map(int, input().split())
    K = k * 2
    """
    K * Kに点を全て移したので、この中で黒模様の左下の頂点を全探索。
    二次元累積和で各場合についてO(1)で計算可能。

    まず前準備として白マスはxかyに関してkずらすことで黒マスにできる。こうすれば記述量はもっと減らせた。
    """
    hope = [[0] * (K + 1) for _ in range(K + 1)]
    for _ in range(n):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == 'B':
            """あとで累積和を0-indexedで取る都合上、頂点座標は1-indexedにしておく。"""
            hope[1 + y % K][1 + x % K] += 1
        if c == 'W':
            hope[1 + (y + k) % K][1 + x % K] += 1

    """
    二次元累積和の書き方に悩んでたのは失態。
    やってみて気づいたが、やはり累積和は0-indexedにしないと後々の取り扱いが非常に面倒。
    """
    sumB = [[0] * (K + 1) for _ in range(K + 1)]
    for y in range(1, K + 1):
        for x in range(1, K + 1):
            sumB[y][x] = sumB[y-1][x] + sumB[y][x-1] + hope[y][x] - sumB[y-1][x-1]

    def calc_sum(x0, y0, x1, y1):
        
        return sumB[y1][x1] - sumB[y0-1][x1] - sumB[y1][x0-1] + sumB[y0-1][x0-1]

    """
    あとは黒四角の左下頂点(x, y)に関して全探索。
    """
    ans = 0
    for y in range(1, K+1):
        for x in range(1, k+1):
            if y <= k:
                val = (calc_sum(1, 1, x-1, y-1) + calc_sum(x, y, x+k-1, y+k-1)
                        + calc_sum(x+k, y+k, K, K) + calc_sum(x+k, 1, K, y-1)
                        + calc_sum(1, y+k, x-1, K))
                ans = max(ans, val)
            else:
                val = (calc_sum(x, 1, x+k-1, y-k-1) + calc_sum(1, y-k, x-1, y-1)
                        + calc_sum(x+k, y-k, K, y-1) + calc_sum(x, y, x+k-1, K))
                ans = max(ans, val)
    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = map(int, readline().split())
    l = 2 * k
    grid = [[0] * (2 * l) for _ in range(2 * l)]

    for i in range(n):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "W":
            x += k
        mx, my = x % l, y % l
        grid[mx][my] += 1
        grid[mx + k][my] -= 1
        grid[mx][my + k] -= 1
        grid[mx + k][my + k] += 1
        grid[mx + k][my + k] += 1
        grid[mx + 2 * k][my + k] -= 1
        grid[mx + k][my + 2 * k] -= 1
        grid[mx + 2 * k][my + 2 * k] += 1

    for x in range(1, 2 * l):
        for y in range(2 * l):
            grid[x][y] += grid[x - 1][y]

    for x in range(2 * l):
        for y in range(1, 2 * l):
            grid[x][y] += grid[x][y - 1]

    count = [[0] * l for _ in range(l)]

    for x in range(2 * l):
        for y in range(2 * l):
            count[x % l][y % l] += grid[x][y]
    ans = 0
    for x in range(l):
        for y in range(l):
            ans = max(ans, count[x][y])

    print(ans)


if __name__ == '__main__':
    main()