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
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(str, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    ans = ['Odd', 'Even']
    print(ans[(a*b)%2-1])
    return

#B
def B():
    a, b = map(str,input().split())
    a = a + b
    if math.sqrt(int(a)).is_integer():
        print("Yes")
    else:
        print("No")
    return

#C
def C():
    n = II()
    pre = (0, 0, 0)
    for _ in range(n):
        t,x,y = LI()
        dist = abs(pre[0] - x) + abs(pre[1] - y)
        if dist <= t - pre[2] and dist % 2 == (t - pre[2]) % 2:
            pre = (x, y, t)
            continue
        print("No")
        return
    print("Yes")
    return

# D
# 解説AC
# prd_xxxさんのを参考にしたけど理解できてないので絶対に理解すること
# https://atcoder.jp/contests/abc086/submissions/3454297
# PS: 2019/10/12
# なんとなく理解
# まず白の情報は市松模様的にk右に行ったところが黒になるという情報と同じ
# 更に座標を2*kの剰余で考えても問題ない
# あとは2次元累積和をとって市松模様の一番左下に当たる白の領域の右上が
# どの位置にあるかはk*k通りあるのでそれを試してその時の模様における
# 黒配置がどの数ただしくなるか調べる
def D():
    n, k = LI()
    dp = [[0] * (2 * k + 1) for i in range(2 * k + 1)]
    for _ in range(n):
        x, y, c = LS()
        x, y = int(x), int(y)
        if c == "W":
            dp[y % (2 * k) + 1][(x + k) % (2 * k) + 1] += 1
        else:
            dp[y % (2 * k) + 1][x % (2 * k) + 1] += 1
    for y in range(2 * k + 1):
        for x in range(1, 2 * k + 1):
            dp[y][x] += dp[y][x - 1]
    for y in range(1, 2 * k + 1):
        for x in range(2 * k + 1):
            dp[y][x] += dp[y - 1][x]
    
    def count(l, r, d, u):
        return dp[d][l] - dp[d][r] - dp[u][l] + dp[u][r]
    
    ans = 0
    for i in range(k):
        for j in range(k):
            tmp = count(j, j + k, i, i + k) + count(0, j, 0, i) + count(j + k, 2 * k, 0, i) + \
                 count(0, j, i + k, 2 * k) + count(j + k, 2 * k, i + k, 2 * k)
            ans = max(ans, tmp, n - tmp)
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
w=[[0]*(k+1) for _ in range(k+1)]
b=[[0]*(k+1) for _ in range(k+1)]
for i in range(n):
    if ((int(l[i][0])//k+int(l[i][1])//k)%2==0)^(l[i][2]=='W'):
        b[int(l[i][0])%k][int(l[i][1])%k]+=1
    else:
        w[int(l[i][0])%k][int(l[i][1])%k]+=1

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

ans=0
for i in range(k):
    for j in range(k):
        ans=max(ans,b[k-1][k-1]-b[i][k-1]-b[k-1][j]+2*b[i][j]+w[i][k-1]+w[k-1][j]-2*w[i][j])
        ans=max(ans,w[k-1][k-1]-w[i][k-1]-w[k-1][j]+2*w[i][j]+b[i][k-1]+b[k-1][j]-2*b[i][j])
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
w=[[0]*(k+1) for _ in range(k+1)]
b=[[0]*(k+1) for _ in range(k+1)]
for i in range(n):
    if ((int(l[i][0])//k+int(l[i][1])//k)%2==0)^(l[i][2]=='W'):
        b[int(l[i][0])%k][int(l[i][1])%k]+=1
    else:
        w[int(l[i][0])%k][int(l[i][1])%k]+=1

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

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
w=[[0]*(k+1) for _ in range(k+1)]
b=[[0]*(k+1) for _ in range(k+1)]
for i in range(n):
    if ((int(l[i][0])//k+int(l[i][1])//k)%2==0)^(l[i][2]=='W'):
        b[int(l[i][0])%k][int(l[i][1])%k]+=1
    else:
        w[int(l[i][0])%k][int(l[i][1])%k]+=1

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

ans=0
for i in range(k+1):
    for j in range(k+1):
        ans=max(ans,b[k][k]-b[i][k]-b[k][j]+2*b[i][j]+w[i][k]+w[k][j]-2*w[i][j])
        ans=max(ans,w[k][k]-w[i][k]-w[k][j]+2*w[i][j]+b[i][k]+b[k][j]-2*b[i][j])
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
def main():
    input = sys.stdin.readline
    def gen_pattern(x):
        if x < K-1:
            return [[0, x+1], [x+K+1, 2*K]]
        else:
            return [[x-K+1, x+1]]
    def inputs():
        return [int(x) for x in input().split()]
    def inputstr():
        return list(input().split())
    N,K = inputs()
    BB = [[0]*(2*K+1) for _ in range(2*K+1)]
    for i in range(N):
        x,y,c = inputstr()
        if c=="W":
            y = int(y)+K
        x = int(x)%(2*K)
        y = int(y)%(2*K)
        #BB[x,y] += 1
        for shift in [0,K]:
            for b,t in gen_pattern((y+shift)%(2*K)):
                for l,r in gen_pattern((x+shift)%(2*K)):
                    BB[b][l] +=1
                    BB[b][r] -=1
                    BB[t][l] -=1
                    BB[t][r] +=1
    ans = (np.max(np.cumsum(np.cumsum(BB, axis=1), axis=0)))
    #print(BB)
    print(int(ans))
main()

Submission status: Accepted

Solution code:
def d_checker():
    # 参考1: https://pitsbuffersolution.com/compro/atcoder/arc089d.php
    # 参考2: https://atcoder.jp/contests/abc086/submissions/3271380
    import numpy as np
    N, K = [int(i) for i in input().split()]

    def get_bound(p):
        """ある希望を満たすような角のマスの集合はKxK正方形区間のようになっている
        p<K-1 のときはその正方形を分割しないとならない"""
        return [(0, p + 1), (p + K + 1, 2 * K)] if p < K - 1 else [(p - K + 1, p + 1)]

    # マス(x, y)が白⇔マス(x, y+K)が黒なので、希望の色を黒に統一する
    # 市松模様の周期は2Kなので、x, y座標をそれぞれ2Kで剰余を取った座標と同一視できる
    requests_black = [[0] * (2 * K + 1) for _ in range(2 * K + 1)]
    for _ in range(N):
        x, y, c = input().split()
        x = int(x) % (2 * K)
        y = int(y) % (2 * K) if c == 'B' else (int(y) + K) % (2 * K)

        for shift in (0, K):  # 2Kx2Kの市松模様の中に同色の領域が2つずつあることを反映
            # bottom, top, left, right
            for b, t in get_bound((y + shift) % (2 * K)):
                for l, r in get_bound((x + shift) % (2 * K)):
                    # 2次元imos法(左上、左下、右上、右下に±1することと対応)
                    requests_black[b][l] += 1
                    requests_black[t][l] -= 1
                    requests_black[b][r] -= 1
                    requests_black[t][r] += 1
    # 最後に累積和を取ると、あるマスを正方形の角としたとき叶えられる希望の数がわかる
    return int(np.max(np.cumsum(np.cumsum(requests_black, axis=1), axis=0)))

print(d_checker())

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,K = II()
x = [0]*N
y = [0]*N
z = ['0']*N
for i in range(N):
    a,b,c = input().split()
    x[i],y[i],z[i] = int(a),int(b),c

x,y = y,x

for i in range(N):
    if z[i]=='B':
        x[i] = (2*K-1)-x[i]%(2*K)
        y[i] = y[i]%(2*K)
    else:
        x[i] += K
        x[i] = (2*K-1)-x[i]%(2*K)
        y[i] = y[i]%(2*K)

kukan = []
for i in range(N):
    if x[i]+K-1<=2*K-1:
        if y[i]-K+1>=0:
            kukan.append([x[i],x[i]+K-1,y[i]-K+1,y[i]])
        else:
            kukan.append([x[i],x[i]+K-1,0,y[i]])
            kukan.append([x[i],x[i]+K-1,K+y[i]+1,2*K-1])
    else:
        if y[i]-K+1>=0:
            kukan.append([0,x[i]-K-1,y[i]-K+1,y[i]])
            kukan.append([x[i],2*K-1,y[i]-K+1,y[i]])
        else:
            kukan.append([0,x[i]-K-1,0,y[i]])
            kukan.append([0,x[i]-K-1,K+y[i]+1,2*K-1])
            kukan.append([x[i],2*K-1,0,y[i]])
            kukan.append([x[i],2*K-1,K+y[i]+1,2*K-1])

tiles = [[0]*(2*K+1) for _ in range(2*K+1)]
for k in kukan:
    tiles[k[0]][k[2]] += 1
    tiles[k[0]][k[3]+1] -= 1
    tiles[k[1]+1][k[2]] -= 1
    tiles[k[1]+1][k[3]+1] += 1

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

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

ans = 0
for i in range(2*K):
    for j in range(2*K):
        if tiles[i][j]+tiles[(i+K)%(2*K)][(j+K)%(2*K)]>ans:
            ans = tiles[i][j]+tiles[(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())
grid = [[0]*k for i in range(k)]
black = 0
for i in range(n):
    a,b,c =input().split()
    a,b = int(a), int(b)
    f = a//k + b//k
    a %= k
    b %= k
    if (c == "W" and f%2==0) or (c == "B" and f%2==1):
        grid[a][b] += 1
    else:
        grid[a][b] -= 1
        black += 1

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

ans = 0
for i in range(k):
    for j in range(k):
        a = s[k][k] - s[i][k] - s[k][j] + 2*s[i][j] + black
        ans = max(ans, max(a, n-a))
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
info = [list(input().split()) for i in range(n)]

cnt_b = [[0]*k for i in range(k)]
cnt_w = [[0]*k for i in range(k)]

for i in range(n):
    x, y, c = info[i]
    x, y = int(x), int(y)
    move_cnt = (x//k) + (y//k)
    if move_cnt % 2 == 0:
        if c == "B":
            cnt_b[x % k][y % k] += 1
        if c == "W":
            cnt_w[x % k][y % k] += 1
    else:
        if c == "B":
            cnt_w[x % k][y % k] += 1
        if c == "W":
            cnt_b[x % k][y % k] += 1

ruiseki_b = [[0]*(k+1) for i in range(k+1)]
ruiseki_w = [[0]*(k+1) for i in range(k+1)]
for i in range(k):
    for j in range(k):
        ruiseki_b[i+1][j+1] = ruiseki_b[i+1][j] + cnt_b[i][j]
        ruiseki_w[i+1][j+1] = ruiseki_w[i+1][j] + cnt_w[i][j]
for j in range(k):
    for i in range(k):
        ruiseki_b[i+1][j+1] += ruiseki_b[i][j+1]
        ruiseki_w[i+1][j+1] += ruiseki_w[i][j+1]
ans = 0
for i in range(k+1):
    for j in range(k+1):
        ans_b = ruiseki_b[k][k] - ruiseki_b[i][k] - ruiseki_b[k][j] + 2*ruiseki_b[i][j]
        ans_w = ruiseki_w[i][k] + ruiseki_w[k][j] - 2*ruiseki_w[i][j]
        ans = max(ans_w + ans_b, ans)
        ans_w = ruiseki_w[k][k] - ruiseki_w[i][k] - ruiseki_w[k][j] + 2*ruiseki_w[i][j]
        ans_b = ruiseki_b[i][k] + ruiseki_b[k][j] - 2*ruiseki_b[i][j]
        ans = max(ans_w + ans_b, ans)
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N,K = map(int,input().split())
    BMAP = [[0]*(2*K) for j in range(2*K)]
    WMAP = [[0]*(2*K) for j in range(2*K)]
    
    for i in range(N):
        x,y,c = input().split()
        x = int(x)%(2*K)
        y = int(y)%(2*K)
        if c == "B":
            BMAP[y][x] += 1
        else:
            WMAP[y][x] += 1
    
    import copy
    Bruiseki =  copy.deepcopy(BMAP)
    Wruiseki =  copy.deepcopy(WMAP)
    
    for i in range(2*K):
        for j in range(1,2*K):
            Bruiseki[i][j] += Bruiseki[i][j-1]
            Wruiseki[i][j] += Wruiseki[i][j-1]
    
    for i in range(2*K):
        for j in range(1,2*K):
            Bruiseki[j][i] += Bruiseki[j-1][i]
            Wruiseki[j][i] += Wruiseki[j-1][i]
    
    ans = 0
    for i in range(K):
        for j in range(K):
            Bone = Bruiseki[i][j]
            Btwo = Bruiseki[i][j+K] - Bone
            Bthree = Bruiseki[i][2*K-1] - Bruiseki[i][j+K]
            Bfour = Bruiseki[i+K][j] - Bone
            Bfive = Bruiseki[i+K][j+K] - Bone - Btwo - Bfour
            Bsix = Bruiseki[i+K][2*K-1] - Bruiseki[i+K][j+K] - Bthree
            Bseven =  Bruiseki[2*K-1][j] - Bruiseki[i+K][j]
            Beight = Bruiseki[2*K-1][j+K] - Bruiseki[i+K][j+K] - Bseven
            Bnine = Bruiseki[2*K-1][2*K-1] - Bruiseki[2*K-1][j+K] - Bthree - Bsix
            
            Wone = Wruiseki[i][j]
            Wtwo = Wruiseki[i][j+K] - Wone
            Wthree = Wruiseki[i][2*K-1] - Wruiseki[i][j+K]
            Wfour = Wruiseki[i+K][j] - Wone
            Wfive = Wruiseki[i+K][j+K] - Wone - Wtwo - Wfour
            Wsix = Wruiseki[i+K][2*K-1] - Wruiseki[i+K][j+K] - Wthree
            Wseven =  Wruiseki[2*K-1][j] - Wruiseki[i+K][j]
            Weight = Wruiseki[2*K-1][j+K] - Wruiseki[i+K][j+K] - Wseven
            Wnine = Wruiseki[2*K-1][2*K-1] - Wruiseki[2*K-1][j+K] - Wthree - Wsix
            
            tmp1 = Wone+Wthree+Wfive+Wseven+Wnine + Btwo+Bfour+Bsix+Beight
            tmp2 = Bone+Bthree+Bfive+Bseven+Bnine + Wtwo+Wfour+Wsix+Weight
            
            if tmp1 > ans:
                ans = tmp1
            if tmp2 > ans:
                ans = tmp2
            
    print(ans)

    
    
main()

Submission status: Accepted

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

dp = [[0] * (3*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 == 'W' :
        x += K
    
    m = min(x//K, y//K)
    x -= m * K
    y -= m * K
    x %= 2 * K
    y %= 2 * K
    
    dp[x][y] += 1
    if x < K and y < K :
        dp[x+K][y+K] += 1
        dp[x][y+2*K] += 1
    elif x < K and y >= K :
        dp[x+K][y-K] += 1
        dp[x+K][y+K] += 1
    elif x >= K and y < K :
        dp[x-K][y+K] += 1
        dp[x][y+2*K] += 1

for i in range(2 * K) :
    for j in range(3 * K) :
        dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        
ret = 0
for i in range(K-1, 2 * K) :
    for j in range(K-1, 3 * K) :
        ret = max(ret, dp[i][j] - dp[i][j-K] - dp[i-K][j] + dp[i-K][j-K])
print(ret)

Submission status: Accepted

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


N, K = map(int, input().split())
black = []
white = []
for i in range(N):
    x, y, c = map(str, input().split())
    temp = 0
    dx, x = divmod(int(x), K)
    temp += dx
    dy, y = divmod(int(y), K)
    temp += dy
    color = 0 if c == 'B' else 1
    color = (color + temp) % 2
    if color == 0:
        white.append((x, y))
    else:
        black.append((x, y))

white_bit_list = [0]
black_bit_list = [0]
for _ in range(K):
    white_bit = Bit(K)
    black_bit = Bit(K)
    white_bit_list.append(white_bit)
    black_bit_list.append(black_bit)
white_y = [0] * K
black_y = [0] * K
for xy in white:
    x, y = xy
    white_y[y] += 1
    x += 1
    y += 1
    white_bit_list[x].add(y, 1)
for xy in black:
    x, y = xy
    black_y[y] += 1
    x += 1
    y += 1
    black_bit_list[x].add(y, 1)
white_y_cum = [0] * (K + 1)
black_y_cum = [0] * (K + 1)
for i in range(K):
    white_y_cum[i + 1] = white_y_cum[i] + white_y[i]
    black_y_cum[i + 1] = black_y_cum[i] + black_y[i]

ans_best = 0
for dy in range(1, K):
    ul_w = 0
    ur_b = black_y_cum[dy]
    ll_b = 0
    lr_w = white_y_cum[-1] - white_y_cum[dy]
    ans = ul_w + ur_b + ll_b + lr_w
    ans_best = max(ans_best, ans, N - ans)
    for dx in range(1, K):
        ul_w += white_bit_list[dx].sum(dy)
        ur_b -= black_bit_list[dx].sum(dy)
        ll_b += black_bit_list[dx].sum(K) - black_bit_list[dx].sum(dy)
        lr_w -= white_bit_list[dx].sum(K) - white_bit_list[dx].sum(dy)
        ans = ul_w + ur_b + ll_b + lr_w
        ans_best = max(ans_best, ans, N - ans)
l_w = 0
r_b = len(black)
ans = l_w + r_b
ans_best = max(ans_best, ans, N - ans)
for dx in range(1, K):
    l_w += white_bit_list[dx].sum(K)
    r_b -= black_bit_list[dx].sum(K)
    ans = l_w + r_b
    ans_best = max(ans_best, ans, N - ans)

print(ans_best)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
w=[[0]*(k+1) for _ in range(k+1)]
b=[[0]*(k+1) for _ in range(k+1)]
for i in range(n):
    if ((int(l[i][0])//k+int(l[i][1])//k)%2==0)^(l[i][2]=='W'):
        b[int(l[i][0])%k][int(l[i][1])%k]+=1
    else:
        w[int(l[i][0])%k][int(l[i][1])%k]+=1

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

ans=0
for i in range(k+1):
    for j in range(k+1):
        ans=max(ans,b[k][k]-b[i][k]-b[k][j]+2*b[i][j]+w[i][k]+w[k][j]-2*w[i][j])
        ans=max(ans,w[k][k]-w[i][k]-w[k][j]+2*w[i][j]+b[i][k]+b[k][j]-2*b[i][j])
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(str, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    ans = ['Odd', 'Even']
    print(ans[(a*b)%2-1])
    return

#B
def B():
    a, b = map(str,input().split())
    a = a + b
    if math.sqrt(int(a)).is_integer():
        print("Yes")
    else:
        print("No")
    return

#C
def C():
    n = II()
    pre = (0, 0, 0)
    for _ in range(n):
        t,x,y = LI()
        dist = abs(pre[0] - x) + abs(pre[1] - y)
        if dist <= t - pre[2] and dist % 2 == (t - pre[2]) % 2:
            pre = (x, y, t)
            continue
        print("No")
        return
    print("Yes")
    return

#D
def D():
    n, k = LI()
    dp = [[0] * (2 * k + 1) for i in range(2 * k + 1)]
    for _ in range(n):
        x, y, c = LS()
        x, y = int(x), int(y)
        if c == "W":
            dp[y % (2 * k) + 1][(x + k) % (2 * k) + 1] += 1
        else:
            dp[y % (2 * k) + 1][x % (2 * k) + 1] += 1
    for y in range(2 * k + 1):
        for x in range(1, 2 * k + 1):
            dp[y][x] += dp[y][x - 1]
    for y in range(1, 2 * k + 1):
        for x in range(2 * k + 1):
            dp[y][x] += dp[y - 1][x]
    
    def count(l, r, d, u):
        return dp[d][l] - dp[d][r] - dp[u][l] + dp[u][r]
    
    ans = 0
    for i in range(k):
        for j in range(k):
            tmp = count(j, j + k, i, i + k) + count(0, j, 0, i) + count(j + k, 2 * k, 0, i) + \
                 count(0, j, i + k, 2 * k) + count(j + k, 2 * k, i + k, 2 * k)
            ans = max(ans, tmp, n - tmp)
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
#n = int(input())
n,k = [int(i) for i in readline().split()]
xyc = []


B = [[0]*(k+1) for i in range(k+1)]
W = [[0]*(k+1) for i in range(k+1)]

for _ in range(n):
    x,y,c = [i for i in readline().split()] 
    x = int(x)
    y = int(y)
    sgn = 0
    sgn += x//k
    x %= k
    sgn += y//k
    y %= k
    if sgn&1:
        if c == "W": B[x+1][y+1] += 1
#            xyc.append((x,y,"B"))
        else: W[x+1][y+1] += 1
#            xyc.append((x,y,"W"))
    else:
        if c == "W": W[x+1][y+1] += 1
#            xyc.append((x,y,"B"))
        else: B[x+1][y+1] += 1
#            xyc.append((x,y,"W"))


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

#print(B)
#print(W)

ans = 0
for i in range(k):
    for j in range(k):
        resb1 = B[i][j] + (B[-1][-1] - B[-1][j] - B[i][-1] + B[i][j])
        resw1 = W[i][j] + (W[-1][-1] - W[-1][j] - W[i][-1] + W[i][j])
        
        resb2 = (B[i][-1] - B[i][j]) + (B[-1][j] - B[i][j])
        resw2 = (W[i][-1] - W[i][j]) + (W[-1][j] - W[i][j])
        
#        print(i,j,"ij",resb1,resw2,resw1,resb2)
        ans = max(ans,resb1+resw2, resw1+resb2)


print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

N, K = map(int, input().split())
KK = 2*K
m = [[0] * (2*KK+1) for i in range(2*KK+1)]
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        y += K
    x %= KK
    y %= KK
    m[y+1][x+1] += 1
    m[y+KK+1][x+KK+1] += 1
    m[y+1][x+KK+1] += 1
    m[y+KK+1][x+1] += 1
for i in range(1, 2*KK+1):
    for j in range(2*KK):
        m[i][j+1] += m[i][j]
for j in range(1, 2*KK+1):
    for i in range(2*KK):
        m[i+1][j] += m[i][j]
ans = 0
for i in range(KK):
    for j in range(KK):
        ans = max(ans, 2*m[i+K][j+K]-m[i+K][j]-m[i][j+K]+m[i][j]+m[i+KK][j+KK]-m[i+KK][j+K]-m[i+K][j+KK])
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
XYC = [[int(x)%(2*K),int(y)%(2*K),int(c=="B")] for x,y,c in [input().split() for _ in [0]*N]]

score = [[[0]*(3*K+1) for _ in [0]*(3*K+1)] for _ in [0]*2]
for x,y,c in XYC:
    x+=1
    y+=1
    score[c][y][x] += 1
    if x<K: score[c][y][x+2*K] += 1
    if y<K: score[c][y+2*K][x] += 1
    if x<K and y<K: score[c][y+2*K][x+2*K] += 1

S = score
for c in range(2):
    for j in range(3*K):
        for i in range(3*K):
            S[c][i+1][j+1] += S[c][i][j+1]
    for i in range(3*K):
        for j in range(3*K):
            S[c][i+1][j+1] += S[c][i+1][j]

def get_sum(c,si,sj,i,j):
    i+=1
    j+=1
    return S[c][i][j] + S[c][si][sj] - S[c][i][sj] - S[c][si][j]

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

Submission status: Accepted

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

SB = [[0] * (4 * K + 1) for _ in range(4 * K + 1)]
for x in range(4 * K):
    for y in range(4 * K):
        SB[x][y] = B[x % (2 * K)][y % (2 * K)]
for x in range(4 * K):
    for y in range(4 * K):
        SB[x + 1][y] += SB[x][y]
for y in range(4 * K):
    for x in range(4 * K):
        SB[x][y + 1] += SB[x][y]

ans = 0
for x in range(2 * K):
    for y in range(2 * K):
        cand = SB[x + K][y + K] - SB[x][y + K] - SB[x + K][y] + SB[x][y]
        cand += SB[x + 2 * K][y + 2 * K] - SB[x + K][y + 2 * K] - \
            SB[x + 2 * K][y + K] + SB[x + K][y + K]
        ans = max(ans, cand)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
B = np.zeros((2 * K, 2 * K), np.int32)

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

SB = np.zeros((4 * K + 1, 4 * K + 1), np.int32)

SB[0*K+1:2*K+1, 0*K+1:2*K+1] = B
SB[0*K+1:2*K+1, 2*K+1:4*K+1] = B
SB[2*K+1:4*K+1, 0*K+1:2*K+1] = B
SB[2*K+1:4*K+1, 2*K+1:4*K+1] = B

np.cumsum(SB, 0, out=SB)
np.cumsum(SB, 1, out=SB)

ans = 0
cand = SB[1*K:3*K+1, 1*K:3*K+1].copy()
cand -= SB[0*K:2*K+1, 1*K:3*K+1]
cand -= SB[1*K:3*K+1, 0*K:2*K+1]
cand += SB[0*K:2*K+1, 0*K:2*K+1]
cand += SB[2*K:4*K+1, 2*K:4*K+1]
cand -= SB[1*K:3*K+1, 2*K:4*K+1]
cand -= SB[2*K:4*K+1, 1*K:3*K+1]
cand += SB[1*K:3*K+1, 1*K:3*K+1]
ans = np.max(cand)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
# from time import time

# t0 = time()
N, K = map(int, input().split())
B = np.zeros((2 * K, 2 * K), np.int32)
W = np.zeros((2 * K, 2 * K), np.int32)
# t1 = time()
# print(t1 - t0)
for _ in range(N):
    x, y, c = input().split()
    if c == "B":
        B[int(x) % (2 * K)][int(y) % (2 * K)] += 1
    else:
        W[int(x) % (2 * K)][int(y) % (2 * K)] += 1
# t2 = time()
# print(t2 - t1)
SB = np.zeros((4 * K + 1, 4 * K + 1), np.int32)
SW = np.zeros((4 * K + 1, 4 * K + 1), np.int32)
# t3 = time()
# print(t3 - t2)
SB[0*K+1:2*K+1, 0*K+1:2*K+1] = B
SB[0*K+1:2*K+1, 2*K+1:4*K+1] = B
SB[2*K+1:4*K+1, 0*K+1:2*K+1] = B
SB[2*K+1:4*K+1, 2*K+1:4*K+1] = B
SW[0*K+1:2*K+1, 0*K+1:2*K+1] = W
SW[0*K+1:2*K+1, 2*K+1:4*K+1] = W
SW[2*K+1:4*K+1, 0*K+1:2*K+1] = W
SW[2*K+1:4*K+1, 2*K+1:4*K+1] = W
# t4 = time()
# print(t4 - t3)
np.cumsum(SB, 0, out=SB)
np.cumsum(SB, 1, out=SB)
np.cumsum(SW, 0, out=SW)
np.cumsum(SW, 1, out=SW)
# t5 = time()
# print(t5 - t4)
ans = 0
cand = SB[1*K:3*K+1, 1*K:3*K+1].copy()
cand -= SB[0*K:2*K+1, 1*K:3*K+1]
cand -= SB[1*K:3*K+1, 0*K:2*K+1]
cand += SB[0*K:2*K+1, 0*K:2*K+1]
cand += SB[2*K:4*K+1, 2*K:4*K+1]
cand -= SB[1*K:3*K+1, 2*K:4*K+1]
cand -= SB[2*K:4*K+1, 1*K:3*K+1]
cand += SB[1*K:3*K+1, 1*K:3*K+1]
cand += SW[2*K:4*K+1, 1*K:3*K+1]
cand -= SW[1*K:3*K+1, 1*K:3*K+1]
cand -= SW[2*K:4*K+1, 0*K:2*K+1]
cand += SW[1*K:3*K+1, 0*K:2*K+1]
cand += SW[1*K:3*K+1, 2*K:4*K+1]
cand -= SW[0*K:2*K+1, 2*K:4*K+1]
cand -= SW[1*K:3*K+1, 1*K:3*K+1]
cand += SW[0*K:2*K+1, 1*K:3*K+1]
ans = np.max(cand)
# t6 = time()
# print(t6 - t5)

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
dp=[[0]*k for i in range(k)]
for i in range(n):
    x,y,z=input().split()
    x,y=int(x),int(y)
    if (x//k)%2==(y//k)%2:
        if z=='W':
            x,y=x%k,y%k
            dp[0][0]+=1
            if y<k-1:
                dp[0][y+1]-=1
            if x<k-1:
                dp[x+1][0]-=1
            if x<k-1 and y<k-1:
                dp[x+1][y+1]+=2
        else:
            x,y=x%k,y%k
            if y<k-1:
                dp[0][y+1]+=1
            if x<k-1:
                dp[x+1][0]+=1
            if x<k-1 and y<k-1:
                dp[x+1][y+1]-=2
    else:
        if z=='W':
            x,y=x%k,y%k
            if y<k-1:
                dp[0][y+1]+=1
            if x<k-1:
                dp[x+1][0]+=1
            if x<k-1 and y<k-1:
                dp[x+1][y+1]-=2
        else:
            x,y=x%k,y%k
            dp[0][0]+=1
            if y<k-1:
                dp[0][y+1]-=1
            if x<k-1:
                dp[x+1][0]-=1
            if x<k-1 and y<k-1:
                dp[x+1][y+1]+=2
for i in range(k):
    for j in range(1,k):
        dp[i][j]+=dp[i][j-1]
Max=0
Min=n
for j in range(k):
    for i in range(k):
        if i==0:
            Max=max(Max,dp[i][j])
            Min=min(Min,dp[i][j])
        else:
            dp[i][j]+=dp[i-1][j]
            Max=max(Max,dp[i][j])
            Min=min(Min,dp[i][j])
ans=max(Max,n-Min)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    white = [[0] * K for _ in range(2*K)]
    for i in range(N):
        x, y, c = input().split()
        x, y = int(x) % (2*K), int(y) % (2*K)
        if y >= K:
            y -= K
            x = (x-K) % (2*K)
        if c == "W":
            white[x][y] += 1
        else:
            white[(x+K) % (2*K)][y] += 1
    ysum = [[0] * (2*K) for _ in range(2*K)]
    for i in range(2*K):
        ysum[i][0] = sum(white[i][:K])
        for j in range(1, K):
            ysum[i][j] = ysum[i][j-1] - white[i][j-1]
        for j in range(K+1, 2*K):
            ysum[i][j] = ysum[i][j-1] + white[i][(j+K-1) % (2*K)]
    csum = [[0] * (2*K) for _ in range(2*K)]
    ans = 0
    for i in range(2*K):
        csum[0][i] = sum([ysum[x][i] for x in range(K)]) + \
            sum([ysum[x][(i+K) % (2*K)] for x in range(K, 2*K)])
        for j in range(1, 2*K):
            csum[j][i] = csum[j-1][i] \
                + ysum[(j+K-1) % (2*K)][i] - ysum[(j+K-1) % (2*K)][(i+K) % (2*K)]\
                - ysum[j-1][i] + ysum[j-1][(i+K) % (2*K)]
    for i in range(2*K):
        for j in range(K):
            ans = max(ans, csum[i][j])
    print(ans)


if __name__ == "__main__":
    main()