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())
mod = 2*k
imos = [[0]*(mod+1) for i in range(mod+1)]
board = [[0]*mod for _ in range(mod)]
delta = [(0,0),(k,k),(k,-k),(-k,k),(-k,-k)]
m_cnt = 0
for i in range(n):
    x,y,c = input().split()
    x,y = map(int,[x,y])
    d = 1
    if c == 'W':
        x -= k
    x,y = x%mod,y%mod
    if (x//k) ^ (y//k):
        x = (x+k)%mod
        d *= -1
        m_cnt += 1
    if x < k or y < k:
        x += k
        y += k
    imos[x+1][y+1] += d
    imos[x-k+1][y-k+1] += d
    imos[x+1][y-k+1] -= d
    imos[x-k+1][y+1] -= d



for i in range(1,mod):
    for j in range(mod):
        imos[i][j] += imos[i-1][j]
ans = 0
for i in range(mod):
    for j in range(1,mod):
        imos[i][j] += imos[i][j-1]
        for di,dj in delta:
            if 0 <= i+di < mod and 0 <= j+dj < mod:
                board[i+di][j+dj] += imos[i][j]
for i in range(mod):
    for j in range(mod):
        ans = max(ans,board[i][j])
print(ans + m_cnt)

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

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

for i in range(1, 2*K+1):
    black[i] = list(accumulate(black[i]))
    white[i] = list(accumulate(white[i]))
    for j in range(2*K+1):
        black[i][j] += black[i-1][j]
        white[i][j] += white[i-1][j]

ans = 0
for i in range(K):
    for j in range(K):
        cnt = 0
        for k in [-1, 0, 1]:
            for l in [-1, 0, 1]:
                r = i + K*k
                c = j + K*l
                color = black if (k + l) % 2 == 0 else white
                s1 = color[min(r+K, 2*K)][min(c+K, 2*K)]
                s2 = color[min(r+K, 2*K)][max(c, 0)]
                s3 = color[max(r, 0)][min(c+K, 2*K)]
                s4 = color[max(r, 0)][max(c, 0)]
                cnt += s1 - s2 - s3 + s4
        ans = max(ans, cnt, N - cnt)
print(ans)

Solution (Python):
def cumsum(T, K):
    R = [[0] * K for _ in range(K)]
    for i in range(K):
        t = 0
        for j in range(K):
            t += T[i][j]
            R[i][j] = t
    for i in range(K):
        t = 0
        for j in range(K):
            t += R[j][i]
            R[j][i] = t
    return R

def fm(B, W, K):
    m = 0
    for i in range(K):
        for j in range(K):
            t = B[i][j]
            if i == K - 1 or j == K - 1:
                t += W[K - 1][K - 1] - W[i][j]
            else:
                t += B[K - 1][K - 1] - B[K - 1][j] - B[i][K - 1] + B[i][j]
                t += W[K - 1][j] + W[i][K - 1] - 2 * W[i][j]
            m = max(m, t)
    return m

def main():
    N, K = map(int, input().split())
    K2 = 2 * K
    B = [[0] * K for _ in range(K)]
    W = [[0] * K for _ in range(K)]
    for _ in range(N):
        x1, y1, c = input().split()
        x, y = int(x1) % K2, int(y1) % K2
        if c == 'B':
            x = (x - K) % K2
        if x >= K and y >= K:
            x, y = x - K, y - K
        if x < K and y < K:
            B[x][y] += 1
        else:
            x, y = (x - K, y) if y < K else (x, y - K)
            W[x][y] += 1
    B = cumsum(B, K)
    W = cumsum(W, K)
    return max(fm(B, W, K), fm(W, B, K))

print(main())

Solution (Python):
N,K=map(int,input().split())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
for i in range(N):
    a,b,c=map(str,input().split())
    a,b=int(a),int(b)
    if c=="W":
        b+=K
    a%=(2*K)
    b%=(2*K)
    x[i]=a
    y[i]=b
board=[[0 for j in range(2*K+1)] for i in range(2*K+1)]
for i in range(N):
    if y[i]>=K:
        y[i]-=K
        x[i]=(x[i]+K)%(2*K)
    if x[i]>=K and y[i]<K:
        board[0][y[i]+1]+=1
        board[0][y[i]+K+1]-=1
        board[x[i]-K+1][y[i]+1]-=2
        board[x[i]-K+1][y[i]+K+1]+=2
        board[x[i]-K+1][0]+=1
        board[x[i]+1][0]-=1
        board[x[i]+1][y[i]+1]+=2
        board[x[i]+1][y[i]+K+1]-=2
    if x[i]<K and y[i]<K:
        board[0][y[i]+1]-=1
        board[0][y[i]+K+1]+=1
        board[x[i]+K+1][y[i]+1]-=2
        board[x[i]+K+1][y[i]+K+1]+=2
        board[x[i]+K+1][0]+=1
        board[x[i]+1][0]-=1
        board[x[i]+1][y[i]+1]+=2
        board[x[i]+1][y[i]+K+1]-=2
        board[0][0]+=1
coard=[[0 for j in range(2*K)] for i in range(2*K)]
doard=[[0 for j in range(2*K)] for i in range(2*K)]
for i in range(2*K):
    for j in range(2*K):
        if i==0:
            coard[i][j]=board[i][j]
        else:
            coard[i][j]=board[i][j]+coard[i-1][j]
for i in range(2*K):
    for j in range(2*K):
        if j==0:
            doard[i][j]=coard[i][j]
        else:
            doard[i][j]=coard[i][j]+doard[i][j-1]
ans=0
for i in range(2*K):
    for j in range(2*K):
        ans=max(ans,doard[i][j])
print(ans)

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] + csw[i][j]
    v = csb[i][-1] - csb[i][j] + csb[-1][j] - csb[i][j]
    res = max(res, u + v)
    u = csb[-1][-1] - csb[i][-1] - csb[-1][j] + csb[i][j] + csb[i][j]
    v = csw[i][-1] - csw[i][j] + csw[-1][j] - csw[i][j]
    res = max(res, u + v)
    
print(res)

Solution (Python):
import sys


n, k = map(int, sys.stdin.readline().strip().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = sys.stdin.readline().strip().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]



lx = len(x)
graph[0][0] += lx
for i in range(lx):
    graph[x[i]][0] -= 1
    graph[0][y[i]] -= 1
    graph[x[i]][y[i]] += 2

lmx = len(mx)
graph[0][0] -= lmx
for i in range(lmx):
    graph[mx[i]][0] += 1
    graph[0][my[i]] += 1
    graph[mx[i]][my[i]] -= 2

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

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


big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Solution (Python):
import sys


n, k = map(int, sys.stdin.readline().strip().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = sys.stdin.readline().strip().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]



lx = len(x)
graph[0][0] += lx
for i in range(lx):
    graph[x[i]][0] -= 1
    graph[0][y[i]] -= 1
    graph[x[i]][y[i]] += 2

lmx = len(mx)
graph[0][0] -= lmx
for i in range(lmx):
    graph[mx[i]][0] += 1
    graph[0][my[i]] += 1
    graph[mx[i]][my[i]] -= 2

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

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


big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Solution (Python):
import sys


n, k = map(int, sys.stdin.readline().strip().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = sys.stdin.readline().strip().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]



lx = len(x)
graph[0][0] += lx
for i in range(lx):
    graph[x[i]][0] -= 1
    graph[0][y[i]] -= 1
    graph[x[i]][y[i]] += 2

lmx = len(mx)
graph[0][0] -= lmx
for i in range(lmx):
    graph[mx[i]][0] += 1
    graph[0][my[i]] += 1
    graph[mx[i]][my[i]] -= 2

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

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


big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Solution (Python):

from itertools import chain
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, K: int, x: "List[int]", y: "List[int]", c: "List[str]"):
    imos = [[0] * (2 * K) for _ in range(2 * K)]

    def sq(x1: int, y1: int, x2: int, y2: int):
        x1 %= 2 * K
        x2 %= 2 * K
        y1 %= 2 * K
        y2 %= 2 * K
        if x1 > x2:
            imos[y1][0] += 1
            imos[y2][0] -= 1
            if y1 > y2:
                imos[0][0] += 1
        if y1 > y2:
            imos[0][x1] += 1
            imos[0][x2] -= 1
        imos[y1][x1] += 1
        imos[y1][x2] -= 1
        imos[y2][x1] -= 1
        imos[y2][x2] += 1

    for xi, yi, ci in zip(x, y, c):
        if ci == "B":
            bx = xi + 1
            by = yi + 1
        else:
            bx = xi - K + 1
            by = yi + 1
        sq(bx, by, bx + K, by + K)
        sq(bx + K, by + K, bx, by)

    

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

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

    
    print(max(chain(*imos)))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    x = [int()] * (N)  
    y = [int()] * (N)  
    c = [str()] * (N)  
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        c[i] = next(tokens)
    solve(N, K, x, y, c)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.readline
import numpy as np




def sum2d(i1,j1,i2,j2):
    A[i1][j1] += 1
    A[i1][j2] -= 1
    A[i2][j1] -= 1
    A[i2][j2] += 1





N,K = map(int,input().split())
XYC = [list(input().split()) for _ in range(N)]

A = [[0 for _ in range(K*2+1)] for _ in range(K*2+1)]

for x,y,c in XYC:
    
    i = (int(x) if c=="W" else int(x)+K) % (K*2)
    j = int(y) % (K*2)
    i0 = i%K
    j0 = j%K

    
    
    
    
    if (i<K and j<K) or (i>=K and j>=K):
        sum2d(0,0,i0,j0) 
        sum2d(i0+K,0,K*2,j0) 
        sum2d(i0,j0,i0+K,j0+K) 
        sum2d(0,j0+K,i0,K*2) 
        sum2d(i0+K,j0+K,K*2,K*2) 

    
    
    
    
    else:
        sum2d(i0,0,i0+K,j0) 
        sum2d(0,j0,i0,j0+K) 
        sum2d(i0+K,j0,K*2,j0+K) 
        sum2d(i0,j0+K,i0+K,K*2) 
 

AA = np.array(A)
for i in range(K*2):
    AA[i+1, :] += AA[i, :]
for j in range(K*2):
    AA[:, j+1] += AA[:, j]
 
print(AA.max())

Solution (Python):
import numpy as np
n,k=map(int,input().split())
m=np.zeros((3*k,3*k),dtype=int)
l=2*k
o=0
for _ in range(n):
  x,y,c=input().split()
  x,y=int(x)%l,int(y)%l
  t=c=='W'
  m[x,y]+=1-2*t
  o+=t
for _ in range(2):
  m[l:]=m[:k]
  m=np.cumsum(m,axis=0)
  m[:l]=m[k:]-m[:l]
  m=m.T
m=m[:l,:l]
print(o+(m+np.roll(np.roll(m,k,axis=0),k,axis=1)).max())

Solution (Python):


N, K = map(int, input().split())
g = [[0]*K for _ in range(K)] 

for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    tmp = (x//K + y//K) % 2
    x %= K
    y %= K
    if (tmp == 0 and c == "B") or (tmp == 1 and c == "W"):
        g[x][y] += 1
    else:
        g[x][y] -= 1 

for i in range(K):
    for j in range(1,K):
        g[i][j] += g[i][j-1]

for i in range(1,K):
    for j in range(K):
        g[i][j] += g[i-1][j]



ans = 0
for i in range(K):
    for j in range(K):
        n_satisfied = g[-1][-1] -2*(g[-1][j] + g[i][-1]) + 4*g[i][j]
        ans = max(ans, (N + n_satisfied)//2, (N - n_satisfied)//2) 

print(ans)

Solution (Python):


N, K = map(int, input().split())
g = [[0]*K for _ in range(K)] 

for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    tmp = (x//K + y//K) % 2
    x %= K
    y %= K
    if (tmp == 0 and c == "B") or (tmp == 1 and c == "W"):
        g[x][y] += 1
    else:
        g[x][y] -= 1 

for i in range(K):
    for j in range(1,K):
        g[i][j] += g[i][j-1]

for i in range(1,K):
    for j in range(K):
        g[i][j] += g[i-1][j]



ans = 0
for i in range(K):
    for j in range(K):
        n_satisfied = g[-1][-1] -2*(g[-1][j] + g[i][-1]) + 4*g[i][j]
        ans = max(ans, (N + n_satisfied)//2, (N - n_satisfied)//2) 

print(ans)

Solution (Python):
import sys


N, K = map(int, input().split())
cnt_B = 0
black = [[0] * (2 * K) for _ in range(2 * K)]
for s in sys.stdin.readlines():
    x, y, c = s.split()
    x = int(x); y = int(y)
    y = y if c == 'B' else y + K
    black[x % (2 * K)][y % (2 * K)] += 1
    cnt_B += 1

S_black = [[0] * (2 * K + 1) for _ in range(2 * K)]
for i in range(2 * K):
    for j in range(2 * K):
        S_black[i][j + 1] = S_black[i][j] + black[i][j]

ans = 0
for j in range(K):
    var_B = 0
    for i in range(K):
        var_B += S_black[i][j + K] - S_black[i][j]
        var_B += S_black[i + K][2 * K] - (S_black[i + K][j + K] - S_black[i + K][j])
    ans = max(ans, max(var_B, cnt_B - var_B))

    for i in range(K):
        var_B += (S_black[i + K][j + K] - S_black[i + K][j]) - (S_black[i][j + K] - S_black[i][j])
        var_B -= S_black[i + K][2 * K] - (S_black[i + K][j + K] - S_black[i + K][j])
        var_B += S_black[i][2 * K] - (S_black[i][j + K] - S_black[i][j])
        ans = max(ans, max(var_B, cnt_B - var_B))

print(ans)

Solution (Python):
import sys


N, K = map(int, input().split())
cnt_B = 0
cnt_W = 0
black = [[0] * (2 * K) for _ in range(2 * K)]
white = [[0] * (2 * K) for _ in range(2 * K)]
for s in sys.stdin.readlines():
    x, y, c = s.split()
    x = int(x); y = int(y)
    if c == 'B':
        black[x % (2 * K)][y % (2 * K)] += 1
        cnt_B += 1
    else:
        white[x % (2 * K)][y % (2 * K)] += 1
        cnt_W += 1

S_black = [[0] * (2 * K + 1) for _ in range(2 * K)]
S_white = [[0] * (2 * K + 1) for _ in range(2 * K)]
for i in range(2 * K):
    for j in range(2 * K):
        S_black[i][j + 1] = S_black[i][j] + black[i][j]
        S_white[i][j + 1] = S_white[i][j] + white[i][j]

ans = 0
for j in range(K):
    var_B, var_W = 0, 0
    for i in range(K):
        var_B += S_black[i][j + K] - S_black[i][j]
        var_W += S_white[i][j + K] - S_white[i][j]
        
        var_B += S_black[i + K][2 * K] - (S_black[i + K][j + K] - S_black[i + K][j])
        var_W += S_white[i + K][2 * K] - (S_white[i + K][j + K] - S_white[i + K][j])

    ans = max(ans, max(var_B + (cnt_W - var_W), var_W + (cnt_B - var_B)))
    for i in range(K):
        var_B += (S_black[i + K][j + K] - S_black[i + K][j]) - (S_black[i][j + K] - S_black[i][j])
        var_W += (S_white[i + K][j + K] - S_white[i + K][j]) - (S_white[i][j + K] - S_white[i][j])

        var_B -= S_black[i + K][2 * K] - (S_black[i + K][j + K] - S_black[i + K][j])
        var_B += S_black[i][2 * K] - (S_black[i][j + K] - S_black[i][j])
        var_W -= S_white[i + K][2 * K] - (S_white[i + K][j + K] - S_white[i + K][j])
        var_W += S_white[i][2 * K] - (S_white[i][j + K] - S_white[i][j])

        ans = max(ans, max(var_B + (cnt_W - var_W), var_W + (cnt_B - var_B)))

print(ans)

Solution (Python):
def main():
    n,k=map(int,input().split())
    grid=[[0]*k for _ in range(k)]
    for i in range(n):
        x,y,c=map(lambda x:x,input().split())
        x,y=int(x),int(y)
        p=(x//k+y//k)%2
        if (p==0 and c=="B")|(p==1 and c=="W"): grid[x%k][y%k]+=1
        else: grid[x%k][y%k]-=1

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

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


    ans=0
    for i in range(k):
        for j in range(k):
            b=grid[i][j]*4+grid[k-1][k-1]-(grid[i][k-1]+grid[k-1][j])*2
            ans=max(ans,n+b,n-b)
    print(ans//2)

if __name__ == "__main__":
    main()

Solution (Python):
n,k=map(int,input().split())
grid=[[0]*k for _ in range(k)]
for i in range(n):
    x,y,c=map(lambda x:x,input().split())
    x,y=int(x),int(y)
    p=(x//k+y//k)%2
    if (p==0 and c=="B")|(p==1 and c=="W"): grid[x%k][y%k]+=1
    else: grid[x%k][y%k]-=1

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

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


ans=0
for i in range(k):
    for j in range(k):
        b=grid[i][j]*4+grid[k-1][k-1]-(grid[i][k-1]+grid[k-1][j])*2
        ans=max(ans,n+b,n-b)
print(ans//2)

Solution (Python):
n,k=map(int,input().split())
grid=[[0]*k for _ in range(k)]
for i in range(n):
    x,y,c=map(lambda x:x,input().split())
    x,y=int(x),int(y)
    p=(x//k+y//k)%2
    if (p==0 and c=="B")|(p==1 and c=="W"): grid[x%k][y%k]+=1
    else: grid[x%k][y%k]-=1

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

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


ans=0
for i in range(k):
    for j in range(k):
        b=grid[i][j]*4+grid[k-1][k-1]-(grid[i][k-1]+grid[k-1][j])*2
        ans=max(ans,(n+b)//2,(n-b)//2)
print(ans)

Solution (Python):
n,k = map(int,input().split())
xyc = [list(input().split()) for i in range(n)]
for i in range(n):
  x,y,c = xyc[i]
  x = int(x)
  y = int(y)
  xq = x//k
  yq = y//k
  if (xq+yq)%2:
    if c == "B":
      c = "W"
    else:
      c = "B"
  x %= k
  y %= k
  xyc[i] = x,y,c
gridw = [[0 for i in range(k+1)] for j in range(k+1)]
gridb = [[0 for i in range(k+1)] for j in range(k+1)]
for x,y,c in xyc:
  x += 1
  y += 1
  if c == "B":
    gridb[x][y] += 1
  else:
    gridw[x][y] += 1
for grid in gridb,gridw:
  for i in range(1,k+1):
    for j in range(k+1):
      grid[i][j] += grid[i-1][j]
for grid in gridb,gridw:
  for i in range(k+1):
    for j in range(1,k+1):
      grid[i][j] += grid[i][j-1]
nw = gridw[-1][-1]
nb = gridb[-1][-1]
ans = 0
def sm(grid,i,j):
  return grid[i][j]+grid[-1][-1]-grid[-1][j]-grid[i][-1]+grid[i][j]
for i in range(k+1):
  for j in range(k+1):
    x = sm(gridb,i,j)+nw-sm(gridw,i,j)
    ans = max(ans,x,n-x)
print(ans)

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
mod = K * 2
XY = []
MAX = K * 4
imos = list2d(MAX+1, MAX+1, 0)
for i in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    x %= mod
    y %= mod
    if c == 'B':
        x += K
    for a1 in range(2):
        for a2 in range(2):
            for b in [0, K]:
                if c == 'B':
                    b = -b
                x1 = x + a1 * mod + b
                y1 = y + a2 * mod + b
                x2 = x1 + K
                y2 = y1 + K
                x1 = max(min(x1, MAX), 0)
                y1 = max(min(y1, MAX), 0)
                x2 = max(min(x2, MAX), 0)
                y2 = max(min(y2, MAX), 0)
                imos[x1][y1] += 1
                imos[x2][y2] += 1
                imos[x1][y2] -= 1
                imos[x2][y1] -= 1

for i in range(MAX+1):
    imos[i] = list(accumulate(imos[i]))
for j in range(MAX+1):
    for i in range(MAX):
        imos[i+1][j] += imos[i][j]
ans = 0
for i in range(K*2, K*4+1):
    ans = max(ans, max(imos[i][K*2:K*4+1]))
print(ans)

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
mod = K * 2
XY = []
MAX = K * 4
acc = list2d(MAX+1, MAX+1, 0)
for i in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    x %= mod
    y %= mod
    if c == 'B':
        x += K
    for a1 in range(3):
        for a2 in range(3):
            for b in [0, K]:
                if c == 'B':
                    b = -b
                x1 = x + a1 * mod + b
                y1 = y + a2 * mod + b
                x2 = x1 + K
                y2 = y1 + K
                x1 = max(min(x1, MAX), 0)
                y1 = max(min(y1, MAX), 0)
                x2 = max(min(x2, MAX), 0)
                y2 = max(min(y2, MAX), 0)
                acc[x1][y1] += 1
                acc[x2][y2] += 1
                acc[x1][y2] -= 1
                acc[x2][y1] -= 1

for i in range(MAX+1):
    acc[i] = list(accumulate(acc[i]))
for j in range(MAX+1):
    for i in range(MAX):
        acc[i+1][j] += acc[i][j]
ans = 0
for i in range(K*2, K*4+1):
    ans = max(ans, max(acc[i][K*2:K*4+1]))
print(ans)

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
mod = K * 2
XY = []
MAX = K*4 + 7
acc = list2d(MAX, MAX, 0)
for i in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    x %= mod
    y %= mod
    if c == 'B':
        x += K
    for a1 in range(3):
        for a2 in range(3):
            for b in [0, K]:
                if c == 'B':
                    b = -b
                x1 = x + a1 * mod + b
                y1 = y + a2 * mod + b
                x2 = x1 + K
                y2 = y1 + K
                x1 = max(min(x1, MAX-1), 0)
                y1 = max(min(y1, MAX-1), 0)
                x2 = max(min(x2, MAX-1), 0)
                y2 = max(min(y2, MAX-1), 0)
                acc[x1][y1] += 1
                acc[x2][y2] += 1
                acc[x1][y2] -= 1
                acc[x2][y1] -= 1

for i in range(MAX):
    acc[i] = list(accumulate(acc[i]))
for j in range(MAX):
    for i in range(MAX-1):
        acc[i+1][j] += acc[i][j]
mx = 0
for j in range(K*2, K*4):
    for i in range(K*2, K*4):
        mx = max(mx, acc[i][j])
print(mx)

Solution (Python):

"""
@auther: SPD_9X2
https://atcoder.jp/contests/abc086/tasks/arc089_b

考察：

まず、x,y座標を2Kで割っておいてよい。

黒白
白黒　で考え、左下(0,0)で開始。

縦軸を固定し、左に動かしていくことを考える。
すると、現在　x%K == 0　となる部分にいる希望のみ、達成・非達成が反転する

初期の達成数を記録しておき、各列で達成・非達成がいくつあるのかをリストに記録
ずらすと、現在の達成数 += 新たに達成する要求 - 非達成になる要求
となる。2*K回操作して元に戻す

縦軸の移動は各行について、どの列に要求があるのかをおいておき、その部分の達成・非達成数を反転する
各要求で高々2回しかチェックしないため、O(N + K^2)で処理できる
"""




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

cansub = [ [] for i in range(2*K) ]
notsub = [ [] for i in range(2*K) ]

notlis = [0] * (2*K)
canlis = [0] * (2*K)

for i in range(N):

    x,y,c = input().split()
    x = int(x)
    y = int(y)
    x %= (2*K)
    y %= (2*K)

    if (x >= K and y >= K) or (x < K and y < K):
        nc = "W"
    else:
        nc = "B"

    if nc == c:
        cansub[x].append(y)
        canlis[y] += 1
    else:
        notsub[x].append(y)
        notlis[y] += 1



ans = 0

for i in range(2*K):

    ncan = sum(canlis)

    for j in range(2*K):

        j %= (2*K)

        ans = max(ans,ncan)
        ncan += notlis[j]
        ncan -= canlis[j]

        t = notlis[j]
        notlis[j] = canlis[j]
        canlis[j] = t

        j += K
        j %= (2*K)

        ncan += notlis[j]
        ncan -= canlis[j]

        t = notlis[j]
        notlis[j] = canlis[j]
        canlis[j] = t


    for k in cansub[i]:
        notlis[k] += 1
        canlis[k] -= 1
    for k in notsub[i]:
        notlis[k] -= 1
        canlis[k] += 1

    t = cansub[i]
    cansub[i] = notsub[i]
    notsub[i] = t

    i += K
    i %= (2*K)

    for k in cansub[i]:
        notlis[k] += 1
        canlis[k] -= 1
    for k in notsub[i]:
        notlis[k] -= 1
        canlis[k] += 1

    t = cansub[i]
    cansub[i] = notsub[i]
    notsub[i] = t

print (ans)

Solution (Python):
import sys
import numpy as np

read = sys.stdin

N, K = map(int, read.readline().split())
k = 2 * K
xyc = np.array(read.read().split(), np.str)
x = xyc[::3].astype(int)
y = xyc[1::3].astype(int)
c = xyc[2::3]

x[c == 'B'] -= K
x %= k
y %= k

grid = np.zeros((3 * K, 3 * K), np.int64)
np.add.at(grid, (x, y), 1)
np.add.at(grid, (x + K, y + K), 1)
np.subtract.at(grid, (x + K, y), 1)
np.subtract.at(grid, (x, y + K), 1)
np.cumsum(grid, axis=0, out=grid)
np.cumsum(grid, axis=1, out=grid)

p1 = grid[:K, :K] + grid[k:, k:] + grid[K:k, K:k] + grid[k:, :K] + grid[:K, k:]
p2 = grid[K:k, :K] + grid[K:k, k:] + grid[:K, K:k] + grid[k:, K:k]
print(max(p1.max(), p2.max()))

Solution (Python):
import sys
import numpy as np
from collections import Counter

read = sys.stdin

N, K = map(int, read.readline().split())
k = 2 * K
xyc = np.array(read.read().split(), np.str).reshape(-1, 3)
x = xyc[:, 0].astype(int)
y = xyc[:, 1].astype(int)
c = xyc[:, 2]

x[c == 'B'] -= K
x %= k
y %= k

grid = np.zeros((3 * K, 3 * K), np.int64)
np.add.at(grid, (x, y), 1)
np.add.at(grid, (x + K, y + K), 1)
np.subtract.at(grid, (x + K, y), 1)
np.subtract.at(grid, (x, y + K), 1)
np.cumsum(grid, axis=0, out=grid)
np.cumsum(grid, axis=1, out=grid)

p1 = grid[:K, :K] + grid[k:, k:] + grid[K:k, K:k] + grid[k:, :K] + grid[:K, k:]
p2 = grid[K:k, :K] + grid[K:k, k:] + grid[:K, K:k] + grid[k:, K:k]
print(max(p1.max(), p2.max()))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def query_cumsum2d(s, x1, y1, x2, y2):
    
    if x2 < x1:
        x1, x2 = x2, x1
    if y2 < y1:
        y1, y2 = y2, y1
    return s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]

def main():
    N, K = LI()
    G = [[0 for _ in range(2*K)] for __ in range(2*K)]
    cumsum2d = [[0 for _ in range(2*K + 1)] for __ in range(2*K + 1)]
    xyc = []
    for _ in range(N):
        x, y, c =  LS()
        x = int(x)
        y = int(y)
        if c == 'W':
            x += K
        x = x % (2 * K)
        y = y % (2 * K)
        G[x][y] += 1
        xyc.append((x, y, c))
    for x in range(2*K):
        for y in range(2*K):
            cumsum2d[x+1][y+1] = (
                cumsum2d[x+1][y]
                + cumsum2d[x][y+1]
                - cumsum2d[x][y]
                + G[x][y]
            )
    ans = 0
    
    
    
    
    
    
    
    
    for x in range(K):
        for y in range(K):
            
            cnt = (
                  query_cumsum2d(cumsum2d, 0, 0, x, y)
                + query_cumsum2d(cumsum2d, x, y, x+K, y+K)
                + query_cumsum2d(cumsum2d, x+K, 0, 2 * K, y)
                + query_cumsum2d(cumsum2d, 0, y+K, x, 2 * K)
                + query_cumsum2d(cumsum2d, 2*K, 2*K, x+K, y+K)
            )

            ans = max(ans, cnt, N - cnt)
    print(ans)



main()