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:
# -*- 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にするか人によって色々で、
　それぞれに考慮する点があると思った。
・定数倍高速化のためループまとめて(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())

# ここは循環するK*2まで作る
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)
    # 白に塗る条件はxかyにKずらして黒の条件にする(これで2色考えなくていい)
    if c == 'W':
        y += K
    # 循環するのでmod K*2でやる
    # 累積和でひとつ前を見に行くので、1-indexedにする
    B[x%(K*2)+1][y%(K*2)+1] += 1

# ここはK*2の正方形を右下まで動かすので、K*4まで作っておく
sm = [[0] * (K*4+1) for i in range(K*4+1)]
# 2次元累積和を取る
# 1-indexedなので、気にせず1からループすればいい
for i in range(1, K*4+1):
    for j in range(1, K*4+1):
        # K*2からはみ出る範囲も正しく累積和を出すため、K*2までの値を循環させる
        # 1-indexedにしているため、ここの加減がややこしい
        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]

# 2次元累積和に必要な4点の加減を行う
def get_sum(x1, y1, x2, y2, sm):
    # 1-indexedなので、x, yがマイナスの値になる考慮は必要ない
    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):
        # 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にするか人によって色々で、
　それぞれに考慮する点があると思った。
・とりあえず理解重視で、処理を分けて実装したから、このままだと多分pypyでもTLEかと。
"""

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

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

# K*2の正方形を右下まで動かすので、K*4まで作っておく
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)
    # 白に塗る条件はxかyにKずらして黒の条件にする(これで2色考えなくていい)
    if c == 'W':
        y += K
    # 循環するのでmod K*2でやる
    # 累積和でひとつ前を見に行くので、1-indexedにする
    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):
        # K*2からはみ出る範囲も正しく累積和を出すため、K*2までの値を循環させる
        # 1-indexedにしているため、ここの加減がややこしい
        B[i][j] = B[(i-1)%(K*2)+1][(j-1)%(K*2)+1]

# 2次元累積和を取る
# 1-indexedなので、気にせず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]

# 2次元累積和に必要な4点の加減を行う
def get_sum(x1, y1, x2, y2, sm):
    # 1-indexedなので、x, yがマイナスの値になる考慮は必要ない
    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):
        # 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)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
Requests = []
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)

    # 白ならKずらして黒についての要望と捉えることができる
    if c == 'W':
        x += K

    # 2Kずらすと必ず色が一致するので、2Kでmodを取ってよい
    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):
        # 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(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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# time complexity: O(N + K^2)
# space complexity: O(K^2)

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)

Submission status: Accepted

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

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

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

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

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

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

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

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

print(ans)

Submission status: Accepted

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

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

    # 白をKずらして黒に変換
    if c == "W":
        y += K

    # 2Kでmodをとる
    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):
        # 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(X)
R2D.calc()

# 真ん中の黒四角形について左上を全探索（K * Kまで）
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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 = []
# mod K をとり、すべての希望を黒に変換
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:
    
    # xが K 未満のとき
    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

    # xが K 以上のとき
    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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
#!/usr/bin/env 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

Submission status: Accepted

Solution code:
#!/usr/bin/env 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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
N, K = map(int, raw_input().split())
DP = [[0] * (K + 1) for i in range(K + 1)]
bias = 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
    DP[y % K + 1][x % K + 1] += 1 - 2 * p
    bias += p

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

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

ans = 0

for i in range(K + 1):
    for j in range(K + 1):
        S = DP[i][K] + DP[K][j] - DP[i][j] * 2
        ans = max(ans, S, DP[K][K] - S)

print ans + bias

Submission status: Accepted

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

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

sys.setrecursionlimit(1000000)

N, K = map(int, raw_input().split())
DP = [[0] * (K + 1) for i in range(K + 1)]
bias = 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
    DP[y % K + 1][x % K + 1] += 1 - 2 * p
    bias += p

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

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

ans = 0

for i in range(K + 1):
    for j in range(K + 1):
        S = DP[i][K] + DP[K][j] - DP[i][j] * 2
        ans = max(ans, S, DP[K][K] - S)

print ans + bias

Submission status: Accepted

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

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

sys.setrecursionlimit(1000000)

N, K = map(int, raw_input().split())
DP = [[0] * (K + 1) for i in range(K + 1)]
bias = 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
    DP[y % K + 1][x % K + 1] += 1 - 2 * p
    bias += p

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

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

ans = 0

for i in range(K + 1):
    for j in range(K + 1):
        S1 = DP[i][j] * 2 - DP[i][K] - DP[K][j] + DP[K][K]
        S2 = DP[i][K] + DP[K][j] - DP[i][j] * 2
        ans = max(ans, S1, S2)

print ans + bias

Submission status: Accepted

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

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

sys.setrecursionlimit(1000000)

N, K = map(int, raw_input().split())
DP = [[0] * (K + 1) for i in range(K + 1)]
bias = 0

for i in range(N):
    x, y, c = raw_input().split()
    x, y, c = int(x), int(y), (c == 'W')
    if (x / K + y / K + c) % 2 == 0:
        DP[y % K + 1][x % K + 1] += 1
    else:
        DP[y % K + 1][x % K + 1] -= 1
        bias += 1

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

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

ans = 0

for i in range(K + 1):
    for j in range(K + 1):
        S1 = DP[i][j] * 2 - DP[i][K] - DP[K][j] + DP[K][K]
        S2 = DP[i][K] + DP[K][j] - DP[i][j] * 2
        ans = max(ans, S1, S2)

print ans + bias

Submission status: Accepted

Solution code:
from itertools import product

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


class CumSum2d(object):
    def __init__(self, H, W):
        self.H, self.W = H, W
        self.tiles = [[0] * W for _ in range(H)]

    def add(self, x, y, c=1):
        self.tiles[y][x] += c

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

    def get(self, sx, sy, tx, ty):
        assert sx <= tx and sy <= ty
        cnt = self.tiles[ty][tx]
        if sx > 0:
            cnt -= self.tiles[ty][sx - 1]
        if sy > 0:
            cnt -= self.tiles[sy - 1][tx]
        if sx > 0 and sy > 0:
            cnt += self.tiles[sy - 1][sx - 1]
        return cnt


cs = CumSum2d(kk, kk)
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        y += K
    cs.add(x % kk, y % kk)
cs.build()

ans = 0
for x, y in product(range(K), repeat=2):
    cnt = cs.get(x, y, x + K - 1, y + K - 1)
    cnt += cs.get(x + K, y + K, kk - 1, kk - 1)
    if x > 0:
        cnt += cs.get(0, y + K, x - 1, kk - 1)
    if y > 0:
        cnt += cs.get(x + K, 0, kk - 1, y - 1)
    if x > 0 and y > 0:
        cnt += cs.get(0, 0, x - 1, y - 1)
    ans = max(ans, cnt, N - cnt)
print(ans)

Submission status: Accepted

Solution code:
def main():
  n, k = map(int, input().split())
  mp1 = [[0] * k for _ in range(k)]
  mp2 = [[0] * k for _ in range(k)]
  for _ in range(n):
    x, y, c = input().split()
    t = int(x) // k + int(y) // k
    x = int(x) % k
    y = int(y) % k
    if c == "B":
      t += 1
    if t % 2:
      mp1[y][x] += 1
    else:
      mp2[y][x] += 1
  
  mp10 = mp1[0]
  mp20 = mp2[0]
  for x in range(1, k):
    mp10[x] += mp10[x - 1]
    mp20[x] += mp20[x - 1]
  
  for y in range(1, k):
    acc1 = 0
    acc2 = 0
    mp1y = mp1[y]
    mp2y = mp2[y]
    mp1y1 = mp1[y - 1]
    mp2y1 = mp2[y - 1]
    for x in range(k):
      acc1 += mp1y[x]
      mp1y[x] = acc1 + mp1y1[x]
      acc2 += mp2y[x]
      mp2y[x] = acc2 + mp2y1[x]
  
  ans = 0
  sum1 = mp1[k - 1][k - 1]
  sum2 = mp2[k - 1][k - 1]
  mp1k = mp1[k - 1]
  mp2k = mp2[k - 1]
  for y in range(k):
    mp1y = mp1[y]
    mp1yk = mp1y[k - 1]
    mp2y = mp2[y]
    mp2yk = mp2y[k - 1]
    for x in range(k):
      mp1yx = mp1y[x]
      mp2yx = mp2y[x]
      mp1kx = mp1k[x]
      mp2kx = mp2k[x]
  
      a1 = 2 * mp1yx + sum1 - mp1yk - mp1kx + mp2kx + mp2yk - 2 * mp2yx
      a2 = 2 * mp2yx + sum2 - mp2yk - mp2kx + mp1kx + mp1yk - 2 * mp1yx
  
      if ans < a1:
        ans = a1
      if ans < a2:
        ans = a2
  
  
  print(ans)

main()