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



Sample input:
4 3
0 1 W
1 2 W
5 3 B
5 4 B


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class cumsum2(object):
    def __init__(self,m,n):
        self.__m=m
        self.__n=n
        self.__S=[[0]*(n+1) for _ in range(m+1)]

    def add(self,i,j,w):
        self.__S[i+1][j+1]+=w

    def cumurate(self):
        S=self.__S
        for i in range(self.__m):
            for j in range(self.__n):
                S[i+1][j+1]+=S[i+1][j]+S[i][j+1]-S[i][j]

    def sum(self,i0,j0,i1,j1):
        S=self.__S
        return S[i1][j1]-S[i0][j1]-S[i1][j0]+S[i0][j0]

def resolve():
    n,k=map(int,input().split())
    white=cumsum2(2*k,2*k)
    black=cumsum2(2*k,2*k)
    for _ in range(n):
        x,y,c=input().split()
        x=int(x)%(2*k)
        y=int(y)%(2*k)
        if(c=='W'): white.add(x,y,1)
        else: black.add(x,y,1)
    white.cumurate()
    black.cumurate()

    ans=0
    from itertools import product
    for i,j in product(range(k),repeat=2):
        # 中心が白の場合
        score=0
        score+=white.sum(i+k,j+k,2*k,2*k)
        score+=white.sum(0,j+k,i,2*k)
        score+=white.sum(i,j,i+k,j+k)
        score+=white.sum(0,0,i,j)
        score+=white.sum(i+k,0,2*k,j)
        score+=black.sum(i,j+k,i+k,2*k)
        score+=black.sum(0,j,i,j+k)
        score+=black.sum(i+k,j,2*k,j+k)
        score+=black.sum(i,0,i+k,j)
        ans=max(ans,score)
        # 中心が黒の場合
        score=0
        score+=black.sum(i+k,j+k,2*k,2*k)
        score+=black.sum(0,j+k,i,2*k)
        score+=black.sum(i,j,i+k,j+k)
        score+=black.sum(0,0,i,j)
        score+=black.sum(i+k,0,2*k,j)
        score+=white.sum(i,j+k,i+k,2*k)
        score+=white.sum(0,j,i,j+k)
        score+=white.sum(i+k,j,2*k,j+k)
        score+=white.sum(i,0,i+k,j)
        ans=max(ans,score)
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    L = 2*K
    state = [[[0, 0] for _ in range(L+1)] for _ in range(L+1)]

    for _ in range(N):
        x, y, c = map(str, input().split())
        if c == 'W':
            state[int(x)%L+1][int(y)%L+1][0] += 1
        else:
            state[int(x)%L+1][int(y)%L+1][1] += 1

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

    ans = 0
    for x in range(K):
        for y in range(K):
            for k in [0, 1]:
                count = 0
                count += state[x][y][k]
                count += state[x+K][y+K][k] - state[x][y+K][k] - state[x+K][y][k] + state[x][y][k]
                count += state[L][y][k] - state[x+K][y][k]
                count += state[x][L][k] - state[x][y+K][k]
                count += state[L][L][k] - state[x+K][L][k] - state[L][y+K][k] + state[x+K][y+K][k]

                l = k ^ 1
                count += state[x+K][y][l] - state[x][y][l]
                count += state[x][y+K][l] - state[x][y][l]
                count += state[L][y+K][l] - state[x+K][y+K][l] - state[L][y][l] + state[x+K][y][l]
                count += state[x+K][L][l] - state[x+K][y+K][l] - state[x][L][l] + state[x][y+K][l]

                ans = max(ans, count)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def main():
    input = sys.stdin.readline
    def gen_pattern(x):
        if x < K-1:
            return [[0, x+1], [x+K+1, 2*K]]
        else:
            return [[x-K+1, x+1]]
    def inputs():
        return [int(x) for x in input().split()]
    def inputstr():
        return list(input().split())
    N,K = inputs()
    BB = np.zeros((2*K+1,2*K+1))
    for i in range(N):
        x,y,c = inputstr()
        if c=="W":
            y = int(y)+K
        x = int(x)%(2*K)
        y = int(y)%(2*K)
        #BB[x,y] += 1
        for shift in [0,K]:
            for b,t in gen_pattern((y+shift)%(2*K)):
                for l,r in gen_pattern((x+shift)%(2*K)):
                    BB[b,l] +=1
                    BB[b,r] -=1
                    BB[t,l] -=1
                    BB[t,r] +=1
    ans = (np.max(np.cumsum(np.cumsum(BB, axis=1), axis=0)))
    #print(BB)
    print(int(ans))
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def judge(k,x,y):
    return (x//k + y//k)%2

n,k = map(int,input().split())
x = []
y = []
c = []
for i in range(n):
    s = input().split()
    x.append(int(s[0]))
    y.append(int(s[1]))
    if s[2] == "W":
        c.append(0)
    else:
        c.append(1)
count = 0
ans = 0
for i in range(k):
    x_tmp = np.array(x) + i
    for j in range(k):
        y_tmp = np.array(y) + j
        for l in range(n):
            if judge(k,x_tmp[l],y_tmp[l]) == c[l]:
                count += 1
        tmp = max(count,n-count)
        ans = max(ans,tmp)
        count = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
kibok = input().split()
kibo,k = int(kibok[0]),int(kibok[1])
#print(kibo,k)
loop=k*2
kibolist=[[0,0,"W"] for i in range(kibo)]
#print(len(kibox))
for i in range(kibo):
  kibon=input().split()
  kibox,kiboy,kiboc = int(kibon[0]),int(kibon[1]),kibon[2]
#  print(kibox,kiboy,kiboc)
  kibox=kibox%loop
  kiboy=kiboy%loop
#  print(kibox,kiboy,kiboc)
  kibolist[i]=(kibox,kiboy,kiboc)
#for i in range(kibo):
#  print(kibolist[i])
#white
maxkanaukibo=0
kanaukibo=0
for m in range(k):#0,1,k
  for n in range(k):#0,1,k
    for l in range(kibo):
      if (int((kibolist[l][0]+m)/k)+int((kibolist[l][1]+n)/k))%2==0:
        if kibolist[l][2]=='W':
          kanaukibo=kanaukibo+1
      if (int((kibolist[l][0]+m)/k)+int((kibolist[l][1]+n)/k))%2==1:
        if kibolist[l][2]=='B':
          kanaukibo=kanaukibo+1
#    print(kanaukibo)
    maxkanaukibo=max(kanaukibo,maxkanaukibo)
    kanaukibo=0
for m in range(k):#0,1,k
  for n in range(k):#0,1,k
    for l in range(kibo):
      if (int((kibolist[l][0]+m)/k)+int((kibolist[l][1]+n)/k))%2==0:
        if kibolist[l][2]=='B':
          kanaukibo=kanaukibo+1
      if (int((kibolist[l][0]+m)/k)+int((kibolist[l][1]+n)/k))%2==1:
        if kibolist[l][2]=='W':
          kanaukibo=kanaukibo+1
#    print(kanaukibo)
    maxkanaukibo=max(kanaukibo,maxkanaukibo)
    kanaukibo=0
print(maxkanaukibo)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
XYC = [[int(x)%(2*K),int(y)%(2*K),int(c=="B")] for x,y,c in [input().split() for _ in [0]*N]]

score = [{} for _ in [0]*2]
for x,y,c in XYC:
    score[c][(y,x)] = score[c].get((y,x),0) + 1

for c in range(2):
    for x in range(K):
        for y in range(2*K):
            if (y,x) in score[c]:
                score[c][(y,x+2*K)] = score[c][(y,x)]
for c in range(2):
    for x in range(3*K):
        for y in range(K):
            if (y,x) in score[c]:
                score[c][(y+2*K,x)] = score[c][(y,x)]
    
S = [[[0]*(3*K+1) for _ in [0]*(3*K+1)] for _ in [0]*2]
for c in range(2):
    for i in range(3*K):
        for j in range(3*K):
            S[c][i+1][j+1] = S[c][i][j+1] + score[c].get((i,j),0)
    for i in range(3*K):
        for j in range(3*K):
            S[c][i+1][j+1] += S[c][i+1][j]

def get_sum(c,si,sj,i,j):
    i+=1
    j+=1
    return S[c][i][j] + S[c][si][sj] - S[c][i][sj] - S[c][si][j]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate
input = sys.stdin.readline
def main():
    N, K = map( int ,input().split())
    TK = K*2
    B = [[0]*(K*2) for _ in range(TK)]
    for _ in range(N):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "B":
            B[x%TK][y%TK] += 1
        else:
            B[x%TK][(y+K)%TK] += 1
    C = [[0]*(TK+1)] + [[0] + list( accumulate(B[i])) for i in range(TK)]
    for i in range(TK):
        for j in range(TK+1):
            C[i+1][j] += C[i][j]
    def get(i1, j1, i2, j2):
        return C[i2][j2] - C[i1][j2] - C[i2][j1] + C[i1][j1]
    ans = 0
    for i in range(K+1):
        for j in range(K+1):
            if ans < get(0,0,i,j) + get(i+K, 0, TK, j) + get(i, j, i+K, j+K) + get(0, j+K, i, TK) + get(K+i, K+j, TK, TK):
                ans = get(0,0,i,j) + get(i+K, 0, TK, j) + get(i, j, i+K, j+K) + get(0, j+K, i, TK) + get(K+i, K+j, TK, TK)
            if ans < get(i, 0, i+K, j) + get(0, j, i, j+K) + get(i+K, j, TK, j+K) + get(i, j+K, i+K, TK):
                ans = get(i, 0, i+K, j) + get(0, j, i, j+K) + get(i+K, j, TK, j+K) + get(i, j+K, i+K, TK)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
from collections import defaultdict
data=defaultdict(int)
cnt=0
tate=defaultdict(int)
yoko=defaultdict(int)
for i in range(N):
    x,y,c=input().split()
    if c=="B":
        c=-1
    else:
        c=1
    x1,x2=divmod(int(x),K)
    y1,y2=divmod(int(y),K)
    if x1%2==1:
        c*=-1
    if y1%2==1:
        c*=-1
    if c==1:
        cnt+=1
    tate[(x2,K)]+=c
    yoko[(K,y2)]+=c
    data[(x2,y2)]+=c
dp=defaultdict(int)
ans=max(cnt,N-cnt)
dp[(-1,0)]=cnt
tate[(-1,K)]=0
for i in range(K):
    dp[(i,0)]=dp[(i-1,0)]-tate[(i-1,K)]
    for j in range(K):
        yoko[(i+1,j)]=yoko[(i,j)]+data[(i,j)]
        dp[(i,j+1)]=dp[(i,j)]-yoko[(K,j)]+2*yoko[(i,j)]
print(int(max(N-min(dp.values()),max(dp.values()))))

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, K = map(int, next(sys.stdin).split())

MOD = K * 2
grid = np.zeros((MOD, MOD))


def draw(sx, sy, ex, ey):
    sx %= MOD
    sy %= MOD
    ex = (ex - 1) % MOD + 1
    ey = (ey - 1) % MOD + 1

    if sx < ex and sy < ey:
        grid[sx, sy] += 1
        if ex < MOD:
            grid[ex, sy] -= 1
        if ey < MOD:
            grid[sx, ey] -= 1
        if ex < MOD and ey < MOD:
            grid[ex, ey] += 1

    elif ex <= sx:
        if ey <= sy:
            draw(0, 0, ex, ey)
            draw(0, sy, ex, MOD)
            draw(sx, 0, MOD, ey)
            draw(sx, sy, MOD, MOD)
        else:
            draw(0, sy, ex, ey)
            draw(sx, sy, MOD, ey)
    else:
        draw(sx, 0, ex, ey)
        draw(sx, sy, ex, MOD)


for _ in range(N):
    x, y, c = next(sys.stdin).split()
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K

    # 黒マスをどこに置けばこの条件を満たすか
    # 累積和とったときに条件を満たす範囲だけ +1 されるように調整
    draw(x, y, x + K, y + K)
    draw(x + K, y + K, x + K * 2, y + K * 2)
print(int(grid.cumsum(axis=0).cumsum(axis=1).max()))

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

MOD = K * 2
grid = np.zeros((MOD, MOD))


def draw(sx, sy, ex, ey):
    sx %= MOD
    sy %= MOD
    ex = (ex - 1) % MOD + 1
    ey = (ey - 1) % MOD + 1

    if sx < ex and sy < ey:
        grid[sx, sy] += 1
        if ex < MOD:
            grid[ex, sy] -= 1
        if ey < MOD:
            grid[sx, ey] -= 1
        if ex < MOD and ey < MOD:
            grid[ex, ey] += 1

    elif ex <= sx:
        if ey <= sy:
            draw(0, 0, ex, ey)
            draw(0, sy, ex, MOD)
            draw(sx, 0, MOD, ey)
            draw(sx, sy, MOD, MOD)
        else:
            draw(0, sy, ex, ey)
            draw(sx, sy, MOD, ey)
    else:
        draw(sx, 0, ex, ey)
        draw(sx, sy, ex, MOD)


for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K

    # 黒マスをどこに置けばこの条件を満たすか
    # 累積和とったときに条件を満たす範囲だけ +1 されるように調整
    draw(x, y, x + K, y + K)
    draw(x + K, y + K, x + K * 2, y + K * 2)
print(int(grid.cumsum(axis=0).cumsum(axis=1).max()))

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(x) for x in input().split()]
xyc = [[x for x in input().split()]for _ in range(N)]
ans = 0
for i in range(2*K-1):
    for j in range(2*K-1):
        cnt = 0
        for x in xyc:
            X = (int(x[0])-i)%(2*K)
            Y = (int(x[1])-j)%(2*K)
            if(x[2]=='B' and (((0<=X and X<K) and (0<=Y and Y<K)) or ((K<=X and X<2*K) and (K<=Y and Y<2*K)))):
                cnt += 1
            elif(x[2]=='W' and (((0<=X and X<K) and (K<=Y and Y<2*K))or((K<=X and X<2*K) and (0<=Y and Y<K)))):
                cnt += 1
        ans = max(cnt,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int, input().split())
K2 = 2*K
inmap = [[0]*(K) for _ in range(K2)]
accmap = [[0]*(K+1) for _ in range(K2+1)]
inmapdeb = {}
for i in range(N):
    line = input().split()
    x, y, wb = int(line[0]), int(line[1]), line[2]
    if wb == 'W':
        x += K
    y %= K2
    if y >= K:
        y = y%K
        x = (x+K) %K2
    else:
        x = x % K2
    inmap[x][y] += 1
#     if not (x,y) in inmapdeb:
#         inmapdeb[(x,y)] = 1
#     else:
#         inmapdeb[(x,y)] += 1
# print(inmapdeb)

for i in range(K2):
    for j in range(K):
        accmap[i+1][j+1] = inmap[i][j] + accmap[i+1][j] + accmap[i][j+1] - accmap[i][j]

res = 0
for i in range(K):
    for j in range(K):
        # print(i,j)
        cand = 2*(accmap[i][j] - accmap[i+K][j]) + accmap[i+K][K] - accmap[i][K] + accmap[K2][j]
        # print("i{} j{} res:{}".format(i,j,cand))
        res = max(res, cand, N-cand)

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().strip()
n, k = [int(item) for item in input().split()]
xyc = [[item for item in input().split()] for _ in range(n)]
 
a = [[0] * 2*k for _ in range(2*k)]
for x, y, c in xyc:
    x = int(x)
    y = int(y)
    if c == "W":
        a[x%(2*k)][y%(2*k)] +=  1
    else: 
        a[(x+k)%(2*k)][(y)%(2*k)] += 1

cumsum = np.cumsum(np.cumsum(a, axis=0), axis=1)
 
ans = 0
for i in range(k):
    for j in range(k):
        ret = 0
        ik = i+k
        jk = j+k
        hm = 2*k-1
        ret += (cumsum[ik][hm] - cumsum[i][hm] + 2 * cumsum[i][jk] + cumsum[hm][j+k] - cumsum[hm][j] + 2 * cumsum[ik][j] - 2 * cumsum[ik][jk] - 2 * cumsum[i][j])
        ans = max(ans, ret, n-ret)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
kl = set(range(1, 2 * 1000 + 10))
board_tmp = [0 for i in kl]
board = []
for i in kl:
    board.append(board_tmp[:])
n, k = map(int, input().split())
xy_list = []
nl = set(range(n))
kl = set(range(1, 2 * k + 1))
total = 0
for i in nl:
    xi, yi, wb = input().split()
    xi = (int(xi) if wb == 'B' else int(xi) + k) % (2 * k)
    yi = int(yi) % (2 * k)
    board[xi+1][yi+1] += 1
    total += 1
for i in kl:
    for j in kl:
        board[i][j] += board[i][j - 1]
for j in kl:
    for i in kl:
        board[i][j] += board[i - 1][j]
ans = -1
kl = set(range(k+1))
for i in kl:
    for j in kl:
        ik = i + k
        jk = j + k
        a = board[i][j]
        b = board[ik][jk] - board[ik][j] \
            - board[i][jk] + board[i][j]
        c = board[2 * k][j] - board[ik][j]
        d = board[i][2 * k] - board[i][jk]
        e = board[2 * k][2 * k] - board[2 * k][jk] \
            - board[ik][2 * k] + board[ik][jk]
        tmp = a + b + c + d + e
        ans = max(ans, max(tmp, total - tmp))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, k = [int(item) for item in input().split()]
xyc = [[item for item in input().split()] for _ in range(n)]

a = [[0] * 2*k for _ in range(2*k)]
for x, y, c in xyc:
    x = int(x)
    y = int(y)
    if c == "W":
        a[x%(2*k)][y%(2*k)] +=  1
    else: 
        a[(x+k)%(2*k)][(y)%(2*k)] += 1

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

ans = 0
for i in range(k):
    for j in range(k):
        ret = 0
        ik = i+k
        jk = j+k
        hm = 2*k-1
        ret += (cumsum[ik][hm] - cumsum[i][hm] + 2 * cumsum[i][jk] + cumsum[hm][j+k] - cumsum[hm][j] + 2 * cumsum[ik][j] - 2 * cumsum[ik][jk] - 2 * cumsum[i][j])
        ans = max(ans, ret, n-ret)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, k = [int(item) for item in input().split()]
xyc = [[item for item in input().split()] for _ in range(n)]

a = [[0] * 2*k for _ in range(2*k)]
for x, y, c in xyc:
    x = int(x)
    y = int(y)
    if c == "W":
        a[x%(2*k)][y%(2*k)] +=  1
    else: 
        a[(x+k)%(2*k)][(y)%(2*k)] += 1

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

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

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(item) for item in input().split()]
xyc = [[item for item in input().split()] for _ in range(n)]

a = [[0] * 2*k for _ in range(2*k)]
for x, y, c in xyc:
    x = int(x)
    y = int(y)
    if c == "W":
        a[x%(2*k)][y%(2*k)] +=  1
    else: 
        a[(x+k)%(2*k)][(y)%(2*k)] += 1

cumsum = [[0] * 2*k for _ in range(2*k)]
for i in range(2*k):
    for j in range(2*k):
        if j == 0:
            cumsum[i][j] += a[i][j]
        else:
            cumsum[i][j] += a[i][j] + cumsum[i][j-1]
for i in range(2*k):
    for j in range(1,2*k):
        cumsum[j][i] += cumsum[j-1][i]

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

N, K = map(int, input().split())
K2 = K * 2
Mij = np.zeros((K2 + 1, K2 + 1), dtype=int)

def imos(i1, j1, i2, j2):
    Mij[i1][j1] += 1
    Mij[i1][j2] -= 1
    Mij[i2][j1] -= 1
    Mij[i2][j2] += 1

for _ in range(N):
    i, j, s = sys.stdin.readline().split()
    i = int(i) % K2
    j = int(j) % K2
    if s == "B":
        i = (i + K) % K2
    i1 = i % K
    j1 = j % K
    if (i < K and j < K) or (K <= i and K <= j):
        imos(0, 0, i1, j1)
        imos(0, j1 + K, i1, K2)
        imos(i1 + K, 0, K2, j1)
        imos(i1 + K, j1 + K, K2, K2)
        imos(i1, j1, i1 + K, j1 + K)
    else:
        imos(0, j1, i1, j1 + K)
        imos(i1 + K, j1, K2, j1 + K)
        imos(i1, 0, i1 + K, j1)
        imos(i1, j1 + K, i1 + K, K2)

# 累積和
Mij = np.cumsum(Mij, axis=0)
Mij = np.cumsum(Mij, axis=1)

print(Mij.max())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

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

Mij = np.zeros((K2 + 1, K2 + 1), dtype=int)

diff = [
    [-2, 0],
    [-1, -1],
    [-1, 1],
    [0, 0],
    [1, -1],
    [1, 1],
]


for _ in range(N):
    i, j, s = sys.stdin.readline().split()
    i = int(i) % K2
    j = int(j) % K2
    if s == "B":
        i = (i + K) % K2

    for y, x in diff:
        di = i + y * K
        dj = j + x * K
        i1 = max(di, 0)
        j1 = max(dj, 0)
        i2 = min(di + K, K2)
        j2 = min(dj + K, K2)
        if i1 >= K2 or j1 >= K2 or i2 <= 0 or j2 <= 0:
            continue
        Mij[i1][j1] += 1
        Mij[i2][j1] -= 1
        Mij[i1][j2] -= 1
        Mij[i2][j2] += 1

# 累積和
Mij = np.cumsum(Mij, axis=0)
Mij = np.cumsum(Mij, axis=1)

print(Mij.max())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

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

Mij = np.zeros((K2 + 1, K2 + 1), dtype=int)

diff = [
    [-2, 0],
    [-1, -1],
    [-1, 1],
    [0, 0],
    [1, -1],
    [1, 1],
]

def imos(i, j, i2, j2):
    Mij[i][j] += 1
    Mij[i2][j] -= 1
    Mij[i][j2] -= 1
    Mij[i2][j2] += 1

for _ in range(N):
    i, j, s = sys.stdin.readline().split()
    i = int(i) % K2
    j = int(j) % K2
    if s == "B":
        i = (i + K) % K2

    for y, x in diff:
        di = y * K
        dj = x * K
        i1 = max(i + di, 0)
        j1 = max(j + dj, 0)
        i2 = min(i + di + K, K2)
        j2 = min(j + dj + K, K2)
        if i1 >= K2 or j1 >= K2 or i2 <= 0 or j2 <= 0:
            continue
        imos(i1, j1, i2, j2)

# 累積和
for i in range(K2):
    Mij[i + 1, :] += Mij[i, :]
for j in range(K2):
    Mij[:, j + 1] += Mij[:, j]

print(Mij.max())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

K2 = K * 2

Gij = [None] * N
for idx, s in enumerate(Si):
    i = int(s[0]) % K2
    j = int(s[1]) % K2
    if s[2] == "B":
        i = (i + K) % K2
    Gij[idx] = [i, j]

Mij = np.zeros((K2 + 1, K2 + 1), dtype=int)

def imos(i, j, i2, j2):
    Mij[i][j] += 1
    Mij[i2][j] -= 1
    Mij[i][j2] -= 1
    Mij[i2][j2] += 1

for i, j in Gij:
    #
    for y in range(5):
        for x in range(5):
            if (y + x) % 2 > 0:
                continue
            di = (y - 2) * K
            dj = (x - 2) * K
            i1 = max(i + di, 0)
            j1 = max(j + dj, 0)
            i2 = min(i + di + K, K2)
            j2 = min(j + dj + K, K2)
            if i1 >= K2 or j1 >= K2 or i2 <= 0 or j2 <= 0:
                continue
            imos(i1, j1, i2, j2)

# 累積和
for i in range(K2):
    Mij[i + 1, :] += Mij[i, :]
for j in range(K2):
    Mij[:, j + 1] += Mij[:, j]

print(Mij.max())

Submission status: Time Limit Exceeded

Solution code:
class BIT2D:
    '''2 dimensional 1-indexed BIT
    '''

    def __init__(self, size: int):
        self.__size = size
        self.__data = [[0] * (size+1) for _ in range(size+1)]

    def update(self, x: int, y: int, v: int):
        tx, ty = x, y
        while tx <= self.__size:
            ty = y
            while ty <= self.__size:
                self.__data[tx][ty] += v
                ty += ty & -ty
            tx += tx & -tx

    def sum(self, x1: int, y1: int, x2: int, y2: int)->int:
        return self.__sum(x2, y2) - self.__sum(x2, y1) - self.__sum(x1, y2) + self.__sum(x1, y1)

    def __sum(self, x: int, y: int)->int:
        s, tx, ty = 0, x, y
        while tx > 0:
            ty = y
            while ty > 0:
                s += self.__data[tx][ty]
                ty -= ty & -ty
            tx -= tx & -tx
        return s


def points(cx: int, cy: int, K: int)->list:
    # 中心
    ps = [(max(0, cx-K), max(0, cy-K), cx, cy)]

    # 右上
    x2, y2 = min(2*K, cx+K), min(2*K, cy+K)
    x1, y1 = cx, cy
    ps.append((x1, y1, x2, y2))

    if K < cy:
        # 右下
        x2, y2 = min(2*K, cx+K), cy - K
        x1, y1 = cx, max(0, y2-K)
        ps.append((x1, y1, x2, y2))

    if cx < K:
        # 右
        x2, y2 = min(2*K, cx+2*K), cy
        x1, y1 = cx + K, max(0, cy-K)
        ps.append((x1, y1, x2, y2))

    if K < cx:
        # 左上
        x2, y2 = cx - K, min(2*K, cy+K)
        x1, y1 = max(0, x2-K), cy
        ps.append((x1, y1, x2, y2))

    if K < cx and K < cy:
        # 左下
        x2, y2 = cx - K, cy - K
        x1, y1 = max(0, x2-K), max(0, y2-K)
        ps.append((x1, y1, x2, y2))

    return ps


def checker(N: int, K: int, XYC: list)->int:
    # white = BIT2D(2*K)
    # for x, y, c in XYC:
    #     if c == 'B':
    #         x = x + K
    #     tx, ty = (x % (2*K)) + 1, (y % (2*K)) + 1
    #     white.update(tx, ty, 1)

    white = [[0] * (2*K + 1) for _ in range(2*K + 1)]
    for x, y, c in XYC:
        if c == 'B':
            x = x + K
        tx, ty = (x % (2*K)) + 1, (y % (2*K)) + 1
        white[tx][ty] += 1

    for ky in range(2*K):
        for kx in range(2*K):
            white[ky+1][kx+1] += white[ky+1][kx]

    for ky in range(2*K):
        for kx in range(2*K):
            white[ky+1][kx+1] += white[ky][kx+1]

    def get(x1: int, y1: int, x2: int, y2: int)->int:
        return white[y2][x2] - white[y2][x1] - white[y1][x2] + white[y1][x1]

    max_count = 0
    for ky in range(K, 2*K):
        for kx in range(2*K):
            # count = sum(white.sum(x1, y1, x2, y2)
            #             for x1, y1, x2, y2 in points(kx, ky, K))
            count = sum(get(x1, y1, x2, y2)
                        for x1, y1, x2, y2 in points(kx, ky, K))
            max_count = max(max_count, count)
            if max_count == N:
                break
    return max_count


if __name__ == "__main__":
    N = 0
    N, K = map(int, input().split())
    XYC = []
    for _ in range(N):
        x, y, c = input().split()
        XYC.append((int(x), int(y), c))
    ans = checker(N, K, XYC)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class BIT2D:
    '''2 dimensional 1-indexed BIT
    '''

    def __init__(self, size: int):
        self.__size = size
        self.__data = [[0] * (size+1) for _ in range(size+1)]

    def update(self, x: int, y: int, v: int):
        tx, ty = x, y
        while tx <= self.__size:
            ty = y
            while ty <= self.__size:
                self.__data[tx][ty] += v
                ty += ty & -ty
            tx += tx & -tx

    def sum(self, x1: int, y1: int, x2: int, y2: int)->int:
        return self.__sum(x2, y2) - self.__sum(x2, y1) - self.__sum(x1, y2) + self.__sum(x1, y1)

    def __sum(self, x: int, y: int)->int:
        s, tx, ty = 0, x, y
        while tx > 0:
            ty = y
            while ty > 0:
                s += self.__data[tx][ty]
                ty -= ty & -ty
            tx -= tx & -tx
        return s


def points(cx: int, cy: int, K: int)->list:
    # 中心
    ps = [(max(0, cx-K), max(0, cy-K), cx, cy)]

    # 右上
    x2, y2 = min(2*K, cx+K), min(2*K, cy+K)
    x1, y1 = cx, cy
    ps.append((x1, y1, x2, y2))

    if K < cy:
        # 右下
        x2, y2 = min(2*K, cx+K), cy - K
        x1, y1 = cx, max(0, y2-K)
        ps.append((x1, y1, x2, y2))

    if cx < K:
        # 右
        x2, y2 = min(2*K, cx+2*K), cy
        x1, y1 = cx + K, max(0, cy-K)
        ps.append((x1, y1, x2, y2))

    if K < cx:
        # 左上
        x2, y2 = cx - K, min(2*K, cy+K)
        x1, y1 = max(0, x2-K), cy
        ps.append((x1, y1, x2, y2))

    if K < cx and K < cy:
        # 左下
        x2, y2 = cx - K, cy - K
        x1, y1 = max(0, x2-K), max(0, y2-K)
        ps.append((x1, y1, x2, y2))

    return ps


def checker(N: int, K: int, XYC: list)->int:
    white, black = BIT2D(2*K), BIT2D(2*K)
    for x, y, c in XYC:
        if c == 'B':
            x = x + K
        tx, ty = (x % (2*K)) + 1, (y % (2*K)) + 1
        # black.update(tx, ty, 1)
        # if c == 'W':
        white.update(tx, ty, 1)

    # white = [[0] * (2*K + 1) for _ in range(2*K + 1)]
    # black = [[0] * (2*K + 1) for _ in range(2*K + 1)]
    # # sorted(sorted(XYC, key=lambda x: x[0]), key=lambda x: x[1]):
    # for x, y, c in XYC:
    #     tx, ty = (x % (2*K)) + 1, (y % (2*K)) + 1
    #     if c == 'W':
    #         white[tx][ty] += 1
    #     if c == 'B':
    #         black[tx][ty] += 1

    # for ky in range(2*K):
    #     for kx in range(2*K):
    #         white[ky+1][kx+1] = white[ky+1][kx] + white[ky][kx+1]
    #         black[ky+1][kx+1] = black[ky+1][kx] + black[ky][kx+1]

    # print('finished initialized')

    max_count = 0
    for ky in range(K, 2*K):
        for kx in range(2*K):
            count = 0
            # print('-'*30)
            for x1, y1, x2, y2 in points(kx, ky, K):
                count += white.sum(x1, y1, x2, y2)
                # count += white[x2][y2] - white[x2][y1] - \
                #     white[x1][y2] + white[x1][y1]
                # op += 1
                # print('white ({}, {}, {}, {})'.format(x1, y1, x2, y2))
                # print(count)

            # for x1, y1, x2, y2 in points((kx+K) % (2*K), ky, K):
            #     count += black.sum(x1, y1, x2, y2)
            #     # count += black[x2][y2] - black[x2][y1] - \
            #     #     black[x1][y2] + black[x1][y1]
            #     op += 1
            #     # print('black ({}, {}, {}, {})'.format(x1, y1, x2, y2))
            #     # print(count)

            max_count = max(max_count, count)
            if max_count == N:
                break
    return max_count


if __name__ == "__main__":
    N = 0
    N, K = map(int, input().split())
    XYC = []
    for _ in range(N):
        x, y, c = input().split()
        XYC.append((int(x), int(y), c))
    ans = checker(N, K, XYC)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()

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

ans = 0
for x in range(0,2*K+1):
    for y in range(0,2*K+1):
        W[x][y] += W[x][y-1]
for y in range(0,2*K+1):
    for x in range(0,2*K+1):
        W[x][y] += W[x-1][y]
        ans = max(ans,W[x][y])

print(ans)