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: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


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

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

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

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


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

    print(calc_max())





if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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


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

Submission status: Accepted

Solution code:
class Accumulate2D: #2次元累積和
    def __init__(self, a):#a=graph
        self.height = len(a)
        self.width = len(a[0])
        self.acc = self.accumulate(a)

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

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


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

kk = k*2

z = [[0]*kk for i in range(kk)]#2k*2kのgraph

for i in range(n):
    x,y,c = input().split()
    x = (int(x) + (k if c=='W'else 0)) % kk#Wの場合はy+kにして、k*kマスへ変換
    y = int(y) % kk#k*kマスへ変換
    z[x][y]+=1

z = Accumulate2D(z)

ans = 0
for i in range(k):
    for j in range(k):#i,jについて全探索
        a = z.sum([0,0],[i-1,j-1])\
            + z.sum([i,j],[i+k-1,j+k-1])\
            + z.sum([0,j+k],[i-1,kk-1])\
            + z.sum([i+k,0],[kk-1,j-1])\
            + z.sum([i+k,j+k],[kk-1,kk-1])
        ans = max(ans,a,n-a)

print(ans)

Submission status: Accepted

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

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

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


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


# print('black')
# print(*b, sep='\n')
# print(*b_cs, sep='\n')

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

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

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

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

    y %= 2 * k

    b[y][x] += 1

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

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

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

Submission status: Accepted

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

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

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

    y %= 2 * k

    b[y][x] += 1

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

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

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

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

Submission status: Accepted

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

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

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


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

kk = k*2

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

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

z = Accumulate2D(z)

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

print(ans)

Submission status: Accepted

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

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

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


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

kk = k*2

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

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

z = Accumulate2D(z)

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

print(ans)

Submission status: Accepted

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

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

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

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

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

print(ans)

Submission status: Accepted

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


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

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

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    def _build(self, h, w, a):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + a[r][c]
                # 末項は必要に応じて改変すること
        return ret

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


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

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

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

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


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()

Submission status: Accepted

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

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

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

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

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

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import io

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

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

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
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)