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

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

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

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

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

Solution (Python):


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()

Solution (Python):


"""
参考：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())


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)
    
    if c == 'W':
        y += K
    
    B[x%(K*2)][y%(K*2)] += 1


sm = [[0] * (K*4) for i in range(K*4)]

for i in range(K*4):
    for j in range(K*4):
        
        
        sm[i][j] = B[i%(K*2)][j%(K*2)]
        
        
        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]


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):
        
        tmp = get_sum(i, j, i+K-1, j+K-1, sm)
        
        tmp += get_sum(i+K, j+K, i+K*2-1, j+K*2-1, sm)
        ans = max(tmp, ans)
print(ans)

Solution (Python):


"""
参考：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())


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)
    
    if c == 'W':
        y += K
    
    B[x%(K*2)][y%(K*2)] += 1

for i in range(K*4):
    for j in range(K*4):
        
        
        B[i][j] = B[i%(K*2)][j%(K*2)]



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]


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):
        
        tmp = get_sum(i, j, i+K-1, j+K-1, B)
        
        tmp += get_sum(i+K, j+K, i+K*2-1, j+K*2-1, B)
        ans = max(tmp, ans)
print(ans)

Solution (Python):


"""
参考：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にするか人によって色々で、
　それぞれに考慮する点があると思った。
・定数倍高速化のためループまとめて(4K^2)*3回を1回にしたから、
　5200万がO((4K)^2+(2K)^2)=2000万くらいになって結構速くなったはず。
　…と思ったらメモリがオーバーしたから余計な配列減らした。
"""

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

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


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


sm = [[0] * (K*4+1) for i in range(K*4+1)]


for i in range(1, K*4+1):
    for j in range(1, K*4+1):
        
        
        sm[i][j] = B[(i-1)%(K*2)+1][(j-1)%(K*2)+1]
        
        sm[i][j] += sm[i][j-1] + sm[i-1][j] - sm[i-1][j-1]


def get_sum(x1, y1, x2, y2, sm):
    
    res = sm[x2][y2] - sm[x1-1][y2] - sm[x2][y1-1] + sm[x1-1][y1-1]
    return res

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

Solution (Python):


"""
参考：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にするか人によって色々で、
　それぞれに考慮する点があると思った。
・とりあえず理解重視で、処理を分けて実装したから、このままだと多分pypyでもTLEかと。
"""

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

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


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

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



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


def get_sum(x1, y1, x2, y2, sm):
    
    res = sm[x2][y2] - sm[x1-1][y2] - sm[x2][y1-1] + sm[x1-1][y1-1]
    return res

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

Solution (Python):
N, K = map(int, input().split())
Requests = []
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)
    Requests.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):
        
        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(Requests)
R2D.calc()

ans = 0
for x in range(K):
    for y in range(K):
        tmp = 0
        tmp += R2D.get(0, 0, x - 1, y - 1)  
        tmp += R2D.get(x + K, 0, 2 * K - 1, y - 1)  
        tmp += R2D.get(x, y, x + K - 1, y + K - 1)  
        tmp += R2D.get(0, y + K, x - 1, 2 * K - 1)  
        tmp += R2D.get(x + K, y + K, 2 * K - 1, 2 * K - 1)  

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

print(ans)

Solution (Python):
N, K = map(int, input().split())
G = [[[0, 0] for j in range(2 * K + 1)] for i in range(K + 1)]
W = 0
for i in range(N):
  x, y, c = input().split()
  X = int(x) % (2 * K)
  Y = int(y) % (2 * K)
  if X >= K:
    X = (X - K) % K
    Y = (Y - K) % (2 * K)
  G[X + 1][Y + 1][0 if c == 'W' else 1] += 1
  W += 1 if c == 'W' else 0
for i in range(1, K + 1):
  for j in range(1, 2 * K + 1):
    G[i][j][0] += G[i][j - 1][0]
    G[i][j][1] += G[i][j - 1][1]
for i in range(1, K + 1):
  for j in range(1, 2 * K + 1):
    G[i][j][0] += G[i - 1][j][0]
    G[i][j][1] += G[i - 1][j][1]
cnt = 0
for i in range(1, K + 1):
  for j in range(1, K + 1):
    w = 2 * G[i - 1][j - 1][0] + G[K][j + K - 1][0] - 2 * G[i - 1][j + K - 1][0] - G[K][j - 1][0] + G[i - 1][2 * K][0]
    b = 2 * G[i - 1][j - 1][1] + G[K][j + K - 1][1] - 2 * G[i - 1][j + K - 1][1] - G[K][j - 1][1] + G[i - 1][2 * K][1]
    cnt = max([w + (N - W - b), (W - w) + b, cnt])
print(cnt)

Solution (Python):



import sys
fin = sys.stdin.readline
from collections import defaultdict
from pprint import pprint

def sum_range_2D(cuml_mat, coord_left_up, Kx, Ky):
    if Kx <= 0 or Ky <= 0:
        return 0
    x, y = coord_left_up
    if x - 1 >= 0 and y - 1 >= 0:
        left_up = cuml_mat[x - 1][y - 1]
    else:
        left_up = 0
    if x - 1 >= 0 and y + Ky - 1 >= 0:
        right_up = cuml_mat[x - 1][y + Ky - 1]
    else:
        right_up = 0
    if x + Kx - 1 >= 0 and y - 1 >= 0:
        left_down = cuml_mat[x + Kx - 1][y - 1]
    else:
        left_down = 0
    right_down = cuml_mat[min(len(cuml_mat) - 1, x + Kx - 1)][min(len(cuml_mat) - 1, y + Ky - 1)]
    return right_down - right_up - left_down + left_up


N, K = [int(elem) for elem in fin().split()]
black_desires = []
for _ in range(N):
    x, y, c = fin().split()
    x = int(x) % (2 * K)
    y = int(y) % (2 * K) if c == 'B' else (int(y) + K) % (2 * K)
    black_desires.append((x, y))

cuml_2D = [[0] * (2*K) for _ in range(2*K)]
for x, y in black_desires:
    cuml_2D[x][y] += 1

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

max_num = 0
for i in range(K + 1):
    for j in range(K):
        current_num = sum_range_2D(cuml_2D, (i, j), K, K) \
                    + sum_range_2D(cuml_2D, (0, 0), i, j) \
                    + sum_range_2D(cuml_2D, (0, j + K), i, K - j) \
                    + sum_range_2D(cuml_2D, (i + K, 0), K - i, j) \
                    + sum_range_2D(cuml_2D, (i + K, j + K), K - i, K - j)
        max_num = max(max_num, current_num)


for i in range(K + 1):
    for j in range(K, 2 * K):
        current_num = sum_range_2D(cuml_2D, (i, j), K, 2 * K - j) \
                    + sum_range_2D(cuml_2D, (0, j - K), i, K) \
                    + sum_range_2D(cuml_2D, (i + K, j - K), K - i, K) \
                    + sum_range_2D(cuml_2D, (i, 0), K, j - K)
        max_num = max(max_num, current_num)

print(max_num)

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

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

X = []
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)

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

    
    X.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):
        
        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(X)
R2D.calc()


ans = 0
for i in range(K):
    for j in range(K):
        tmp = 0
        tmp += R2D.get(0, 0, i - 1, j - 1)  
        tmp += R2D.get(0, j + K, i - 1, 2 * K - 1)  
        tmp += R2D.get(i, j, i + K - 1, j + K - 1)  
        tmp += R2D.get(i + K, 0, 2 * K - 1, j - 1)  
        tmp += R2D.get(i + K, j + K, 2 * K - 1, 2 * K - 1)  

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

print(ans)

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

X = []
for i in range(N):
    h, w, c = input().split()
    h, w = int(h) - 1, int(w) - 1
    if c == "W":
        h += K
    X.append((h % (2 * K), w % (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):
        
        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(X)
R2D.calc()

ans = 0
for h in range(K):
    for w in range(K):
        tmp = 0
        tmp += R2D.get(h, w, h + K - 1, w + K - 1)  
        tmp += R2D.get(0, 0, h - 1, w - 1)  
        tmp += R2D.get(0, w + K, h - 1, 2 * K - 1)  
        tmp += R2D.get(h + K, 0, 2 * K - 1, w - 1)  
        tmp += R2D.get(h + K, w + K, 2 * K - 1, 2 * K - 1)  
        ans = max(ans, tmp, N - tmp)

print(ans)

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

def vertex(z):
    if z < K:
        return [(0,z+1),(z+K+1,2*K)]
    else:
        return [(z-K+1,z+1)]

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

    for d in [0,K]:
        for b,t in vertex((y+d)%(2*K)):
            for l,r in vertex((x+d)%(2*K)):
                cum[b][l] += 1
                cum[t][r] += 1
                cum[b][r] -= 1
                cum[t][l] -= 1

import numpy as np
cum = np.array(cum)
print(np.cumsum(np.cumsum(cum,axis=0),axis=1).max())

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

black = 0
imos = [[0 for i in range(k)] for j in range(k)]

for i in range(n):
    X, Y, C = input().split()
    x = int(X)
    y = int(Y)
    c = 1 if C == "W" else 0

    x = x % (2*k)
    y = y % (2*k)
    if x > k-1:
        x -= k
        c += 1
    if y > k-1:
        y -= k
        c += 1
    c = 1 if c%2 == 1 else -1
    imos[x][y] += c
    if c == -1:
        black += 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):
        m = imos[k-1][k-1] - imos[k-1][j] - imos[i][k-1] + 2 * imos[i][j]
        ans = max(ans, max(n-(black+m), black+m))
print(ans)

Solution (Python):
N,K=map(int,input().split())
XYC=[list(input().split()) for i in range(N)]

MAP=[[0 for i in range(K*2+1)] for j in range(K*2+1)]
mod=K*2
for x,y,c in XYC:
    x=int(x)
    y=int(y)
    if c=="W":
        x+=K

    MAP[x%mod+1][y%mod+1]+=1
    MAP[(x+K)%mod+1][(y+K)%mod+1]+=1




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

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

ANS=0
for i in range(K):
    for j in range(K):

        if ANS<MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]:
            ANS=MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]
        if ANS<N-(MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j]):
            ANS=N-(MAP[i+K][j+K]-MAP[i][j+K]-MAP[i+K][j]+MAP[i][j])
print(ANS)

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

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

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

def count(x1,x2,y1,y2):
    return grid[y1][x1] - grid[y1][x2] - grid[y2][x1] + grid[y2][x2]

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)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def cum_2d(field:list):
    row = len(field)
    col = len(field[0])
    
    
    for r in range(row):
        for c in range(col-1):
            field[r][c+1] += field[r][c]
    
    
    for c in range(col):
        for r in range(row-1):
            field[r+1][c] += field[r][c]
            
    return field

n,k = li()

wishes = []

for _ in range(n):
    x,y,c = ls()
    x = int(x) % (2*k)
    y = int(y) % (2*k)
    
    if c == "B":
        if x >= k and y >= k:
            x -= k
            y -= k
        
        elif y >= k:
            x += k
            y -= k
    
    if c == "W":
        if x >= k and y >= k:
            y -= k
        
        elif x >= k:
            x -= k
            
        elif y >= k:
            y -= k
            
        else:
            x += k
        
    wishes.append((x,y))

imos = [[0 for _ in range(2*k+1)] for _ in range(2*k+1)]

for x, y in wishes:
    
    
    if x < k:
        
        imos[0][y+k+1] += 1
        imos[0][2*k] -= 1
        imos[x+1][y+k+1] -= 1
        imos[x+1][2*k] += 1
            
        
        imos[0][0] += 1
        imos[x+1][0] -= 1
        imos[0][y+1] -= 1
        imos[x+1][y+1] += 1
            
        
        imos[x+1][y+1] += 1
        imos[x+1][y+k+1] -= 1
        imos[x+k+1][y+1] -= 1
        imos[x+k+1][y+k+1] += 1
        
        
        imos[x+k+1][0] += 1
        imos[x+k+1][y+1] -= 1
        imos[2*k][0] -= 1
        imos[2*k][y+1] += 1
            
        
        imos[x+k+1][y+k+1] += 1
        imos[x+k+1][2*k] -= 1
        imos[2*k][y+k+1] -= 1
        imos[2*k][2*k] += 1

    
    else:
        
        imos[0][y+1] += 1
        imos[x-k+1][y+1] -= 1
        imos[0][y+k+1] -= 1
        imos[x-k+1][y+k+1] += 1
        
        
        imos[x-k+1][0] += 1
        imos[x-k+1][y+1] -= 1
        imos[x+1][0] -= 1
        imos[x+1][y+1] += 1
        
        
        imos[x+1][y+1] += 1
        imos[2*k][y+1] -= 1
        imos[x+1][y+k+1] -= 1
        imos[2*k][y+k+1] += 1
        
        
        imos[x-k+1][y+k+1] += 1
        imos[x-k+1][2*k] -= 1
        imos[x+1][y+k+1] -= 1
        imos[x+1][2*k] += 1
    


imos = cum_2d(imos)

ans = 0
for i in range(2*k):
    for j in range(2*k):
        if imos[i][j] > ans:
            ans = imos[i][j]
        

print(ans)

Solution (Python):
import numpy as np
n, k = list(map(int, input().split()))

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

blacks = [[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]:
        for b, t in get_bound((y+shift)%(2*k)):
            for l, r in get_bound((x+shift)%(2*k)):
                blacks[b][l] += 1
                blacks[t][l] -= 1
                blacks[b][r] -= 1
                blacks[t][r] += 1
        
ans = np.max(np.cumsum(np.cumsum(blacks, axis = 1), axis = 0))
print(int(ans))

Solution (Python):
R,r,g=range,raw_input,int;N,K=map(g,r().split());L=K+1;P,Q=R(K),R(L);D=[L*[0]for i in Q];a=b=0
for i in R(N):x,y,c=r().split();x,y=g(x),g(y);p=(x/K+y/K+ord(c))%2;D[y%K+1][x%K+1]+=1-2*p;b+=p
for i in P:
 for j in Q:D[i+1][j]+=D[i][j]
for i in P:
 for j in Q:D[j][i+1]+=D[j][i]
for i in Q:
 for j in Q:S=D[i][K]+D[K][j]-D[i][j]*2;a=max(a,S,D[K][K]-S)
print a+b

Solution (Python):
R,r=range,raw_input;N,K=map(int,r().split());L=K+1;P,Q=R(K),R(L);D=[L*[0]for i in Q];a=b=0
for i in R(N):x,y,c=r().split();x,y=int(x),int(y);p=(x/K+y/K+ord(c))%2;D[y%K+1][x%K+1]+=1-2*p;b+=p
for i in P:
 for j in Q:D[i+1][j]+=D[i][j]
for i in P:
 for j in Q:D[j][i+1]+=D[j][i]
for i in Q:
 for j in Q:S=D[i][K]+D[K][j]-D[i][j]*2;a=max(a,S,D[K][K]-S)
print a+b

Solution (Python):
R,r=range,raw_input;N,K=map(int,r().split());L=K+1;P,Q=R(K),R(L);D=[L*[0]for i in Q];a=b=0
for i in R(N):x,y,c=r().split();x,y=int(x),int(y);p=(x/K+y/K+ord(c))%2;D[y%K+1][x%K+1]+=1-2*p;b+=p
for i in P:
 for j in Q:D[i+1][j]+=D[i][j]
for i in P:
 for j in Q:D[j][i+1]+=D[j][i]
for i in Q:
 for j in Q:
  S=D[i][K]+D[K][j]-D[i][j]*2;a=max(a,S,D[K][K]-S)
print a+b

Solution (Python):
R,r=range,raw_input
N,K=map(int,r().split())
L=K+1
P,Q=R(K),R(L)
D=[L*[0]for i in Q]
a=b=0
for i in R(N):
 x,y,c=r().split()
 x,y=int(x),int(y)
 p=(x/K+y/K+ord(c))%2
 D[y%K+1][x%K+1]+=1-2*p
 b+=p
for k in R(2):
 for i in P:
  for j in Q:D[(i+1,j)[k]][(j,i+1)[k]]+=D[(i,j)[k]][(j,i)[k]]
for i in Q:
 for j in Q:
  S=D[i][K]+D[K][j]-D[i][j]*2
  a=max(a,S,D[K][K]-S)
print a+b

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

R,r=range,raw_input
N,K=map(int,r().split())
L=K+1
P,Q=R(K),R(L)
D=[L*[0]for i in Q]
a=b=0
for i in R(N):
 x,y,c=r().split()
 x,y=int(x),int(y)
 p=(x/K+y/K+ord(c))%2
 D[y%K+1][x%K+1]+=1-2*p
 b+=p
for i in P:
 for j in Q:D[i+1][j]+=D[i][j]
for i in P:
 for j in Q:D[j][i+1]+=D[j][i]
for i in Q:
 for j in Q:
  S=D[i][K]+D[K][j]-D[i][j]*2
  a=max(a,S,D[K][K]-S)
print a+b

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

R,r=range,raw_input
N,K=map(int,r().split())
L=K+1
P,Q=R(K),R(L)
D=[L*[0]for i in Q]
a=b=0
for i in R(N):
 x,y,c=r().split()
 x,y=int(x),int(y)
 p=(x/K+y/K+ord(c))%2
 D[y%K+1][x%K+1]+=1-2*p
 b+=p
for i in P:
 for j in Q:D[i+1][j]+=D[i][j]
for i in Q:
 for j in P:D[i][j+1]+=D[i][j]
for i in Q:
 for j in Q:
  S=D[i][K]+D[K][j]-D[i][j]*2
  a=max(a,S,D[K][K]-S)
print a+b

Solution (Python):
R,r=range,raw_input
N,K=map(int,r().split())
L=K+1
P,Q=R(K),R(L)
D=[L*[0]for i in Q]
a=b=0
for i in R(N):
 x,y,c=r().split()
 x,y=int(x),int(y)
 p=(x/K+y/K+ord(c))%2
 D[y%K+1][x%K+1]+=1-2*p
 b+=p
for i in P:
 for j in Q:D[i+1][j]+=D[i][j]
for i in Q:
 for j in P:D[i][j+1]+=D[i][j]
for i in Q:
 for j in Q:
  S=D[i][K]+D[K][j]-D[i][j]*2
  a=max(a,S,D[K][K]-S)
print a+b

Solution (Python):
N, K = map(int, raw_input().split())
R0, R1 = range(K), range(K + 1)
D = [[0] * (K + 1) for i in R1]
a = b = 0

for i in range(N):
    x, y, c = raw_input().split()
    x, y, c = int(x), int(y), c == 'W'
    p = (x / K + y / K + c) % 2
    D[y % K + 1][x % K + 1] += 1 - 2 * p
    b += p

for i in R0:
    for j in R1:
        D[i + 1][j] += D[i][j]

for i in R1:
    for j in R0:
        D[i][j + 1] += D[i][j]

for i in R1:
    for j in R1:
        S = D[i][K] + D[K][j] - D[i][j] * 2
        a = max(a, S, D[K][K] - S)

print a + b

Solution (Python):
N, K = map(int, raw_input().split())
R0, R1 = range(K), range(K + 1)
D = [[0] * (K + 1) for i in R1]
a = b = 0

for i in range(N):
    x, y, c = raw_input().split()
    x, y, c = int(x), int(y), (c == 'W')
    p = (x / K + y / K + c) % 2
    D[y % K + 1][x % K + 1] += 1 - 2 * p
    b += p

for i in R0:
    for j in R1:
        D[i + 1][j] += D[i][j]

for i in R1:
    for j in R0:
        D[i][j + 1] += D[i][j]

for i in R1:
    for j in R1:
        S = D[i][K] + D[K][j] - D[i][j] * 2
        a = max(a, S, D[K][K] - S)

print a + b

Solution (Python):
N, K = map(int, raw_input().split())
L = K + 1
D = [[0] * L for i in range(L)]
b = 0

for i in range(N):
    x, y, c = raw_input().split()
    x, y, c = int(x), int(y), (c == 'W')
    p = (x / K + y / K + c) % 2
    D[y % K + 1][x % K + 1] += 1 - 2 * p
    b += p

for i in range(K):
    for j in range(L):
        D[i + 1][j] += D[i][j]

for i in range(L):
    for j in range(K):
        D[i][j + 1] += D[i][j]

a = 0

for i in range(L):
    for j in range(L):
        S = D[i][K] + D[K][j] - D[i][j] * 2
        a = max(a, S, D[K][K] - S)

print a + b