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())
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=int(a)
    b=int(b)
    if c=="W":
        b+=K
    x[i]=a%(2*K)
    y[i]=b%(2*K)
board=[[0 for i in range(2*K+1)] for i in range(2*K+1)]
for i in range(N):
    if x[i]>=K and y[i]>=K:
        x[i]-=K
        y[i]-=K
    if x[i]<K and y[i]>=K:
        x[i]+=K
        y[i]-=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[x[i]+1][y[i]+1]+=2
        board[x[i]+K+1][y[i]+K+1]+=2
        board[x[i]+1][y[i]+K+1]-=2
        board[x[i]+K+1][y[i]+1]-=2
        board[0][0]+=1
        board[x[i]+1][0]-=1
        board[0][y[i]+1]-=1
        board[x[i]+K+1][0]+=1
        board[0][y[i]+K+1]+=1
tmp=[[0 for i in range(2*K)] for i in range(2*K)]
bs=[[0 for i 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:
            tmp[i][j]=board[i][j]
        else:
            tmp[i][j]=board[i][j]+tmp[i-1][j]
for i in range(2*K):
    for j in range(2*K):
        if j==0:
            bs[i][j]=tmp[i][j]
        else:
            bs[i][j]=tmp[i][j]+bs[i][j-1]
ans=bs[0][0]
for i in range(2*K):
    for j in range(2*K):
        if bs[i][j]>ans:
            ans=bs[i][j]
print(ans)

Submission status: Accepted

Solution code:
def d_checker(N, K, Q):
    # マス(x,y)が白⇔マス(x,y+K)が黒なので、希望の色がすべて黒になるようにする
    # 市松模様の周期は2Kなので、x,y座標をそれぞれ2Kで剰余を取った座標と同一視できる
    mat = [[0]*(2*K+2) for _ in range(2*K+2)]
    total = [[0]*(4*K+2) for _ in range(4*K+2)]
    for x, y, c in Q:
        if c == 'W':
            y += K
        mat[(x % (2*K)) + 1][(y % (2*K)) + 1] += 1

    # 事前に累積和を取る
    for x in range(1, 4*K+1):
        for y in range(1, 4*K+1):
            total[x][y] = total[x][y-1] + \
                mat[((x-1) % (2*K)) + 1][((y-1) % (2*K)) + 1]
    for y in range(1, 4*K+1):
        for x in range(1, 4*K+1):
            total[x][y] += total[x-1][y]

    def get(x, y):
        # 市松模様の橋の黒の座標を決めたときに実現できる希望の数
        return total[x+K-1][y+K-1] + total[x-1][y-1] - total[x-1][y+K-1] - total[x+K-1][y-1]

    # 正方形の隅の座標を各々決めたときに実現できる希望の数を求め、最大値を得る
    ans = 0
    for x in range(1, 2*K+1):
        for y in range(1, 2*K+1):
            ans = max(ans, get(x, y)+get(x+K, y+K))
    return ans

N, K = [int(i) for i in input().split()]
Q = [(int(x), int(y), c)
    for x, y, c in [input().split() for i in range(N)]]
print(d_checker(N, K, Q))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())

xy = []
F = [[0]*(2*k+1) for _ in range(2*k+1)]
for __ in range(n):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        y += k
    x %= 2*k
    y %= 2*k

    for _ in range(2):
        x = (x+k)%(2*k)
        y = (y+k)%(2*k)
        #右上
        F[y+1][x+1] += 1
        if x-k >= 0 and y-k >= 0:
            #普通の左上と左上右下
            F[y+1][x-k+1] -= 1
            F[y-k+1][x+1] -= 1
            F[y-k+1][x-k+1] += 1
        elif y-k >= 0:
            #特殊な左
            F[y-k+1][0] += 1
            F[y+1][0] -= 1
            F[y-k+1][x+1] -= 1
            #特殊な左上と左下
            F[y-k+1][x+k+1] += 1
            F[y+1][x+k+1] -= 1
        elif x-k >= 0:
            F[0][x-k+1] += 1
            F[0][x+1] -= 1
            F[y+1][x-k+1] -= 1

            F[y+k+1][x-k+1] += 1
            F[y+k+1][x+1] -=1
        else:
            F[0][x+1] -= 1
            F[y+1][0] -= 1
            F[0][0] += 1
            #左上
            F[y+k+1][0] += 1
            F[y+k+1][x+1] -= 1
            #右下
            F[0][x+k+1] += 1
            F[y+1][x+k+1] -= 1
            #右上
            F[y+k+1][x+k+1] += 1
    if __ == 0:
        pass
        # break
ans = 0
m = 3

from numpy import array
F = array(F)
for i in range(0, 2*k):
    F[:, i+1] += F[:, i]
for i in range(0, 2*k):
    F[i+1, :] += F[i, :]
print(F[:2*k, :2*k].max())

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
v = []
for i in range(n):
    abc = [x for x in input().split()]
    a = int(abc[0])
    b = int(abc[1])
    c = abc[2]
    if c == 'W':
        b += k
    v.append((a % (2*k), b % (2*k)))

s = [[0 for _ in range(3*k+1)] for _ in range(3*k+1)]
s2 = [[0 for _ in range(k+1)] for _ in range(k+1)]
s3 = [[0 for _ in range(k+1)] for _ in range(k+1)]

for i in range(n):
    s[v[i][1]][v[i][0]] += 1
    s[v[i][1]+k][v[i][0]+k] += 1
    s[v[i][1]+k][v[i][0]] -= 1
    s[v[i][1]][v[i][0]+k] -= 1

for i in range(3*k):
    for j in range(3*k):
        s[i+1][j] += s[i][j]
for i in range(3*k):
    for j in range(3*k):
        s[i][j+1] += s[i][j]

for i in range(3*k):
    for j in range(3*k):
        c = (i//k+j//k) % 2
        if c == 0:
            s2[i % k][j % k] += s[i][j]
        else:
            s3[i % k][j % k] += s[i][j]
res = 0

for i in range(k):
    for j in range(k):
        res = max(res, s2[i][j])
        res = max(res, s3[i][j])

print(res)

Submission status: Accepted

Solution code:
import numpy as np


def imos2d(x1, y1, x2, y2, board):
    board[y1][x1] += 1
    board[y2][x2] += 1
    board[y2][x1] -= 1
    board[y1][x2] -= 1


if __name__ == '__main__':
    N, K = map(int, input().split())
    lines = [input() for _ in range(N)]

    K2 = 2 * K
    add_dict = {"W": 0, "B": K}
    board = [[0 for _ in range(K2 + 1)] for _ in range(K2 + 1)]
    for line in lines:
        ls = line.split()
        x = int(ls[0]) % K2
        y = (int(ls[1]) + add_dict[ls[2]]) % K2
        x_ = x % K
        y_ = y % K

        # 左上・右上・中央・左下・右下
        if (x < K and y < K) or (K <= x and K <= y):
            # 左上
            imos2d(0, 0, x_ + 1, y_ + 1, board)
            # 右上
            imos2d(x_ + K + 1, 0, K2, y_ + 1, board)
            # 左下
            imos2d(0, y_ + K + 1, x_ + 1, K2, board)
            # 右下
            imos2d(x_ + K + 1, y_ + K + 1, K2, K2, board)
            # 中央
            imos2d(x_ + 1, y_ + 1, x_ + K + 1, y_ + K + 1, board)
        # 上・下・左・右
        else:
            # 上
            imos2d(x_ + 1, 0, x_ + K + 1, y_ + 1, board)
            # 下
            imos2d(x_ + 1, y_ + K + 1, x_ + K + 1, K2, board)

            # 左
            imos2d(0, y_ + 1, x_ + 1, y_ + K + 1, board)
            imos2d(x_ + K + 1, y_ + 1, K2, y_ + K + 1, board)

    board = np.array(board)
    for x in range(K2):
        board[:, x + 1] += board[:, x]
    for y in range(K2):
        board[y + 1, :] += board[y, :]

    print(board.max())

Submission status: Accepted

Solution code:
import numpy as np


def imos2d(x1, y1, x2, y2, board):
    board[y1][x1] += 1
    board[y2][x2] += 1
    board[y2][x1] -= 1
    board[y1][x2] -= 1


if __name__ == '__main__':
    N, K = map(int, input().split())
    lines = [input() for _ in range(N)]

    # N, K = 4, 3
    # lines = ["0 1 W", "1 2 W", "5 3 B", "5 4 B"]

    K2 = 2 * K
    add_dict = {"W": 0, "B": K}
    board = [[0 for _ in range(K2 + 1)] for _ in range(K2 + 1)]
    for line in lines:
        ls = line.split()
        x = int(ls[0]) % K2
        y = (int(ls[1]) + add_dict[ls[2]]) % K2
        x_ = x % K
        y_ = y % K

        # 左上・右上・中央・左下・右下
        if (x < K and y < K) or (K <= x and K <= y):
            # 左上
            imos2d(0, 0, x_ + 1, y_ + 1, board)
            # 右上
            imos2d(x_ + K + 1, 0, K2, y_ + 1, board)
            # 左下
            imos2d(0, y_ + K + 1, x_ + 1, K2, board)
            # 右下
            imos2d(x_ + K + 1, y_ + K + 1, K2, K2, board)
            # 中央
            imos2d(x_ + 1, y_ + 1, x_ + K + 1, y_ + K + 1, board)
        # 上・下・左・右
        else:
            # 上
            imos2d(x_ + 1, 0, x_ + K + 1, y_ + 1, board)
            # 下
            imos2d(x_ + 1, y_ + K + 1, x_ + K + 1, K2, board)

            # 左
            imos2d(0, y_ + 1, x_ + 1, y_ + K + 1, board)
            imos2d(x_ + K + 1, y_ + 1, K2, y_ + K + 1, board)

    board = np.array(board)
    for x in range(K2):
        board[:, x + 1] += board[:, x]
    for y in range(K2):
        board[y + 1, :] += board[y, :]

    print(board.max())

Submission status: Accepted

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

score = [[0] * (K+1) for y in range(K+1)]
base_hope = 0

for i in range(N):
    x, y, c = input().split()
    x2, y2 = int(x) // K, int(y) // K
    x_coord, y_coord = int(x) % K + 1, int(y) % K + 1
    if ((x2 + y2) % 2 == 0 and c == "W") or ((x2 + y2) % 2 == 1 and c == "B"):
        score[y_coord][x_coord] += 1
        base_hope += 1
    else:
        score[y_coord][x_coord] -= 1

xy = [(x, y) for x in range(K) for y in range(K)]
for x, y in xy:
    score[y+1][x+1] += score[y+1][x] + score[y][x+1] - score[y][x]

max_hope = 0
for x, y in xy:
    hope = base_hope - score[K][x] - score[y][K] + 2 * score[y][x]
    true_hope = hope if hope > N - hope else N - hope
    if true_hope > max_hope:
        max_hope = true_hope

print(max_hope)

Submission status: Accepted

Solution code:
N, K = (int(i) for i in input().split())
W = list()
for index in range(N):
	x, y, c = (s for s in input().split())
	x = int(x)
	y = int(y)
	c = 0 if c == "W" else 1
	if x%(2*K) != x%K:
		c = 1-c
	if y%(2*K) != y%K:
		c = 1-c
	W.append((x%K, y%K, c))

w = [[0 for _ in range(K)] for _ in range(K)]
b = [[0 for _ in range(K)] for _ in range(K)]
wx = [0 for _ in range(K)]
wy = [0 for _ in range(K)]
bx = [0 for _ in range(K)]
by = [0 for _ in range(K)]
for x, y, c in W:
	if c == 0:
		w[x][y] += 1
		wx[x] += 1
		wy[y] += 1
	else:
		b[x][y] += 1
		bx[x] += 1
		by[y] += 1

M = 0
for row in w:
	M += sum(row)

s = M
for x in range(K):
	tmp = s
	for y in range(K):
		s += by[y]
		s -= wy[y]
		M = max(s, N-s, M)
	for y in range(K):
		by[y] += w[x][y]
		by[y] -= b[x][y]
		wy[y] += b[x][y]
		wy[y] -= w[x][y]
	tmp += bx[x]
	tmp -= wx[x]
	s = tmp
	M = max(s, N-s, M)

print(M)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
x, y, c = [None] * N, [None] * N, [None] * N
KK = 2 * K
table = [[0] * (KK+1) for i in range(KK+1)]

for i in range(N):
    x[i], y[i], c[i] = input().split()
    x[i], y[i] = int(x[i]), int(y[i])
    if c[i] == 'W':
        x[i] += K
        c[i] = 'B'
    x[i] %= KK
    y[i] %= KK
    table[y[i]+1][x[i]+1] += 1

for i in range(KK+1):
    for j in range(KK):
        table[i][j+1] += table[i][j]
for i in range(KK):
    for j in range(KK+1):
        table[i+1][j] += table[i][j]

def s(x1, x2, y1, y2):
    global table, KK
    MOD = KK + 1
    x1 = x1 % MOD + x1 // MOD
    y1 = y1 % MOD + y1 // MOD
    x2 = x2 % MOD + x2 // MOD
    y2 = y2 % MOD + y2 // MOD
    x11 = x1
    x21 = 0
    y11 = y1
    y21 = 0
    if x1 < x2:
        x12 = x2
        x22 = 0
    else:
        x12 = KK
        x22 = x2
    if y1 < y2:
        y12 = y2
        y22 = 0
    else:
        y12 = KK
        y22 = y2
    f = lambda _x1, _x2, _y1, _y2: \
            table[_y2][_x2] - table[_y2][_x1] \
            - table[_y1][_x2] + table[_y1][_x1]
    # print('x11: %d, x12: %d, y11: %d, y12: %d' % (x11, x12, y11, y12))
    # a1 = f(x11, x12, y11, y12)
    # print('x21: %d, x22: %d, y11: %d, y12: %d' % (x21, x22, y11, y12))
    # a2 = f(x21, x22, y11, y12)
    # print('x11: %d, x12: %d, y21: %d, y22: %d' % (x11, x12, y21, y22))
    # a3 = f(x11, x12, y21, y22)
    # print('x21: %d, x22: %d, y21: %d, y22: %d' % (x21, x22, y21, y22))
    # a4 = f(x21, x22, y21, y22)
    # print(a1, a2, a3, a4)
    return f(x11, x12, y11, y12) + f(x21, x22, y11, y12) \
            + f(x11, x12, y21, y22) + f(x21, x22, y21, y22)

ans = 0
for i in range(KK):
    for j in range(K):
        tmp = s(i, i+K, j, j+K)
        ni, nj = i + K, j + K
        tmp += s(ni, ni+K, nj, nj+K)
        # print('tmp: %d' % tmp)
        ans = max((ans, tmp))
print(ans)

Submission status: Accepted

Solution code:
def main():
    """
    Range:
        (x,y)
        X: x-K+1 〜 x+K-1
        Y: y-K+1 〜 y+K-1

    rangeをすべて試す: 無理
        1つの希望を満たすように範囲指定:
            模様は確定する
                (0,0)-(K,K) * 2(W or B)
                K^2 * N -> 10^3^2 * 10^5
            他の希望は満たされるか判定
    """
    N, K = map(int, input().split())
    xy = []
    for _ in range(N):
        x, y, c = input().split()
        a = K if c == "B" else 0
        xy.append((int(x), int(y) + a))

    AC(K, xy)
    # TLE(K, xy)


def fix(x, K2):
    return min(max(0, x), K2)


def boundary(x, y, K):
    K2 = K * 2
    s = set()
    for i in range(-2, 2):
        for j in range(-2, 2):
            if (i + j) % 2 == 1:
                continue

            x1 = fix(x + i * K, K2)
            y1 = fix(y + j * K, K2)
            x2 = fix(x + (i + 1) * K, K2)
            y2 = fix(y + (j + 1) * K, K2)

            if x1 == x2 or y1 == y2:
                continue

            s.add(((x1, y1), (x2, y2)))

    return s

def AC(K, xy):
    K2 = K * 2
    w = [
        [0] * (K2 + 1)
        for _ in range(K2 + 1)
    ]

    for x, y in xy:
        x = x % K2
        y = y % K2
        for (x1, y1), (x2, y2) in boundary(x, y, K):
            w[y1][x1] += 1
            w[y1][x2] -= 1
            w[y2][x1] -= 1
            w[y2][x2] += 1

    ans = max_cumsum(w)
    print(ans)


def max_cumsum(w):
    # error in atcoder pypy3
    #import numpy as np
    #return np.array(w).cumsum(axis=1).cumsum(axis=0).max()

    import copy
    w = copy.deepcopy(w)
    l = len(w)
    for i in range(1, l):
        for j in range(l):
            w[j][i] += w[j][i-1]

    for i in range(l):
        for j in range(1, l):
            w[j][i] += w[j-1][i]

    return max(map(max, w))


def TLE(K, xy):
    ans = 0
    for i in range(2 * K):
        for j in range(2 * K):
            tmp_ans = 0
            for x, y in xy:
                x = (x + i) % (2 * K)
                y = (y + j) % (2 * K)

                w1 = x < K and y < K
                w2 = x >= K and y >= K
                if w1 or w2:
                    tmp_ans += 1

            ans = max(ans, tmp_ans)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
B = [[0]*k for i in range(k)]
W = [[0]*k for i in range(k)]
for i in range(n):
    x, y, c = input().split(); x = int(x); y = int(y)
    x %= 2*k; y %= 2*k
    if (k <= x) == (k <= y):
        (B if c == 'B' else W)[y%k][x%k] += 1
    else:
        (W if c == 'B' else B)[y%k][x%k] += 1
def calc(M, n):
    D = [[0]*(n+1) for i in range(n+1)]
    for i in range(1, n+1):
        tmp = 0
        for j in range(1, n+1):
            tmp += M[i-1][j-1]
            D[i][j] = tmp + D[i-1][j]
    return D

# [a, c) * [b, d)
def su(D, a, b, c, d):
    return D[d][c] - D[d][a] - D[b][c] + D[b][a]

DB = calc(B, k)
DW = calc(W, k)
ans = 0
for i in range(k):
    for j in range(k):
        ans = max(ans, su(DB, 0, 0, i, j) + su(DB, i, j, k, k) + su(DW, i, 0, k, j) + su(DW, 0, j, i, k))
        ans = max(ans, su(DW, 0, 0, i, j) + su(DW, i, j, k, k) + su(DB, i, 0, k, j) + su(DB, 0, j, i, k))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def getBoundary(p, k, k2):
    if p - k + 1 >= 0:
        return [(p - k + 1, p + 1)]
    else:
        return [(0, p + 1), ((p - k + 1) % k2, k2)]

n, k = map(int, input().strip().split())
k2 = k * 2
b = [[0 for i in range(k2 + 1)] for j in range(k2 + 1)]

for i in range(n):
    x_str, y_str, c_str = input().strip().split()
    x = int(x_str) % k2
    y = (int(y_str) + (c_str == 'B') * k) % k2
    for xb, xe in getBoundary(x % k2, k, k2):
        for yb, ye in getBoundary(y % k2, k, k2):
            b[xb][yb] += 1
            b[xb][ye] -= 1
            b[xe][yb] -= 1
            b[xe][ye] += 1
    for xb, xe in getBoundary((x + k) % k2, k, k2):
        for yb, ye in getBoundary((y + k) % k2, k, k2):
            b[xb][yb] += 1
            b[xb][ye] -= 1
            b[xe][yb] -= 1
            b[xe][ye] += 1

arr_b = np.array(b)
for i in range(k2):
    arr_b[i + 1] += arr_b[i]
for j in range(k2):
    arr_b[:, j + 1] += arr_b[:, j]
print(arr_b.max())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

n, k = map(int, sys.stdin.readline().strip().split(" "))
xyc = [l.strip().split(" ") for l in sys.stdin.readlines()]
xy = [(int(_x) % (2 * k), int(_y) % (2 * k) if _c == "W" else (int(_y) + k) % (2 * k))
      for (_x, _y, _c) in xyc]

# ans = np.zeros((2 * k, 2 * k), dtype=np.int32)
ans = [[0 for j in range(2 * k + 1)] for i in range(2 * k + 1)]
for _x, _y in xy:
    if (_x - k + 0.5) * (_y - k + 0.5) > 0:
        _x %= k
        _y %= k
        ans[_x][_y] += 2
        ans[_x + k][_y] -= 2
        ans[_x][_y + k] -= 2
        ans[_x + k][_y + k] += 2
        ans[_x + k][0] += 1
        ans[0][_y + k] += 1
        ans[0][0] += 1
        ans[_x][0] -= 1
        ans[0][_y] -= 1
    else:
        _x %= k
        _y %= k
        ans[_x][_y] -= 2
        ans[_x + k][_y] += 2
        ans[_x][_y + k] += 2
        ans[_x + k][_y + k] -= 2
        ans[_x + k][0] -= 1
        ans[0][_y + k] -= 1
        ans[_x][0] += 1
        ans[0][_y] += 1
print(np.asarray(ans).cumsum(axis=1).cumsum(axis=0).max())

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
ub = K * 2
b = [[0 for j in range(ub + 1)] for i in range(ub + 1)]
ADD = {"B": 0, "W": K}


def create_bound(p, K, ub):
    if p - K + 1 >= 0:
        return [(p - K + 1, p + 1)]
    else:
        return [(0, p + 1), ((p - K + 1) % ub, ub)]


for i in range(N):
    x, y, c = input().split()
    nx = int(x) % ub
    ny = (int(y) + ADD[c]) % ub
    for add in [0, K]:
        for xlb, xub in create_bound((nx + add) % ub, K, ub):
            for ylb, yub in create_bound((ny + add) % ub, K, ub):
                b[xlb][ylb] += 1
                b[xlb][yub] -= 1
                b[xub][ylb] -= 1
                b[xub][yub] += 1

b_arr = np.array(b)
for i in range(ub):
    b_arr[i + 1, :] += b_arr[i, :]
for j in range(ub):
    b_arr[:, j + 1] += b_arr[:, j]
print(b_arr.max())

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
ub = K * 2
b = [[0 for j in range(ub + 1)] for i in range(ub + 1)]
ADD = {"B": 0, "W": K}

def create_bound(p, K, ub):
	if p - K + 1 >= 0:
		return [(p - K + 1, p + 1)]
	else:
		return [(0, p + 1), ((p - K + 1) % ub, ub)]

for i in range(N):
	x, y, c = input().split()
	nx = int(x) % ub
	ny = (int(y) + ADD[c]) % ub
	for add in [0, K]:
		for xlb, xub in create_bound((nx + add) % ub, K, ub):
			for ylb, yub in create_bound((ny + add) % ub, K, ub):
				b[xlb][ylb] += 1
				b[xlb][yub] -= 1
				b[xub][ylb] -= 1
				b[xub][yub] += 1

b_arr = np.array(b)
for i in range(ub):
	b_arr[i + 1, :] += b_arr[i, :]
for j in range(ub):
	b_arr[:, j + 1] += b_arr[:, j]
print(b_arr.max())

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ub = K * 2
b = [[0 for j in range(ub + 1)] for i in range(ub + 1)]

def create_bound(p):
	if p - K + 1 >= 0:
		return [(p - K + 1, p + 1)]
	else:
		return [(0, p + 1), ((p - K + 1) % ub, ub)]

for i in range(N):
	x, y, c = input().split()
	nx = int(x) % ub
	ny = (int(y) + (K if c == "W" else 0)) % ub
	for add in [0, K]:
		for xlb, xub in create_bound((nx + add) % ub):
			for ylb, yub in create_bound((ny + add) % ub):
				b[xlb][ylb] += 1
				b[xlb][yub] -= 1
				b[xub][ylb] -= 1
				b[xub][yub] += 1

for i in range(ub):
	for j in range(ub):
		b[i][j + 1] += b[i][j]
for j in range(ub):
	for i in range(ub):
		b[i + 1][j] += b[i][j]
print(max(max(b[i]) for i in range(ub)))

Submission status: Accepted

Solution code:
import sys
N, K = map(int, input().split())
x, y, c = [0] * N, [0] * N, [0] * N
board = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
MOD = 2 * K + 1
for i in range(N):
    x[i], y[i], c[i] = input().split()
    x[i], y[i] = int(x[i]), int(y[i])
    if c[i] == 'W':
        x[i] += K
        c[i] = 'B'
    x[i] %= 2 * K
    y[i] %= 2 * K
    board[y[i]+1][x[i]+1] += 1

# for i in range(2*K+1):
#     print(' '.join(map(str, board[i])))
# print('================')
for i in range(2*K+1):
    for j in range(2*K):
        board[i][j+1] += board[i][j]
for j in range(2*K+1):
    for i in range(2*K):
        board[i+1][j] += board[i][j]

# for i in range(2*K+1):
#     print(' '.join(map(str, board[i])))
ans = 0
def c(x1, y1):
    global K, board
    x1 = x1 % MOD + x1 // MOD
    y1 = y1 % MOD + y1 // MOD
    x2 = (x1 + K) % MOD + (x1 + K) // MOD
    y2 = (y1 + K) % MOD + (y1 + K) // MOD
    if x1 < x2:
        x11, x12, x21, x22 = x1, x2, 0, 0
    else:
        x11, x12, x21, x22 = x1, -1, 0, x2
    if y1 < y2:
        y11, y12, y21, y22 = y1, y2, 0, 0
    else:
        y11, y12, y21, y22 = y1, -1, 0, y2
    f = lambda a, b, c, d: board[a][b] + board[c][d]\
            - board[a][d] - board[c][b]
    # print("x11: %d, x12: %d" % (x11, x12))
    # print("x21: %d, x22: %d" % (x21, x22))
    # print("y11: %d, y12: %d" % (y11, y12))
    # print("y21: %d, y22: %d" % (y21, y22))
    # print("a1: %d" % f(y12, x12, y11, x11))
    # print("a2: %d" % f(y22, x22, y21, x21))
    # print("a3: %d" % f(y12, x22, y11, 0))
    # print("a4: %d" % f(y22, x12, 0, x11))
    ret = 0
    ret += f(y12, x12, y11, x11)
    ret += f(y22, x22, y21, x21)
    ret += f(y12, x22, y11, x21)
    ret += f(y22, x12, y21, x11)
    return ret


for i in range(2*K+1):
    for j in range(K+1):
        # print('i: %d, j: %d' % (i, j))
        # print('c(i, j): %d' % c(i, j))
        # print('c(i+K, j+K): %d' % c(i+K, j+K))
        # print('')
        ans = max((ans, c(i, j) + c(i+K, j+K)))

print(ans)

Submission status: Runtime Error

Solution code:
def calcb(lx,ly,rx,ry):
  if rx<0 or ry<0 or lx>rx or ly>ry:
    return 0
  ret=acum1[ry][rx]
  if lx!=0:
    ret-=acum1[ry][lx-1]
  if ly!=0:
    ret-=acum1[ly-1][rx]
  if lx!=0 and ly!=0:
    ret+=acum1[ly-1][lx-1]
  return ret

def calcw(lx,ly,rx,ry):
  if rx<0 or ry<0 or lx>rx or ly>ry:
    return 0
  ret=acum2[ry][rx]
  if lx!=0:
    ret-=acum2[ry][lx-1]
  if ly!=0:
    ret-=acum2[ly-1][rx]
  if lx!=0 and ly!=0:
    ret+=acum2[ly-1][lx-1]
  return ret

n,k=map(int,input().split())
board1=[[0]*(2*k) for _ in range(2*k)]
board2=[[0]*(2*k) for _ in range(2*k)]
acum1=[[0]*(2*k) for _ in range(2*k)]
acum2=[[0]*(2*k) for _ in range(2*k)]
for _ in range(n):
  x,y,c=input().split()
  x,y=int(x)%(2*k),int(y)%(2+k)
  if c=='B':
    board1[y][x]+=1
  if c=='W':
    board2[y][x]+=1
for i in range(2*k):
  for j in range(2*k):
    acum1[i][j]=board1[i][j]
    acum2[i][j]=board2[i][j]
    if i!=0:
      acum1[i][j]+=acum1[i-1][j]
      acum2[i][j]+=acum2[i-1][j]
    if j!=0:
      acum1[i][j]+=acum1[i][j-1]
      acum2[i][j]+=acum2[i][j-1]
    if i!=0 and j!=0:
      acum1[i][j]-=acum1[i-1][j-1]
      acum2[i][j]-=acum2[i-1][j-1]
ans=0
for i in range(k):
  for j in range(k):
    tmp=0
    lx,ly=i,j
    rx,ry=lx+k-1,ly+k-1
    #1個目の黒マス
    tmp+=calcb(lx,ly,rx,ry)
    #左上の黒マス
    tlx,tly=0,0
    trx,ttry=lx-1,ly-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #右上の黒マス
    tlx,tly=rx+1,0
    trx,ttry=2*k-1,ly-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #左下の黒マス
    tlx,tly=0,ry+1
    trx,ttry=lx-1,2*k-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #右下の黒マス
    tlx,tly=rx+1,ry+1
    trx,ttry=2*k-1,2*k-1
    tmp+=calcb(tlx,tly,trx,ttry)
    #上の白マス
    tlx,tly=lx,0
    trx,ttry=rx,ly-1
    tmp+=calcw(tlx,tly,trx,ttry)
    #左の白マス
    tlx,tly=0,ly
    trx,ttry=lx-1,ry
    tmp+=calcw(tlx,tly,trx,ttry)
    #右の白マス
    tlx,tly=rx+1,ly
    trx,ttry=2*k-1,ry
    tmp+=calcw(tlx,tly,trx,ttry)
    #下の白マス
    tlx,tly=lx,ry+1
    trx,ttry=rx,2*k-1
    tmp+=calcw(tlx,tly,trx,ttry)
    ans=max(ans,tmp)
print(ans)

Submission status: Runtime Error

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

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

wcumsum = [array.array('I',[0]*(3*K+1))] + [array.array('I',[0]+list(accumulate(row))) for row in wmap]
hcumsum = [array.array('I',[0]*(3*K+1))] + [array.array('I',[0]+list(accumulate(row))) for row in hmap]

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

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

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

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

print(ans)

Submission status: Runtime Error

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

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

wcumsum = [array.array('H',[0]*(3*K+1))] + [array.array('H',[0]+list(accumulate(row))) for row in wmap]
hcumsum = [array.array('H',[0]*(3*K+1))] + [array.array('H',[0]+list(accumulate(row))) for row in hmap]

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

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

def main():
  def mycount(x1,y1,x2,y2,mat,s):
    return mat[s,x2,y2]-mat[s,x1,y2]-mat[s,x2,y1]+mat[s,x1,y1]
  wb={'W':0,'B':1}
  n,k=map(int,readline().split())
  xyc=[l.split() for l in read().splitlines()]
  xyc=[[int(lst[0]) % (2*k),int(lst[1]) % (2*k),wb[lst[2]]] for lst in xyc]
  mat=np.zeros((2,4*k+1,4*k+1),dtype='int64')
  cand=np.zeros((2,2*k+1,2*k+1),dtype='int64')
  for i in range(4):
    for e in xyc:
      mat[e[2],e[0]+1+2*k*(i&1),e[1]+1+2*k*(i>>1&1)]+=1
  mat=np.cumsum(mat,axis=1)
  mat=np.cumsum(mat,axis=2)
 # for i in range(1,4*k+1):
 #   for j in range(1,4*k+1):
 #     mat[:,i,j]=mat[:,i,j]+mat[:,i-1,j]+mat[:,i,j-1]-mat[:,i-1,j-1]
  cand+=mat[0,k:3*k+1,k:3*k+1]+mat[0,:2*k+1,:2*k+1]-mat[0,k:3*k+1,:2*k+1]-mat[0,:2*k+1,k:3*k+1]\
  cand+=mat[0,2*k:4*k+1,2*k:4*k+1]+mat[0,k:3*k+1,k:3*k+1]-mat[0,2*k:4*k+1,k:3*k+1]-mat[0,k:3*k+1,2*k:4*k+1]\
  cand+=mat[1,2*k:4*k+1,k:3*k+1]+mat[1,k:3*k+1,:2*k+1]-mat[1,2*k:4*k+1,:2*k+1]-mat[1,k:3*k+1,k:3*k+1]\
  cand+=mat[1,k:3*k+1,2*k:4*k+1]+mat[1,:2*k+1,k:3*k+1]-mat[1,:2*k+1,2*k:4*k+1]-mat[1,k:3*k+1,k:3*k+1]
  #print(mat)
  print(np.max(cand))
  
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
class CumulativeSum2D:
  def __init__(self,a):
    self.h=len(a)
    self.w=len(a[0])
    self.s=[(self.w+1)*[0]for _ in range(self.h+1)]
    for i in range(self.h):
      for j in range(self.w):
        self.s[i+1][j+1]=self.s[i+1][j]+self.s[i][j+1]-self.s[i][j]+a[i][j]
    for i in self.s:print(i)
  def sum(self,i1,j1,i2,j2):
    return self.s[i2+1][j2+1]-self.s[i1][j2+1]-self.s[i2+1][j1]+self.s[i1][j1]
n,k=map(int,input().split())
a=[(3*k+7)*[0]for _ in range(3*k+7)]
for _ in range(n):
  x,y,c=input().split()
  x=int(x)
  y=int(y)
  if c=="W":x+=k
  x%=2*k
  y%=2*k
  a[x][y]+=1
  a[x+k][y]-=1
  a[x][y+k]-=1
  a[x+k][y+k]+=1
  a[x+k][y+k]+=1
  a[x+k+k][y+k]-=1
  a[x+k][y+k+k]-=1
  a[x+k+k][y+k+k]+=1
b=[(3*k+8)*[0] for _ in range(3*k+8)]
ans=0
for i in range(3*k+7):
  for j in range(3*k+7):
    b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
    ans=max(ans,b[i+1][j+1])
print(ans)