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:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

# A:product
'''
data = input("")
data = data.split(" ")
a = int(data[0])
b = int(data[1])

if (a*b)%2 == 1: print("Odd")
else: print("Even")
'''

# B:1 21
'''
data = input()
data = int(data.replace(" ",""))
if data%(data**(1/2)) == 0: print("Yes")
else: print("No")
'''

# C:Traveling
'''
n = int(input(""))
data = [0]*n
t = [0]*n
x = [0]*n
y = [0]*n
flag = 0

for i in range(n):
    data[i] = input("")
    t[i] = int(data[i].split(" ")[0])
    x[i] = int(data[i].split(" ")[1])
    y[i] = int(data[i].split(" ")[2])

for i in range(n):
    if i == 0:
        if x[i]+y[i] > t[i] or (x[i]+y[i]-t[i])%2 != 0:
            print("No")
            flag = 1
            break
    else:
        if abs(x[i]-x[i-1])+abs(y[i]-y[i-1]) > t[i] or (x[i]+y[i]-t[i])%2 != 0:
            print("No")
            flag = 1
            break
if flag == 0:print("Yes")
'''

# D:Checker
def check(y,x,k):
    l = max(0,min(m,x))
    r = max(0,min(m,x+k))
    d = max(0,min(m,y))
    u = max(0,min(m,y+k))
    f[d][l] += 1
    f[d][r] -= 1
    f[u][l] -= 1
    f[u][r] += 1
n,k = LI()
m = k*2
f = [[0]*(m+1) for i in range(m+1)]
for i in range(n):
    x,y,c = input().split()
    x = int(x)%m
    y = int(y)%m
    if c == "W":
        y += k
        y %= m
    check(y-m+1,x-m+1,k)
    check(y+1,x-m+1,k)
    check(y-k+1,x-k+1,k)
    check(y+k+1,x-k+1,k)
    check(y-m+1,x+1,k)
    check(y+1,x+1,k)
    check(y-k+1,x+k+1,k)
    check(y+k+1,x+k+1,k)

for y in range(m+1):
    for x in range(m):
        f[y][x+1] += f[y][x]

for y in range(m):
    for x in range(m+1):
        f[y+1][x] += f[y][x]

ans = 0
for i in f:
    ans = max(ans,max(i))
print(ans)

Submission status: Accepted

Solution code:
#(6,6)周期
#36種の希望

import numpy as np
N,K = map(int,input().split())
KK = 2*K
hope = np.zeros((KK,KK),dtype=np.int32)

for _ in range(N):
  x,y,c  = input().split()
  x = int(x)
  y = int(y)
  if c == 'B':
    x -= K
  hope[x%KK,y%KK] += 1
# (x,y)を希望された場合、[x,x+K), [y,y+K)に終点があるべき
# 区間の重なってる枚数を集計。1,0,0,-1, cumsum
A = np.zeros((KK+K,KK+K),dtype=np.int32)
A[:-K,:-K] = hope[:]
A[K:,:-K] += -hope[:]
A[:-K,K:] += -hope[:]
A[K:,K:] += hope[:]
A = A.cumsum(axis = 0).cumsum(axis = 1)

# 実質同じ場所をまとめる
B = A[:,:KK]
B[:,:K] += A[:,KK:] #(3K,2K)
A = B[:KK,:]
A[:K,:] += B[KK:,:] #(2K,2K)
B = A[:K,:] #(K,2K)
B[:,:K] += A[K:,K:]
B[:,K:] += A[K:,:K]

answer = B.max()
print(answer)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
B=[[0]*(2*K) for i in range(2*K)]
W=[[0]*(2*K) for i in range(2*K)]
w=0
for i in range(N):
    x,y,c=map(str,input().split())
    x=int(x)
    y=int(y)
    if c=="B":
        B[y%(2*K)][x%(2*K)]+=1
    else:
        w+=1
        W[y%(2*K)][x%(2*K)]+=1
sumb=[[0]*(2*K+1) for i in range(2*K+1)]
sumw=[[0]*(2*K+1) for i in range(2*K+1)]
for i in range(2*K):
    for j in range(2*K):
        sumb[i+1][j+1]=sumb[i][j+1]+sumb[i+1][j]-sumb[i][j]+B[i][j]
        sumw[i+1][j+1]=sumw[i][j+1]+sumw[i+1][j]-sumw[i][j]+W[i][j]


ans=0
for i in range(K):
    for j in range(K):
        for _ in range(2):
            s=0
            s+=sumb[i][j]-sumb[i][0]-sumb[0][j]+sumb[0][0]#
            s+=sumb[i+K][j+K]-sumb[i][j+K]-sumb[i+K][j]+sumb[i][j]
            s+=sumb[i][2*K]-sumb[0][2*K]-sumb[i][j+K]+sumb[0][j+K]#
            s+=sumb[2*K][j]-sumb[i+K][j]-sumb[2*K][0]+sumb[i+K][0]#
            s+=sumb[2*K][2*K]-sumb[i+K][2*K]-sumb[2*K][j+K]+sumb[i+K][j+K]#

            s+=sumw[i][j+K]-sumw[0][j+K]-sumw[i][j]+sumw[0][j]#
            s+=sumw[i+K][j]-sumw[i][j]-sumw[i+K][0]+sumw[i][0]#
            s+=sumw[2*K][j+K]-sumw[i+K][j+K]-sumw[2*K][j]+sumw[i+K][j]#
            s+=sumw[i+K][2*K]-sumw[i+K][j+K]-sumw[i][2*K]+sumw[i][j+K]#

            ans=max(ans,s)
            sumb,sumw=sumw,sumb

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
B=[[0]*(2*K) for i in range(2*K)]
W=[[0]*(2*K) for i in range(2*K)]
sumb=[[0]*(2*K+1) for i in range(2*K+1)]
sumw=[[0]*(2*K+1) for i in range(2*K+1)]
for i in range(N):
    x,y,c=map(str,input().split())
    x=int(x)
    y=int(y)
    if c=="B":
        B[y%(2*K)][x%(2*K)]=+1
        sumb[y%(2*K)+1][x%(2*K)+1]+=1
    else:
        W[y%(2*K)][x%(2*K)]=+1
        sumw[y%(2*K)+1][x%(2*K)+1]+=1
for i in range(2*K):
    for j in range(2*K):
        sumb[i+1][j+1]=sumb[i][j+1]+sumb[i+1][j]-sumb[i][j]+sumb[i+1][j+1]
        sumw[i+1][j+1]=sumw[i][j+1]+sumw[i+1][j]-sumw[i][j]+sumw[i+1][j+1]

ans=0
for i in range(K):
    for j in range(K):
        for _ in range(2):
            s=0
            s+=sumb[i][j]-sumb[i][0]-sumb[0][j]+sumb[0][0]#
            s+=sumb[i+K][j+K]-sumb[i][j+K]-sumb[i+K][j]+sumb[i][j]
            s+=sumb[i][2*K]-sumb[0][2*K]-sumb[i][j+K]+sumb[0][j+K]#
            s+=sumb[2*K][j]-sumb[i+K][j]-sumb[2*K][0]+sumb[i+K][0]#
            s+=sumb[2*K][2*K]-sumb[i+K][2*K]-sumb[2*K][j+K]+sumb[i+K][j+K]#

            s+=sumw[i][j+K]-sumw[0][j+K]-sumw[i][j]+sumw[0][j]#
            s+=sumw[i+K][j]-sumw[i][j]-sumw[i+K][0]+sumw[i][0]#
            s+=sumw[2*K][j+K]-sumw[i+K][j+K]-sumw[2*K][j]+sumw[i+K][j]#
            s+=sumw[i+K][2*K]-sumw[i+K][j+K]-sumw[i][2*K]+sumw[i][j+K]#

            ans=max(ans,s)
            sumb,sumw=sumw,sumb

print(ans)

Submission status: Accepted

Solution code:
N,K = [ int(it) for it in input().split() ]
K2 = 2*K
li = [ (lambda x,y,z:[int(x)%K2,int(y)%K2,0 if z=="W" else 1] )(*(input().split())) for i in range(N)]

bm = [[0]*(K2+1) for i in range(K2+1)]
wm = [[0]*(K2+1) for i in range(K2+1)]
for x,y,z in li:
  if (z==0):
    wm[x+1][y+1] += 1
  else:
    bm[x+1][y+1] += 1

for i in range(1,2*K+1):
  for j in range(1,2*K+1):
    bm[i][j]=bm[i-1][j]+bm[i][j-1]-bm[i-1][j-1]+bm[i][j]
    wm[i][j]=wm[i-1][j]+wm[i][j-1]-wm[i-1][j-1]+wm[i][j]
sumb=bm
sumw=wm

ans=0
for i in range(K):
    for j in range(K):
        for _ in range(2):
            s=0
            s+=sumb[i][j]-sumb[i][0]-sumb[0][j]+sumb[0][0]#
            s+=sumb[i+K][j+K]-sumb[i][j+K]-sumb[i+K][j]+sumb[i][j]
            s+=sumb[i][2*K]-sumb[0][2*K]-sumb[i][j+K]+sumb[0][j+K]#
            s+=sumb[2*K][j]-sumb[i+K][j]-sumb[2*K][0]+sumb[i+K][0]#
            s+=sumb[2*K][2*K]-sumb[i+K][2*K]-sumb[2*K][j+K]+sumb[i+K][j+K]#

            s+=sumw[i][j+K]-sumw[0][j+K]-sumw[i][j]+sumw[0][j]#
            s+=sumw[i+K][j]-sumw[i][j]-sumw[i+K][0]+sumw[i][0]#
            s+=sumw[2*K][j+K]-sumw[i+K][j+K]-sumw[2*K][j]+sumw[i+K][j]#
            s+=sumw[i+K][2*K]-sumw[i+K][j+K]-sumw[i][2*K]+sumw[i][j+K]#

            ans=max(ans,s)
            sumb,sumw=sumw,sumb

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
Demand = []
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W':
        y += K
    Demand.append([x % (2 * K), y % (2 * K)])


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        # 問題によってイメージしやすいよう書き換えてください
        for x, y in points:
            self.G[x][y] += 1

    def load_imos(self, points):
        # pointsは[[左上h, 左上w, 右下h, 右下w], ...]であること
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  # 左上
            if j2 + 1 < self.W:  # 右上
                self.G[i1][j2 + 1] -= 1
            if i2 + 1 < self.H:
                self.G[i2 + 1][j1] -= 1  # 左下
            if j2 + 1 < self.W and i2 + 1 < self.H:  # 右下
                self.G[i2 + 1][j2 + 1] += 1

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x - 1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y - 1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1 - 1][j2] - self.G[i2][j1 - 1] + self.G[i1 - 1][j1 - 1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1 - 1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


R2D = Ruisekiwa2D(2 * K, 2 * K)
R2D.load(Demand)
R2D.calc()


ans = 0
for x in range(K):
    for y in range(K):
        cnt = 0
        cnt += R2D.get(x, y, x + K - 1, y + K - 1)  # 真ん中
        cnt += R2D.get(0, 0, x - 1, y - 1)  # 左上
        cnt += R2D.get(x + K, 0, 2 * K - 1, y - 1)  # 右上
        cnt += R2D.get(0, y + K, x - 1, 2 * K - 1)  # 左下
        cnt += R2D.get(x + K, y + K, 2 * K - 1, 2 * K - 1)  # 右下
        ans = max(ans, cnt, N - cnt)

print(ans)

Submission status: Accepted

Solution code:
#(6,6)周期
#36種の希望

import numpy as np
N,K = map(int,input().split())
KK = 2*K
hope = np.zeros((KK,KK),dtype=np.int32)

XYC = [input().split() for _ in range(N)]

for x,y,c in XYC:
  x = int(x)
  y = int(y)
  if c == 'B':
    x -= K
  x %= KK
  y %= KK
  hope[x,y] += 1
# (x,y)を希望された場合、[x,x+K), [y,y+K)に終点があるべき
# 区間の重なってる枚数を集計。1,0,0,-1, cumsum
A = np.zeros((KK+K,KK+K),dtype=np.int32)
A[:-K,:-K] = hope[:]
A[K:,:-K] += -hope[:]
A[:-K,K:] += -hope[:]
A[K:,K:] += hope[:]
A = A.cumsum(axis = 0).cumsum(axis = 1)

# 実質同じ場所をまとめる
B = A[:,:KK]
B[:,:K] += A[:,KK:] #(3K,2K)
A = B[:KK,:]
A[:K,:] += B[KK:,:] #(2K,2K)
B = A[:K,:] #(K,2K)
B[:,:K] += A[K:,K:]
B[:,K:] += A[K:,:K]

answer = B.max()
print(answer)

Submission status: Accepted

Solution code:
N,K = [ int(it) for it in input().split() ]
K2 = 2*K
li = [ (lambda x,y,z:[int(x)%K2,int(y)%K2,0 if z=="W" else 1] )(*(input().split())) for i in range(N)]

bm = [[0]*(K2+1) for i in range(K2+1)]
wm = [[0]*(K2+1) for i in range(K2+1)]
for x,y,z in li:
  if (z==0):
    wm[x+1][y+1] += 1
  else:
    bm[x+1][y+1] += 1

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

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

Submission status: Accepted

Solution code:
import sys

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

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

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


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

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

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


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

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

for i in range(MOD - 1):
    for j in range(MOD):
        grid[i + 1][j] += grid[i][j]
for i in range(MOD - 1):
    for j in range(MOD):
        grid[j][i + 1] += grid[j][i]
ans = 0
for i in range(MOD):
    ans = max(ans, *grid[i])
print(ans)

Submission status: Accepted

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

def calc(x, y):
    return accmap[x][y] \
        + (accmap[x+K][K] - accmap[x][K] - accmap[x+K][y] + accmap[x][y]) \
        + (accmap[K2][y] - accmap[x+K][y])

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

res = 0
for i in range(K):
    for j in range(K):
        # print(i,j)
        cand = calc(i, j)
        # print("i{} j{} res:{}".format(i,j,cand))
        res = max(res, cand, N-cand)

print(res)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
Demand = []
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W':
        x += K
    x, y = x % (2 * K), y % (2 * K)
    Demand.append([x, y])


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        # 問題によってイメージしやすいよう書き換えてください
        for x, y in points:
            self.G[x][y] += 1

    def load_imos(self, points):
        # pointsは[[左上h, 左上w, 右下h, 右下w], ...]であること
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  # 左上
            if j2 + 1 < self.W:  # 右上
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  # 左下
            if j2 + 1 < self.W and i2 + 1 < self.H:  # 右下
                self.G[i2+1][j2+1] += 1

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


R2D = Ruisekiwa2D(2 * K, 2 * K)
R2D.load(Demand)
R2D.calc()

ans = 0
for x in range(K):
    for y in range(K):
        fulfill = 0
        fulfill += R2D.get(0, 0, x - 1, y - 1)  # 左上
        fulfill += R2D.get(x + K, 0, 2 * K - 1, y - 1)  # 右上
        fulfill += R2D.get(x, y, x + K - 1, y + K - 1)  # 真ん中
        fulfill += R2D.get(0, y + K, x - 1, 2 * K - 1)  # 左下
        fulfill += R2D.get(x + K, y + K, 2 * K - 1, 2 * K - 1)  # 右下

        ans = max(ans, fulfill, N - fulfill)

print(ans)

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split(" ")]
dm = [[0 for j in range(0, 2 * k)] for i in range(0, 2 * k)]
s = [[0 for j in range(0, 2 * k + 1)] for  i in range(0, 2 * k + 1)]

for i in range(0, n):
    x, y, c = input().split(" ")
    x = int(x) % (2 * k)
    if c == "W":
        y = int(y) % (2 * k)
    else:
        y = (int(y) + k) % (2 * k)
    dm[x][y] += 1

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

def srect(i, j, r, l):
    global s
    return s[r][l] - s[r][j] - s[i][l] + s[i][j]

m = 0
for i in range(0, k):
    for j in range(0, k):
        aw = srect(0, j, i, j + k) + srect(i, 0, i + k, j) + srect(i, j + k, i + k, 2 * k) + srect(i + k, j, 2 * k, j + k)
        raw = n - aw
        if m < max(aw, raw):
            m = max(aw, raw)
print(m)

Submission status: Accepted

Solution code:
import numpy as np


def solve(string):
    n, k, *xyc = string.split()
    k = int(k)
    l = 2 * int(k)
    xy = [(int(x) % l, int(y) % l) if c == "W" else (int(x) % l, (int(y) + k) % l)
          for x, y, c in zip(xyc[::3], xyc[1::3], xyc[2::3])]
    ans = [[0 for j in range(l + 0)] for i in range(l + 0)]
    for _x, _y in xy:
        if (_x - k + 0.5) * (_y - k + 0.5) > 0:
            lt = 2
            lte = 1
            ans[0][0] += 1
        else:
            lt = -2
            lte = -1
        _x %= k
        _y %= k
        ans[_x][_y] += lt
        ans[_x + k][_y] -= lt
        ans[_x][_y + k] -= lt
        ans[_x + k][_y + k] += lt
        ans[_x + k][0] += lte
        ans[0][_y + k] += lte
        ans[_x][0] -= lte
        ans[0][_y] -= lte
    return str(np.asarray(ans).cumsum(axis=1).cumsum(axis=0).max())


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
import numpy as np


def solve(string):
    n, k, *xyc = string.split()
    k = int(k)
    l = 2 * int(k)
    xy = [(int(x) % l, int(y) % l) if c == "W" else (int(x) % l, (int(y) + k) % l)
          for x, y, c in zip(xyc[::3], xyc[1::3], xyc[2::3])]
    ans = [[0 for j in range(l + 0)] for i in range(l + 0)]
    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
    return str(np.asarray(ans).cumsum(axis=1).cumsum(axis=0).max())


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
import numpy as np
import sys

N, K = map(int, input().split())
K2 = K * 2
Mij = [[0 for _ in range(K2 + 1)] for _ in range(K2 + 1)]

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

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

# 累積和
Mij = np.array(Mij)
for x in range(K2):
    Mij[:, x + 1] += Mij[:, x]
for y in range(K2):
    Mij[y + 1, :] += Mij[y, :]
print(Mij.max())

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
K2 = 2 * K
Mij = [[0 for _ in range(K2 + 1)] for _ in range(K2 + 1)]


def imos(x1, y1, x2, y2):
    Mij[y1][x1] += 1
    Mij[y2][x2] += 1
    Mij[y2][x1] -= 1
    Mij[y1][x2] -= 1

for _ in range(N):
    ls = input().split()
    x = int(ls[0]) % K2
    y = int(ls[1]) % K2
    if ls[2] == "B":
        y = (y + K) % K2
    x_ = x % K
    y_ = y % K

    if (x < K and y < K) or (K <= x and K <= y):
        imos(0, 0, x_ + 1, y_ + 1)
        imos(x_ + K + 1, 0, K2, y_ + 1)
        imos(0, y_ + K + 1, x_ + 1, K2)
        imos(x_ + K + 1, y_ + K + 1, K2, K2)
        imos(x_ + 1, y_ + 1, x_ + K + 1, y_ + K + 1)
    else:
        imos(x_ + 1, 0, x_ + K + 1, y_ + 1)
        imos(x_ + 1, y_ + K + 1, x_ + K + 1, K2)
        imos(0, y_ + 1, x_ + 1, y_ + K + 1)
        imos(x_ + K + 1, y_ + 1, K2, y_ + K + 1)

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

print(Mij.max())

Submission status: Accepted

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18
 
N,K=rl()
 
W = [[0 for _ in range(K+3)] for _ in range(K+3)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[x+1][y+1] -= 2
        W[0][K+1] -= 1
        W[x+1][K+1] += 1
        W[x+1][0] += 1
        W[K+1][0] -= 1
        W[K+1][y+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[K+1][y+1] -= 1
        W[x+1][K+1] -= 1
        W[K+1][K+1] += 1
 
for x in range(0,K+2):
    for y in range(0,K+2):
        W[x][y] += W[x][y-1]
for y in range(0,K+2):
    for x in range(0,K+2):
        W[x][y] += W[x-1][y]
 
ans = 0
for x in range(K+1):
    for y in range(K+1):
        res = W[x][y]
        ans = max(ans,res,N-res)
 
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
favor = [tuple(input().split()) for _ in range(n)]
square = [[0 for _ in range(k)] for _ in range(k)]
initscore = 0
for xc, yc, c in favor:
    x = int(xc)
    y = int(yc)
    x %= 2*k
    y %= 2*k
    if (x in range(k) and y in range(k)) or (x in range(k, 2*k) and y in range(k, 2*k)):
        if c == 'B':
            square[x%k][y%k] += 1
        else:
            square[x%k][y%k] -= 1
            initscore += 1
    else:
        if c == 'B':
            square[x%k][y%k] -= 1
            initscore += 1
        else:
            square[x%k][y%k] += 1
cum = [[0 for _ in range(k+1)] for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + square[i][j]
maxscore = 0
for i in range(k):
    for j in range(k):
        score = cum[i][k] + cum[k][j] - 2*cum[i][j]
        maxscore = max(maxscore, max(cum[k][k] - score, score))
print(maxscore + initscore)

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
mod = 2*K
field = [[0]*(2*K+1) for _ in range(2*K+1)]

def gen_pattern(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 = input().split()
    x, y = int(x), int(y)
    if c == 'W':
        y += K
    x %= mod
    y %= mod
    for tmp in [0, K]:
        for l, r in gen_pattern((x+tmp) % mod):
            for b, t in gen_pattern((y+tmp) % mod):
                field[l][b] += 1
                field[l][t] -= 1
                field[r][b] -= 1
                field[r][t] += 1
print(np.max(np.cumsum(np.cumsum(field, axis=0), axis=1)))

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
mod = 2*K
field = [[0]*(2*K+1) for _ in range(2*K+1)]

def gen_pattern(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 = input().split()
    x, y = int(x), int(y)
    if c == 'W':
        y += K
    x %= mod
    y %= mod
    for tmp in [0, K]:
        for l, r in gen_pattern((x+tmp) % mod):
            for b, t in gen_pattern((y+tmp) % mod):
                field[l][b] += 1
                field[l][t] -= 1
                field[r][b] -= 1
                field[r][t] += 1

print(np.max(np.cumsum(np.cumsum(field, axis=0), axis=1)))

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
mod = 2*K
#field = np.zeros((2*K+1, 2*K+1), dtype='i')
field = [[0]*(2*K+1) for _ in range(2*K+1)]

def gen_pattern(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 = input().split()
    x, y = int(x), int(y)
    if c == 'W':
        y += K
    x %= mod
    y %= mod
    for tmp in [0, K]:
        for l, r in gen_pattern((x+tmp) % mod):
            for b, t in gen_pattern((y+tmp) % mod):
                field[l][b] += 1
                field[l][t] -= 1
                field[r][b] -= 1
                field[r][t] += 1

field = np.array(field)
print(field.cumsum(axis=0).cumsum(axis=1).max())

Submission status: Accepted

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

def main():
    na = list(map(int, input().split()))
    N = na[0]
    K = na[1]
    x = []
    y = []
    c = []
    for i in range(N):
        sa = input().split()
        x.append(int(sa[0]))
        y.append(int(sa[1]))
        c.append(True if sa[2] == 'W' else False)

    hopes = [[0 for j in range(K)] for i in range(K)]
    ysum = [[0 for j in range(K * 2)] for i in range(K)]

    score = 0
    for i in range(N):
        xmod = x[i] % K
        ymod = y[i] % K
        f = (int(x[i] / K) + int(y[i] / K)) % 2 == 1
        c[i] ^= f
        if c[i]:
            score += 1
        h = -1 if c[i] else 1
        hopes[xmod][ymod] += h

    for i in range(K):
        s = 0
        for j in range(K):
            s += hopes[i][j]
            ysum[i][j] = s
        for j in range(K):
            s -= hopes[i][j]
            ysum[i][K + j] = s

    smax = 0
    for j in range(K):
        s = 0
        for i in range(K):
            s += ysum[i][K + j]
        for i in range(K):
            s += (ysum[i][j] - ysum[i][K + j])
            smax = max(smax, s)
        for i in range(K):
            s -= (ysum[i][j] - ysum[i][K + j])
            smax = max(smax, s)

    print(score + smax)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

"""
参考：https://pitsbuffersolution.com/compro/atcoder/arc089d.php
　　　http://tutuz.hateblo.jp/entry/2018/06/20/212752
　　　https://paiza.hatenablog.com/entry/2014/05/28/%E3%82%82%E3%81%97%E5%A5%B3%E5%AD%90%E5%A4%A7%E7%94%9F%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E3%81%AB%E3%80%8E%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%80%8F%E3%82%92%E5%9B%B3
　　　http://www.learning-algorithms.com/entry/2018/01/31/144519
　　　https://img.atcoder.jp/arc089/editorial.pdf
・2次元累積和
・0-indexedのまま行くか1-indexedにするか人によって色々で、
　それぞれに考慮する点があると思った。
・今度は0-indexedでループ減らした版。
"""

import sys
def input(): return sys.stdin.readline().strip()

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

# ここは循環するK*2まで作る
B = [[0] * (K*2) for i in range(K*2)]
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    # 白に塗る条件はxかyにKずらして黒の条件にする(これで2色考えなくていい)
    if c == 'W':
        y += K
    # 循環するのでmod K*2でやる
    B[x%(K*2)][y%(K*2)] += 1

# ここはK*2の正方形を右下まで動かすので、K*4まで作っておく
sm = [[0] * (K*4) for i in range(K*4)]
# 2次元累積和を取る
for i in range(K*4):
    for j in range(K*4):
        # K*2からはみ出る範囲も正しく累積和を出すため、K*2までの値を循環させる
        # 0-indexedなのでここはシンプル
        sm[i][j] = B[i%(K*2)][j%(K*2)]
        # 縦横の累積和を同時に集めていく
        # 0-indexedなので、i, jがマイナスになる場合を考慮
        if j > 0:
            sm[i][j] += sm[i][j-1]
        if i > 0:
            sm[i][j] += sm[i-1][j]
        if i > 0 and j > 0:
            sm[i][j] -= sm[i-1][j-1]

# 2次元累積和に必要な4点の加減を行う
def get_sum(x1, y1, x2, y2, sm):
    # 右下は必ず足す
    res = sm[x2][y2]
    # 左下を引く
    if x1 > 0:
        res -= sm[x1-1][y2]
    # 右上を引く
    if y1 > 0:
        res -= sm[x2][y1-1]
    # 左上を足す
    if x1 > 0 and y1 > 0:
        res += sm[x1-1][y1-1]
    return res

ans = 0
for i in range(K*2):
    for j in range(K*2):
        # 1つ目の正方形
        tmp = get_sum(i, j, i+K-1, j+K-1, sm)
        # 2つ目の正方形
        tmp += get_sum(i+K, j+K, i+K*2-1, j+K*2-1, sm)
        ans = max(tmp, ans)
print(ans)

Submission status: Accepted

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

"""
参考：https://pitsbuffersolution.com/compro/atcoder/arc089d.php
　　　http://tutuz.hateblo.jp/entry/2018/06/20/212752
　　　https://paiza.hatenablog.com/entry/2014/05/28/%E3%82%82%E3%81%97%E5%A5%B3%E5%AD%90%E5%A4%A7%E7%94%9F%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E3%81%AB%E3%80%8E%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%80%8F%E3%82%92%E5%9B%B3
　　　http://www.learning-algorithms.com/entry/2018/01/31/144519
　　　https://img.atcoder.jp/arc089/editorial.pdf
・2次元累積和
・0-indexedのまま行くか1-indexedにするか人によって色々で、
　それぞれに考慮する点があると思った。
・練習のために今度は0-indexedでやってみる。
"""

import sys
def input(): return sys.stdin.readline().strip()

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

# K*2の正方形を右下まで動かすので、K*4まで作っておく
B = [[0] * (K*4) for i in range(K*4)]
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    # 白に塗る条件はxかyにKずらして黒の条件にする(これで2色考えなくていい)
    if c == 'W':
        y += K
    # 循環するのでmod K*2でやる
    B[x%(K*2)][y%(K*2)] += 1

for i in range(K*4):
    for j in range(K*4):
        # K*2からはみ出る範囲も正しく累積和を出すため、K*2までの値を循環させる
        # 0-indexedなのでここはシンプル
        B[i][j] = B[i%(K*2)][j%(K*2)]

# 2次元累積和を取る
# 0-indexedなので、i, jがマイナスになる場合を考慮
for i in range(K*4):
    for j in range(K*4):
        if j > 0:
            B[i][j] += B[i][j-1]
for i in range(K*4):
    for j in range(K*4):
        if i > 0:
            B[i][j] += B[i-1][j]

# 2次元累積和に必要な4点の加減を行う
def get_sum(x1, y1, x2, y2, sm):
    # 右下は必ず足す
    res = sm[x2][y2]
    # 左下を引く
    if x1 > 0:
        res -= sm[x1-1][y2]
    # 右上を引く
    if y1 > 0:
        res -= sm[x2][y1-1]
    # 左上を足す
    if x1 > 0 and y1 > 0:
        res += sm[x1-1][y1-1]
    return res

ans = 0
for i in range(K*2):
    for j in range(K*2):
        # 1つ目の正方形
        tmp = get_sum(i, j, i+K-1, j+K-1, B)
        # 2つ目の正方形
        tmp += get_sum(i+K, j+K, i+K*2-1, j+K*2-1, B)
        ans = max(tmp, ans)
print(ans)