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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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)
    if c == 'B':
        x += K
    x %= mod
    y %= mod
    x2 = x + K
    y2 = y + K
    acc[x][y] += 1
    acc[x2][y2] += 1
    acc[x][y2] -= 1
    acc[x2][y] -= 1
    XY.append((x, y))
    if c == 'B':
        x -= K
        x %= mod
        y += K
        y %= mod
        x2 = x + K
        y2 = y + K
    else:
        x += K; y += K
        x2 += K; y2 += K
    acc[x][y] += 1
    acc[x2][y2] += 1
    acc[x][y2] -= 1
    acc[x2][y] -= 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(MAX):
    for i in range(MAX):
        mx = max(mx, acc[i][j])
print(mx)

Submission status: Wrong Answer

Solution code:
def main():
    import sys

    input = sys.stdin.readline

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

    grid = [[0] * (K * 2) for _ in range(K * 2)]
    for _ in range(N):
        col, row, color = input().split()
        col = int(col)
        row = int(row)
        if color == 'W':
            row += K
            # Bに統一
        row %= K * 2
        col %= K * 2
        grid[row][col] += 1

    tbl = [[0] * (K * 2 + 1) for _ in range(K * 2 + 1)]
    for row in range(K * 2):
        for col in range(K * 2):
            tbl[row + 1][col + 1] = tbl[row + 1][col] + tbl[row][col + 1] - tbl[row][col] + grid[row][col]

    def count(row, col, row2, col2):
        return tbl[row2][col2] - tbl[row][col2] - tbl[row2][col] + tbl[row][col]

    ret = max(
        sum((
            count(0, 0, row, col),
            count(row, col, row + K, col + K),
            count(row + K, col + K, K * 2, K * 2),
            count(row + K, 0, K * 2, col),
            count(0, col + K, row, K * 2)
        )) for row in range(K + 1) for col in range(K + 1)
    )
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys

    input = sys.stdin.readline

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

    grid = [[0] * (K * 2) for _ in range(K * 2)]
    for _ in range(N):
        col, row, color = input().split()
        col = int(col)
        row = int(row)
        if color == 'W':
            row += K
            # Bに統一
        row %= K * 2
        col %= K * 2
        grid[row][col] += 1

    tbl = [[0] * (K * 2 + 1) for _ in range(K * 2 + 1)]
    for row in range(K * 2):
        for col in range(K * 2):
            tbl[row + 1][col + 1] = tbl[row + 1][col] + tbl[row][col + 1] - tbl[row][col] + grid[row][col]

    def count(row, col, row2, col2):
        return tbl[row2][col2] - tbl[row][col2] - tbl[row2][col] + tbl[row][col]

    ret = max(
        sum((
            count(0, 0, row, col),
            count(row, col, row + K, col + K),
            count(row + K, col + K, K * 2, K * 2),
            count(row + K, 0, K * 2, col),
            count(0, col + K, row, K * 2)
        )) for row in range(K) for col in range(K)
    )
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys

    input = sys.stdin.readline

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

    grid = [[0] * (K * 2) for _ in range(K * 2)]
    for _ in range(N):
        col, row, color = input().split()
        col = int(col)
        row = int(row)

        if color == 'W':
            row += K
            # Bに統一
        row %= K * 2
        col %= K * 2
        grid[row][col] += 1

    tbl = [[0] * (K * 2 + 1) for _ in range(K * 2 + 1)]
    for row in range(K * 2):
        for col in range(K * 2):
            tbl[row + 1][col + 1] = tbl[row + 1][col] + tbl[row][col + 1] - tbl[row][col] + grid[row][col]

    ret = max(
        tbl[row][col]
        + tbl[row + K][col + K] - tbl[row][col + K] - tbl[row + K][col] + tbl[row][col]
        + tbl[K * 2][K * 2] - tbl[row + K][K * 2] - tbl[K * 2][col + K] + tbl[row + K][col + K]
        + tbl[K * 2][col] - tbl[row + K][col]
        + tbl[row][K * 2] - tbl[row][col + K]
        for row in range(K + 1) for col in range(K + 1))
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys

    input = sys.stdin.readline

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

    grid = [[0] * (K * 2) for _ in range(K * 2)]
    for _ in range(N):
        *xy, c = input().split()
        x, y = map(int, xy)
        if c == 'W':
            y += K
            # Bに統一
        x %= K * 2
        y %= K * 2
        grid[y][x] += 1

    tbl = [[0] * (K * 2 + 1) for _ in range(K * 2 + 1)]
    for r in range(K * 2):
        for c in range(K * 2):
            tbl[r + 1][c + 1] = tbl[r + 1][c] + tbl[r][c + 1] - tbl[r][c] + grid[r][c]

    ret = max(
        tbl[r][c]
        + tbl[r + K][c + K] - tbl[r][c + K] - tbl[r + K][c] + tbl[r][c]
        + tbl[K * 2][K * 2] - tbl[r + K][K * 2] - tbl[K * 2][c + K] + tbl[r + K][c + K]
        + tbl[K * 2][c] - tbl[r + K][c]
        + tbl[r][K * 2] - tbl[r][c + K]
        for r in range(K) for c in range(K))
    print(ret)

    # ret = 0
    # for r in range(K):
    #     for c in range(K):
    #         ret = max(
    #             ret,
    #             (
    #                     tbl[r][c]
    #                     + tbl[r + K][c + K] - tbl[r][c + K] - tbl[r + K][c] + tbl[r][c]
    #                     + tbl[K * 2][K * 2] - tbl[r + K][K * 2] - tbl[K * 2][c + K] + tbl[r + K][c + K]
    #                     + tbl[K * 2][c] - tbl[r + K][c]
    #                     + tbl[r][K * 2] - tbl[r][c + K]
    #             )
    #         )
    # print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    b=[[0]*(kk+1) for _ in [0]*(kk+1)]
    w=[[0]*(kk+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":b[int(x)%kk+1][int(y)%kk+1]+=1
        else:w[int(x)%kk+1][int(y)%kk+1]+=1
    b=[list(ac(i)) for i in b]
    w=[list(ac(i)) for i in w]
    for i in range(1,kk+1):
        for j in range(kk+1):
            b[i][j]+=b[i-1][j]
    for i in range(1,kk+1):
        for j in range(kk+1):
            w[i][j]+=w[i-1][j]
    ans=0
    for i in range(kk):
        for j in range(k):
            a_t=((0,max(i-k,0),-2),(max(i-k,0),i,-1),(i,min(i+k,kk),0),(min(i+k,kk),kk,1))
            b_t=((0,max(j-k,0),-2),(max(j-k,0),j,-1),(j,min(j+k,kk),0),(min(j+k,kk),kk,1))
            a_t=[(i,j,l) for i,j,l in a_t if i!=j]
            b_t=[(i,j,l) for i,j,l in b_t if i!=j]
            black=[]
            white=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
                    else:
                        white.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            for tx1,ty1,tx2,ty2 in white:
                ret+=w[tx1][ty1]+w[tx2][ty2]-w[tx1][ty2]-w[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    b=[[0]*(k+1) for _ in [0]*(kk+1)]
    w=[[0]*(k+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":b[int(x)%kk+1][int(y)%k+1]+=1
        else:w[int(x)%kk+1][int(y)%k+1]+=1
    b=[list(ac(i)) for i in b]
    w=[list(ac(i)) for i in w]
    for i in range(1,kk+1):
        for j in range(k+1):
            b[i][j]+=b[i-1][j]
    for i in range(1,kk+1):
        for j in range(k+1):
            w[i][j]+=w[i-1][j]
    ans=0
    for i in range(kk):
        for j in range(k):
            a_t=((0,max(i-k,0),-2),(max(i-k,0),i,-1),(i,min(i+k,kk),0),(min(i+k,kk),kk,1))
            b_t=((max(j-k,0),j,-1),(j,min(j+k,k),0))
            a_t=[(i,j,l) for i,j,l in a_t if i!=j]
            b_t=[(i,j,l) for i,j,l in b_t if i!=j]
            black=[]
            white=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
                    else:
                        white.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            for tx1,ty1,tx2,ty2 in white:
                ret+=w[tx1][ty1]+w[tx2][ty2]-w[tx1][ty2]-w[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    b=[[0]*(kk+1) for _ in [0]*(kk+1)]
    w=[[0]*(kk+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":b[int(x)%kk+1][int(y)%kk+1]+=1
        else:w[int(x)%kk+1][int(y)%kk+1]+=1
    b=[list(ac(i)) for i in b]
    w=[list(ac(i)) for i in w]
    for i in range(1,kk+1):
        for j in range(kk+1):
            b[i][j]+=b[i-1][j]
    for i in range(1,kk+1):
        for j in range(kk+1):
            w[i][j]+=w[i-1][j]
    ans=0
    for i in range(k):
        for j in range(k):
            a_t=((0,max(i-k,0),-2),(max(i-k,0),i,-1),(i,min(i+k,kk),0),(min(i+k,kk),kk,1))
            b_t=((0,max(j-k,0),-2),(max(j-k,0),j,-1),(j,min(j+k,kk),0),(min(j+k,kk),kk,1))
            a_t=[(i,j,l) for i,j,l in a_t if i!=j]
            b_t=[(i,j,l) for i,j,l in b_t if i!=j]
            black=[]
            white=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
                    else:
                        white.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            for tx1,ty1,tx2,ty2 in white:
                ret+=w[tx1][ty1]+w[tx2][ty2]-w[tx1][ty2]-w[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    b=[[0]*(kk+1) for _ in [0]*(kk+1)]
    w=[[0]*(kk+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":b[int(x)%kk+1][int(y)%kk+1]+=1
        else:w[int(x)%kk+1][int(y)%kk+1]+=1
    b=[list(ac(i)) for i in b]
    w=[list(ac(i)) for i in w]
    for i in range(1,kk+1):
        for j in range(kk+1):
            b[i][j]+=b[i-1][j]
    for i in range(1,kk+1):
        for j in range(kk+1):
            w[i][j]+=w[i-1][j]
    ans=0
main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter as ct
    n,k=map(int,input().split())
    xyc=[input().split() for _ in [0]*n]
    def calc(x,y):
        x=int(x)
        y=int(y)
        return ((x-y)%(2*k)+(2*k))%(2*k)
    b=ct([calc(x,y) for x,y,c in xyc if c=="B"])
    w=ct([calc(x,y) for x,y,c in xyc if c=="W"])
    ans=0
    for i in range(2*k):
        cnt=0
        for j in range(i,i+k):
            cnt+=b[j%(2*k)]
        for j in range(i+k,i+2*k):
            cnt+=w[j%(2*k)]
        ans=max(ans,cnt)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()
 
show_flg=False
#show_flg=True

ans=0

n,k=LI()
K=2*k
r=[[0]*(K) for _ in range(K)]
R=[[0]*(K+1) for _ in range(K+1)]
#s=[[0]*k*2 for _ in range(k*2)]
for i in range(n):
    x,y,z=input().split()
    x,y=int(x),int(y)
    if y>=k:
        x,y=x-k,y-k
    if z=='B':
        r[x%(2*k)][y%(2*k)]+=1
        show(x,y)
    else:
        r[(x+k)%(2*k)][y%(2*k)]+=1
        show((x+k)%(2*k),y%(2*k))
for i in range(K):
    for j in range(K):
        R[i+1][j+1]+=R[i+1][j]+R[i][j+1]-R[i][j]+r[i][j]

for i in r:
    0#show(*i)
show()


ans=0
for i in range(k):
    for j in range(k):
        b=R[k+i][k+j]-R[i][k+j]-R[k+i][j]+R[i][j] +R[K][j]-R[k+i][j]+R[i][j]
        ans=max(ans,b)
        0#show(i,j,b)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()
 
show_flg=False
#show_flg=True

ans=0

n,k=LI()
K=2*k
r=[[0]*(K) for _ in range(K)]
R=[[0]*(K+1) for _ in range(K+1)]
#s=[[0]*k*2 for _ in range(k*2)]
for i in range(n):
    x,y,z=input().split()
    x,y=int(x),int(y)
    if y>=k:
        x,y=x-k,y-k
    if z=='B':
        r[x%(2*k)][y%(2*k)]+=1
        show(x,y)
    else:
        r[(x+k)%(2*k)][y%(2*k)]+=1
        show((x+k)%(2*k),y%(2*k))
for i in range(K):
    for j in range(K):
        R[i+1][j+1]+=R[i+1][j]+R[i][j+1]-R[i][j]+r[i][j]

for i in r:
    0#show(*i)
show()


ans=0
for i in range(k):
    for j in range(k):
        b=R[k+i][k+j]-R[i][k+j]-R[k+i][j]+2*R[i][j] +R[K][j]-R[k+i][j]+R[i][j]
        ans=max(ans,b)
        0#show(i,j,b)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()
 
show_flg=False
#show_flg=True

ans=0

n,k=LI()
K=2*k
r=[[0]*(K) for _ in range(K)]
R=[[0]*(K+1) for _ in range(K+1)]
#s=[[0]*k*2 for _ in range(k*2)]
for i in range(n):
    x,y,z=input().split()
    x,y=int(x),int(y)
    if y>=k:
        x,y=x-k,y-k
    if z=='B':
        r[x%(2*k)][y%(2*k)]+=1
        show(x,y)
    else:
        r[(x+k)%(2*k)][y%(2*k)]+=1
        show((x+k)%(2*k),y%(2*k))
for i in range(K):
    for j in range(K):
        R[i+1][j+1]+=R[i+1][j]+R[i][j+1]-R[i][j]+r[i][j]

for i in r:
    0#show(*i)
show()


ans=0
for i in range(k):
    for j in range(k):
        b=R[k+i][k+j]-R[i][k+j]-R[k+i][j]+2*R[i][j] +(R[K][j-1]-R[k+i-1][j-1] if j!=0 else 0)
        ans=max(ans,b)
        0#show(i,j,b)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()
 
show_flg=False
#show_flg=True

ans=0

n,k=LI()
K=2*k
r=[[0]*(K) for _ in range(K)]
R=[[0]*(K+1) for _ in range(K+1)]
#s=[[0]*k*2 for _ in range(k*2)]
for i in range(n):
    x,y,z=input().split()
    x,y=int(x),int(y)
    if y>=k:
        x,y=x-k,y-k
    if z=='B':
        r[x%(2*k)][y%(2*k)]+=1
        show(x,y)
    else:
        r[(x+k)%(2*k)][y%(2*k)]+=1
        show((x+k)%(2*k),y%(2*k))
for i in range(K):
    for j in range(K):
        R[i+1][j+1]+=R[i+1][j]+R[i][j+1]-R[i][j]+r[i][j]

for i in r:
    0#show(*i)
show()


ans=0
for i in range(k):
    for j in range(k):
        b=R[k+i][k+j]-R[i][k+j]-R[k+i][j]+2*R[i][j] +R[K][j]-R[k+i][j]
        ans=max(ans,b)
        0#show(i,j,b)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()
 
show_flg=False
#show_flg=True

ans=0

n,k=LI()
K=2*k
r=[[0]*(K) for _ in range(K)]
R=[[0]*(K+1) for _ in range(K+1)]
#s=[[0]*k*2 for _ in range(k*2)]
for i in range(n):
    x,y,z=input().split()
    x,y=int(x),int(y)
    if y>=k:
        x,y=x-k,y-k
    if z=='B':
        r[x%(2*k)][y%(2*k)]+=1
        show(x,y)
    else:
        r[(x+k)%(2*k)][y%(2*k)]+=1
        show((x+k)%(2*k),y%(2*k))
for i in range(K):
    for j in range(K):
        R[i+1][j+1]+=R[i+1][j]+R[i][j+1]-R[i][j]+r[i][j]

for i in r:
    show(*i)
show()


ans=0
for i in range(k):
    for j in range(k):
        b=R[k+i][k+j]-R[i][k+j]-R[k+i][j]+R[i][j]
        ans=max(ans,b)
        show(i,j,b)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()
 
show_flg=False
#show_flg=True

ans=0

n,k=LI()
K=2*k
r=[[0]*(K) for _ in range(K)]
R=[[0]*(K+1) for _ in range(K+1)]
#s=[[0]*k*2 for _ in range(k*2)]
for i in range(n):
    x,y,z=input().split()
    x,y=int(x),int(y)
    if z=='B':
        r[x%(2*k)][y%(2*k)]+=1
        show(x,y)
    else:
        r[(x+k)%(2*k)][y%(2*k)]+=1
        show((x+k)%(2*k),y)
for i in range(K):
    for j in range(K):
        R[i+1][j+1]+=R[i+1][j]+R[i][j+1]-R[i][j]+r[i][j]

for i in r:
    show(*i)
show()


ans=0
for i in range(k):
    for j in range(k):
        b=R[k+i][k+j]-R[i][k+j]-R[k+i][j]+R[i][j]
        ans=max(ans,b)
        show(i,j,b)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()
 
show_flg=False
#show_flg=True

ans=0

n,k=LI()
K=2*k
r=[[0]*(K) for _ in range(K)]
R=[[0]*(K+1) for _ in range(K+1)]
#s=[[0]*k*2 for _ in range(k*2)]
for i in range(n):
    x,y,z=input().split()
    x,y=int(x)%k,int(y)%k
    if z=='B':
        r[x][y]+=1
        show(x,y)
    else:
        r[(x+k)%(2*k)][y]+=1
        show((x+k)%(2*k),y)
for i in range(K):
    for j in range(K):
        R[i+1][j+1]+=R[i+1][j]+R[i][j+1]-R[i][j]+r[i][j]

for i in r:
    show(*i)
show()


ans=0
for i in range(k):
    for j in range(k):
        b=R[k+i][k+j]-R[i][k+j]-R[k+i][j]+R[i][j]
        ans=max(ans,b)
        show(i,j,b)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
acc = [[0] * 3 * k for _ in range(2 * k)]
for _ in range(n):
    x, y, c = LS()
    x = int(x); y = int(y)
    if c == 'W':
        x += k
    x %= 2 * k
    y %= 2 * k
    acc[y][x] += 1
    for i, j in ((1, 1), (1, -1), (-1, 1), (-1, -1), (2, 0)):
        if 0 <= y + k * i < 2 * k and 0 <= x + k * j < 3 * k:
            acc[y + k * i][x + k * j] += 1



acc = [[0] * (3 * k + 1)] + [list(accumulate([0] + acc[y])) for y in range(2 * k)]
for y in range(2 * k):
    for x in range(3 * k + 1):
        acc[y + 1][x] += acc[y][x]


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


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
l = 2 * k
acc = [[0] * 3 * k for _ in range(l)]
for _ in range(n):
    x, y, c = LS()
    x = int(x); y = int(y)
    if c == 'W':
        x += k
    x %= 2 * k
    y %= 2 * k
    acc[y][x] += 1
    for i, j in ((1, 1), (1, -1), (-1, 1), (-1, -1), (2, 0)):
        if 0 <= y + k * i < l and 0 <= x + k * j < 3 * k:
            acc[y + k * i][x + k * j] += 1



acc = [[0] * (3 * k + 1)] + [list(accumulate([0] + acc[y])) for y in range(l)]
for y in range(l):
    for x in range(l + 1):
        acc[y + 1][x] += acc[y][x]


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


print(ans)