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:
import sys
import numpy as np
from collections import Counter

read = sys.stdin

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

x = np.where(c == 'B', x - K, x)
x %= k
y %= k

'''
# grid[[1,2],[1,2]]+=1 としてもgrid[1,2]=1であり重複は考慮されない。
# uniqueを使って(x,y)の重複をカウントする
# return_countはver1.9からだった・・・ ダメじゃん
xy, cnt = np.unique(x + y * 10000, return_counts=True)
x = xy % 10000
y = xy // 10000
'''
xy = Counter(list(zip(x, y)))
cnt = np.array(list(xy.values()), np.int64)
xy = np.array(list(xy.keys()), np.int64)
x = xy[:, 0]
y = xy[:, 1]

grid = np.zeros((3 * K, 3 * K), np.int64)
grid[x, y] += cnt
grid[x + K, y + K] += cnt
grid[x + K, y] -= cnt
grid[x, y + K] -= cnt
np.cumsum(grid, axis=0, out=grid)
np.cumsum(grid, axis=1, out=grid)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
ps = []
table = [[0] * (2 * K) for _ in range(2 * K)]
res = 0
ws = 0
for i in range(N):
  u, v, t = input().split()
  u = int(u)
  v = int(v)
  ps.append((u % (2 * K), v % (2 * K), t))
  table[u % (2 * K)][v % (2 * K)] += (-1) ** int(t == "W")
  table[(u + K) % (2 * K)][(v + K) % (2 * K)] += (-1) ** int(t == "W")
  ws += (t == "W")
#print(table)
cs = [[0] * (2 * K + 1) for _ in range(2 * K)]
for i in range(2 * K):
  for j in range(2 * K): cs[i][j + 1] = cs[i][j] + table[i][j]

for i in range(2 * K):
  t = 0
  tres = 0
  for j in range(K): t += cs[j][min(2 * K, i + K)] + cs[j][max(0, i - K)] - cs[j][i] 
  tres = max(tres, t + ws)
  for j in range(2 * K):
    t -= cs[j][min(2 * K, i + K)] + cs[j][max(0, i - K)] - cs[j][i]
    t += cs[(j + K) % (2 * K)][min(2 * K, i + K)] + cs[(j + K) % (2 * K)][max(0, i - K)] - cs[(j + K) % (2 * K)][i]
    tres = max(tres, t + ws)
    #print(tres, t, i, j + 1, j + K)
  res = max(res, tres)
print(res)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
g = [[0]*(k+1) for _ in range(k+1)]
ans,b = 0,0
for _ in range(n):
  x,y,c = input().split()
  x,y = int(x), int(y)
  d = x//k + y//k
  x %= k; y %= k
  if (c == 'W') ^ (d%2):
    g[x+1][y+1] += 1
  else:
    g[x+1][y+1] -= 1
    b += 1
for i in range(k):
  for j in range(k):
    g[i+1][j+1] += g[i][j+1] + g[i+1][j] - g[i][j]
for i in range(k):
  for j in range(k):
    cur = g[k][k] - g[k][j] - g[i][k] + g[i][j]*2 + b
    if cur > ans: ans = cur
    if n-cur > ans: ans = n-cur
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    
    imos2d = [[0]*(2*K+1) for _ in range(2*K+1)]
    
    def get_cord(x):
        if x<K-1:
            return [(0,x+1), (x+K+1,2*K)]
        else:
            return [(x-K+1,x+1)]

    for _ in range(N):
        x,y,c = ST().split()
        x,y = int(x), int(y)
        if c=="W":
            x+=K
        x,y = x%(2*K), y%(2*K)
        for base in [0,K]:
            for l,r in get_cord((x+base)%(2*K)):
                for u,d in get_cord((y+base)%(2*K)):
                    imos2d[l][u] += 1
                    imos2d[l][d] -= 1
                    imos2d[r][u] -= 1
                    imos2d[r][d] += 1

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


    ans = 0
    for a in imos2d:
        ans = max(ans,max(a))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
from datetime import datetime

#print(datetime.now())
n,k = map(int ,input().split())
p = [[0] * (2*k) for i in range(2*k)]
ans = 0
for i in range(n):
  x,y,c = input().split()
  x = int(x)
  y = int(y)
  if c == 'B':
    x += k
  p[x%(2*k)][y%(2*k)] += 1
#[print(p[i]) for i in range(2*k)]
#print()
#print(datetime.now())

csum1 = [[0]*(2*k) for i in range(2*k)]
#csum1 = copy.deepcopy(p)
for i in range(2*k):
    for j in range(0, k):
        csum1[i][0] += p[i][j]
    for j in range(1, 2*k):
        csum1[i][j] = csum1[i][j-1] - p[i][j-1] + p[i][(j+k-1)%(2*k)]
#print(datetime.now())
#[print(csum1[i]) for i in range(2*k)]
#print()

csum2 = [[0]*(2*k) for i in range(2*k)]
#csum2 = copy.deepcopy(csum1)
#print(datetime.now())
for j in range(2*k):
    for i in range(0, k):
        csum2[0][j] += csum1[i][j]
    for i in range(1, 2*k):
        csum2[i][j] = csum2[i-1][j] - csum1[i-1][j] + csum1[(i+k-1)%(2*k)][j]

#[print(csum2[i]) for i in range(2*k)]
#print(datetime.now())
for i in range(2*k):
    for j in range(2*k):
        ans = max(ans, csum2[i][j] + csum2[(i+k)%(2*k)][(j+k)%(2*k)])

print(ans)

Submission status: Accepted

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

N, K = map(int, input().split())
white = [[0]*(K+1) for _ in range(2*K+1)]
black = [[0]*(K+1) for _ in range(2*K+1)]
for _ in range(N):
    str_h, str_w, c = map(str, input().rstrip().split())
    h = int(str_h)%(2*K)
    w = int(str_w)%(2*K)
    if c == "W":
        if w >= K:
            if h >= K:
                white[h-K+1][w-K+1] += 1
            else:
                white[h+K+1][w-K+1] += 1
        else:
            white[h+1][w+1] += 1
    else:
        if w >= K:
            if h >= K:
                black[h-K+1][w-K+1] += 1
            else:
                black[h+K+1][w-K+1] += 1
        else:
            black[h+1][w+1] += 1

for h in range(1, 2*K+1):
    for w in range(1, K+1):
        white[h][w] += white[h][w-1] + white[h-1][w] - white[h-1][w-1]
        black[h][w] += black[h][w-1] + black[h-1][w] - black[h-1][w-1]

ans = 0
for h in range(K+1):
    for w in range(K+1):
        b1 = black[h][w]
        b2 = black[h+K][K] - black[h+K][w] - black[h][K] + black[h][w]
        b3 = black[2*K][w] - black[h+K][w]
        w1 = white[h][K] - white[h][w]
        w2 = white[h+K][w] - white[h][w]
        w3 = white[2*K][K] - white[2*K][w] - white[h+K][K] + white[h+K][w]
        ans = max(ans, b1+b2+b3+w1+w2+w3)

        b1 = white[h][w]
        b2 = white[h+K][K] - white[h+K][w] - white[h][K] + white[h][w]
        b3 = white[2*K][w] - white[h+K][w]
        w1 = black[h][K] - black[h][w]
        w2 = black[h+K][w] - black[h][w]
        w3 = black[2*K][K] - black[2*K][w] - black[h+K][K] + black[h+K][w]
        ans = max(ans, b1+b2+b3+w1+w2+w3)

print(ans)

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)

    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
        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 * 2)
        if c_ == 'W':
            y = (y + k) % (k * 2)
            # すべて黒にする
        g[y][x] += 1  # WA頂点の存在の有無ではなく、頂点数を数えるので、=1ではなく、+=1

    acc2D = Acc2D(g)

    ret = 0
    # 中央にk*kの区画をとり、黒または白に塗る(条件を満たす個数:黒=s,白=n-s)
    # 4辺を伸ばして、2k*2kの区画を分割し、各区画を評価する
    for r in range(k):  # r+k < k*2
        for c in range(k):  # c+k < k*2
            s = (
                    acc2D.get(0, r, 0, c)
                    + acc2D.get(0, r, c + k, k * 2)
                    + acc2D.get(r, r + k, c, c + k)
                    + acc2D.get(r + k, k * 2, 0, c)
                    + acc2D.get(r + k, k * 2, c + k, k * 2)
            )
            ret = max(ret, s, n - s)

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

M = np.zeros((K2, K2), int)
nb = 0
for _ in range(N):
  x, y, c = input().split()
  x = int(x) % K2
  y = int(y) % K2
  if c=='B': nb+=1
  M[x, y] += 1 if c=='W' else -1

Sx = np.zeros((K2, K2+1), int)
for y in range(K2):
  Sx[:, y+1] = Sx[:, y] + M[:, y]

S = np.zeros((K2+1, K2+1), int)
for x in range(K2):
  S[x+1] = S[x] + Sx[x]

ans = -1000000
for x in range(K2):
  x0 = 0
  x1 = max(x-K , 0)
  x2 = x
  x3 = min(x+K , K2)
  x4 = K2

  T1 = S[x4] - S[x3] + S[x2] - S[x1]
  T2 = S[x3] - S[x2] + S[x1] - S[x0]

  U = T1[K2] - T1[K:K2] + T1[:K] + T2[K:K2] - T2[:K]
  ans = max(ans, np.max(U))
  
print(nb + ans)

Submission status: Accepted

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

    if x > k-1:
        x -= k
        c += 1
    if y > k-1:
        y -=k
        c += 1
    c %= 2

    if c == 1:
        white += 1
        imos[x][y] -= 1
    else:
        imos[x][y] += 1

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

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

ans = 0
for i in range(k):
    for j in range(k):
        exp = imos[k-1][k-1] - imos[k-1][j] - imos[i][k-1] + 2 * imos[i][j] + white
        ans = max(ans, max(exp, n - exp))

print(ans)

Submission status: Accepted

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

def query(x1, y1, x2, y2, acc):
    return acc[x2+1][y2+1]-acc[x2+1][y1]-acc[x1][y2+1]+acc[x1][y1]

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

for _ in range(N):
    xi, yi, ci = input().split()
    xi = int(xi)
    yi = int(yi)
    t = (xi-xi%K)//K+(yi-yi%K)//K
    
    if t%2==1:
        ci = 'B' if ci=='W' else 'W'
    
    if ci=='W':
        W[xi%K][yi%K] += 1
    else:
        B[xi%K][yi%K] += 1


W_acc = [[0]*(K+1) for _ in range(K+1)]
B_acc = [[0]*(K+1) for _ in range(K+1)]

for i in range(K):
    for j in range(K):
        W_acc[i+1][j+1] = W_acc[i+1][j]+W_acc[i][j+1]-W_acc[i][j]+W[i][j]
        B_acc[i+1][j+1] = B_acc[i+1][j]+B_acc[i][j+1]-B_acc[i][j]+B[i][j]
        
ans = 0

for i in range(K):
    for j in range(K):
        clear_w = query(0, 0, i, j, W_acc)+query(i+1, j+1, K-1, K-1, W_acc)
        clear_b = query(i+1, 0, K-1, j, B_acc)+query(0, j+1, i, K-1, B_acc)
        ans = max(ans, clear_w+clear_b)
        
        clear_w = query(0, 0, i, j, B_acc)+query(i+1, j+1, K-1, K-1, B_acc)
        clear_b = query(i+1, 0, K-1, j, W_acc)+query(0, j+1, i, K-1, W_acc)
        ans = max(ans, clear_w+clear_b)
        
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,K=map(int,input().split())
#x,y,c=[],[],[]
lis=[[[0]*K for _ in range(K)] for i in range(2)]
for i in range(N):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    """x.append(int(xx))
    y.append(int(yy))
    c.append(cc)"""
    if c=="B" :
        C=1
    if c=="W":
        C=0
    now=(x//K+y//K+C)%2
    lis[now][x%K][y%K]+=1
#print(lis)
for t in range(2):
    for i in range(K):
        for j in range(1,K):
            lis[t][i][j]+=lis[t][i][j-1]
    #print(lis)
    for i in range(1,K):
        for j in range(K):
            lis[t][i][j]+=lis[t][i-1][j]
            #print("A",lis)
"""for t in range(2):
    for i in range(K):
        for j in range(K):
            if i!=0 : lis[t][i][j]+=lis[t][i-1][j]
            if j!=0 : lis[t][i][j]+=lis[t][i][j-1]
            if i!=0 and j!=0:
                lis[t][i][j]-=lis[t][i-1][j-1]"""
#print(lis)
ans=0
for t in range(2):
    for i in range(K):
        for j in range(K):
            cnt=2*lis[t][i][j]+lis[t][-1][-1]-lis[t][i][-1]-lis[t][-1][j]\
            +lis[1-t][i][-1]+lis[1-t][-1][j]-2*lis[1-t][i][j]
            ans=max(ans,cnt)
"""
for i in range(K):
    for j in range(K):
        cnt=-2*lis[i][j]+lis[i][-1]+lis[-1][j]
        ans=max(ans,cnt)"""

print(ans)
#print(x,y,c)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc086/submissions/3454297

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 = 0
    for row in range(K):
        for col in range(K):
            tmp = (
                    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)
            )
            ret = max(ret, tmp, N - tmp)
            # xox
            # oxo
            # xox
            # x=tmp
            # o=N-tmp

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from numpy import*
N,K=map(int,input().split())
m=zeros((3*K,3*K),dtype=int)
L=2*K
o=0
for _ in [0]*N:
 x,y,c=input().split()
 x,y=int(x)%L,int(y)%L
 t=c=='W'
 m[x,y]+=2*t-1
 o+=t
for _ in [0,0]:
 m[L:]=m[:K]
 m=cumsum(m,axis=0)
 m[:L]-=m[K:]
 m=m.T
m=m[:L,:L]
print(o-int((m+roll(roll(m,K,axis=0),K,axis=1)).min()))

Submission status: Accepted

Solution code:
class twoD_cumsum():
    # da[i][j]:(0,0)~(i,j)の長方形の和
    def __init__(self,h,w,a):
        self.h = h; self.w = w
        self.da = a
        for i in range(1, w):
            self.da[0][i] = self.da[0][i - 1] + a[0][i]
        for i in range(1, h):
            cnt_w = 0
            for j in range(w):
                cnt_w += a[i][j]
                self.da[i][j] = self.da[i - 1][j] + cnt_w
    def da_generate(self, da):
        return da
    # da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和
    def da_calc(self, p, q, x, y):
        if p > x or q > y:
            return 0
        if p == 0 and q == 0:
            return self.da[x][y]
        if p == 0:
            return self.da[x][y] - self.da[x][q - 1]
        if q == 0:
            return self.da[x][y] - self.da[p - 1][y]
        return self.da[x][y] - self.da[p - 1][y] - self.da[x][q - 1] + self.da[p - 1][q - 1]

def examD():
    N, K = LI()
    #y=0,x=0上で、原点とおなじグループかどうか
    colorXY = [[0] * (2*K) for _ in range(2*K)]
    for _ in range(N):
        #原点の色を白(0)とする
        x, y, c = LSI()
        x, y = int(x), int(y)
        if c=="B":
            y +=K
        colorXY[x%(2*K)][y%(2*K)] +=1
    ans = 0
    ansC = N
    da = twoD_cumsum(2*K, 2*K, colorXY)
    for i in range(K):
        for j in range(K):
            cur = da.da_calc(0,0,K-i-1,K-j-1) + da.da_calc(K-i,K-j,2*K-i-1,2*K-j-1)\
                + da.da_calc(0,2*K-j,K-i-1,2*K-1) + da.da_calc(2*K-i,0,2*K-1,K-j-1)\
                + da.da_calc(2*K-i,2*K-j,2*K-1,2*K-1)
            ans = max(ans,cur)
            ansC = min(ansC,cur)
    print(max(ans,N-ansC))

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Accepted

Solution code:
#da[i][j]:(0,0)~(i,j)の長方形の和
def da_generate(h,w,a):
    da = [[0]*w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1,w):
        da[0][i] = da[0][i-1]+a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i-1][j]+cnt_w
    return da

#da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和
def da_calc(da,p,q,x,y):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y]-da[x][q-1]
    if q == 0:
        return da[x][y]-da[p-1][y]
    return da[x][y]-da[p-1][y]-da[x][q-1]+da[p-1][q-1]

def examD():
    N, K = LI()
    #y=0,x=0上で、原点とおなじグループかどうか
    colorXY = [[0] * (2*K) for _ in range(2*K)]
    for _ in range(N):
        #原点の色を白(0)とする
        x, y, c = LSI()
        x, y = int(x), int(y)
        if c=="B":
            y +=K
        colorXY[x%(2*K)][y%(2*K)] +=1
    ans = 0
    ansC = N
    da = da_generate(2*K, 2*K, colorXY)
    for i in range(K):
        for j in range(K):
            cur = da_calc(da,0,0,K-i-1,K-j-1) + da_calc(da,K-i,K-j,2*K-i-1,2*K-j-1)\
                + da_calc(da,0,2*K-j,K-i-1,2*K-1) + da_calc(da,2*K-i,0,2*K-1,K-j-1)\
                + da_calc(da,2*K-i,2*K-j,2*K-1,2*K-1)
            ans = max(ans,cur)
            ansC = min(ansC,cur)
    print(max(ans,N-ansC))

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
X = [[0] * (2*K) for _ in range(3*K)]
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == "B":
        x += K
    x %= 2*K
    y %= 2*K
    if y >= K:
        x, y = (x+K) % (2*K), y - K
    for dx, dy in ((0, 0), (2*K, 0), (K, K), (-K, K)):
        xx, yy = x + dx, y + dy
        if 0 <= xx < 3*K and 0 <= yy < 2*K:
            X[xx][yy] += 1

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

ma = 0
for i in range(2*K):
    for j in range(K):
        ma = max(ma, X[i+K][j+K] - X[i][j+K] - X[i+K][j] + X[i][j])
print(ma)

Submission status: Accepted

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

def cumsum_2d(inlist,h,w):
    
    outlist = [ [ inlist[i-1][j-1] if i != 0 and j != 0 else 0 for i in range(k+1) ] for j in range(k+1) ]
    for i in range(1,h+1):
        tmp = 0
        for j in range(1,w+1):
            tmp += outlist[i][j]
            outlist[i][j] = tmp
    for i in range(1,w+1):
        tmp = 0
        for j in range(1,h+1):
            tmp += outlist[j][i]
            outlist[j][i] = tmp

    return outlist
    
n, k = [ int(v) for v in input().split() ]
hope = [ [ a for a in input().split() ] for i in range(n) ]

b_board = [ [ 0 for i in range(k)] for j in range(k) ]
w_board = [ [ 0 for i in range(k)] for j in range(k) ]



for h, w, c in hope:
    a1, a2 = divmod(int(w),k)
    b1, b2 = divmod(int(h),k)
    if (a1+b1) % 2 == 1:
        if c == "B":
            c = "W"
        else:
            c = "B"

    if c == "B":
        b_board[b2][a2] += 1
    else:
        w_board[b2][a2] += 1
    
b_board_3 = cumsum_2d(b_board,k,k)
w_board_3 = cumsum_2d(w_board,k,k)


total_b, total_w = b_board_3[k][k], w_board_3[k][k]
ans = 0

for i in range(1,k+1):
    for j in range(1,k+1):
        b1 = b_board_3[i][j] - b_board_3[0][j] - b_board_3[i][0]
        b2 = total_b - b_board_3[i][k] - b_board_3[k][j] + b_board_3[i][j]
        w1 = w_board_3[i][j] - w_board_3[0][j] - w_board_3[i][0]
        w2 = total_w - w_board_3[i][k] - w_board_3[k][j] + w_board_3[i][j]
        ans = max(b1+b2+(total_w-w1-w2),w1+w2+(total_b-b1-b2),ans)

print(ans)

Submission status: Accepted

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

def cumsum_2d(inlist,h,w):
    outlist = [ [ inlist[i-1][j-1] if i != 0 and j != 0 else 0 for i in range(k+1) ] for j in range(k+1) ]
    for i in range(1,h+1):
        tmp = 0
        for j in range(1,w+1):
            tmp += outlist[i][j]
            outlist[i][j] = tmp
    for i in range(1,w+1):
        tmp = 0
        for j in range(1,h+1):
            tmp += outlist[j][i]
            outlist[j][i] = tmp

    return outlist
    
n, k = [ int(v) for v in input().split() ]
hope = [ [ a for a in input().split() ] for i in range(n) ]

b_board = [ [ 0 for i in range(k)] for j in range(k) ]
w_board = [ [ 0 for i in range(k)] for j in range(k) ]



for h, w, c in hope:
    a1, a2 = divmod(int(w),k)
    b1, b2 = divmod(int(h),k)
    if (a1+b1) % 2 == 1:
        if c == "B":
            c = "W"
        else:
            c = "B"

    if c == "B":
        b_board[int(h)%k][int(w)%k] += 1
    else:
        w_board[int(h)%k][int(w)%k] += 1
    
b_board_3 = cumsum_2d(b_board,k,k)
w_board_3 = cumsum_2d(w_board,k,k)


total_b, total_w = b_board_3[k][k], w_board_3[k][k]
ans = 0

for i in range(1,k+1):
    for j in range(1,k+1):
        b1 = b_board_3[i][j] - b_board_3[0][j] - b_board_3[i][0]
        b2 = total_b - b_board_3[i][k] - b_board_3[k][j] + b_board_3[i][j]
        w1 = w_board_3[i][j] - w_board_3[0][j] - w_board_3[i][0]
        w2 = total_w - w_board_3[i][k] - w_board_3[k][j] + w_board_3[i][j]
        ans = max(b1+b2+(total_w-w1-w2),w1+w2+(total_b-b1-b2),ans)

print(ans)

Submission status: Accepted

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), (0, 2)):
        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: Accepted

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

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

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


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

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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
n, k = map(int, input().split())
list_subj = []
for i in range(n):
  x, y, c = input().split()
  if c == "W":
    list_subj.append([int(x) % (2*k), int(y) % (2*k)])
  else:
    list_subj.append([(int(x) + k) % (2*k), int(y) % (2*k)])

imos_field = [[0] * (2*k+1) for _ in range(2*k+1)]
for x, y in list_subj:
  for place in (0, k):
    adj_y = (y + place) % (2 * k)
    if adj_y >= k - 1:
      imos_y = [(adj_y-k+1, adj_y+1)]
    else:
      imos_y = [(0, adj_y+1), (adj_y+k+1, 2*k)]
    adj_x = (x + place) % (2 * k)
    if adj_x >= k - 1:
      imos_x = [(adj_x-k+1, adj_x+1)]
    else:
      imos_x = [(0, adj_x+1), (adj_x+k+1, 2*k)]
    for bottom, top in imos_y:
      for left, right in imos_x:
        imos_field[bottom][left] += 1
        imos_field[top][left] -= 1
        imos_field[bottom][right] -= 1
        imos_field[top][right] += 1

result = np.cumsum(imos_field, axis=1)
result = np.cumsum(result, axis=0)
result = int(np.max(result))
print(result)

Submission status: Accepted

Solution code:
import numpy as np
import sys

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

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

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

for x,y,c in XYC:
    i = (int(x) if c=="W" else int(x)+K) % (K*2)
    j = int(y) % (K*2)
    i0 = i%K
    j0 = j%K
    if (i<K and j<K) or (i>=K and j>=K):
        sum2d(0,0,i0,j0) # 左上
        sum2d(i0+K,0,K*2,j0) # 右上
        sum2d(i0,j0,i0+K,j0+K) # 真ん中
        sum2d(0,j0+K,i0,K*2) # 左下
        sum2d(i0+K,j0+K,K*2,K*2) # 右下
    else:
        sum2d(i0,0,i0+K,j0) # 上
        sum2d(0,j0,i0,j0+K) # 左
        sum2d(i0+K,j0,K*2,j0+K) # 右
        sum2d(i0,j0+K,i0+K,K*2) # 下

# 2次元累積和
AA = np.array(A)
for i in range(K*2):
    AA[i+1, :] += AA[i, :]
for j in range(K*2):
    AA[:, j+1] += AA[:, j]

print(AA.max())

Submission status: Accepted

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

grid = [[0 for _ in range(2*K)] for _ in range(2*K)]

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

for i in range(2*K):
    for j in range(2*K):
        if i == 0:
            if j != 0:
                grid[i][j] += grid[i][j-1]
        else:
            if j == 0:
                grid[i][j] += grid[i-1][j]
            else:
                grid[i][j] += (grid[i-1][j] + grid[i][j-1] - grid[i-1][j-1])
        

ans = 0
M = grid[2*K-1][2*K-1]
for i in range(K):
    for j in range(K):
        temp = 0
        c = 0
        temp += (M-grid[i+K-1][-1]-grid[-1][j+K-1]+grid[i+K-1][j+K-1])
        temp += grid[i+K-1][j+K-1]
        if i > 0 and j == 0:
            temp += (grid[i-1][-1]-2*grid[i-1][j+K-1])
        if i == 0 and j > 0:
            temp += (grid[-1][j-1]-2*grid[i+K-1][j-1])
        if i > 0 and j > 0:
            temp += (grid[i-1][-1]-2*grid[i-1][j+K-1])
            temp += (grid[-1][j-1]-2*grid[i+K-1][j-1])
            temp += 2*grid[i-1][j-1]
        ans = max(ans, temp, M-temp)
        
print(ans)