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: Wrong Answer

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def fill_2d_accum(accum, command):
        for x, y in command:
            accum[x+1][y+1] += 1
        for i in range(1,2*k+1):
            for j in range(1, 2*k+1):
                accum[i][j] += accum[i][j-1]
        for j in range(1, 2*k+1):
            for i in range(1, 2*k+1):
                accum[i][j] += accum[i-1][j]

    def calc_accum(accum, sx, tx, sy, ty):
        """[sx:tx], [sy:ty] で囲まれる領域に含まれる個数を accum を用いて計算する"""
        return accum[tx][ty] - (accum[sx][ty] + accum[tx][sy]) + accum[sx][sy]

    
    def calc_max():
        ans = -1
        for kx in range(k):
            for ky in range(k):
                b = 0
                b += calc_accum(black_2d_accum, kx, kx+k, ky, ky+k)
                b += calc_accum(black_2d_accum, 0, kx, 0, ky)
                b += calc_accum(black_2d_accum, kx+k, 2*k, 0, ky)
                b += calc_accum(black_2d_accum, 0, kx, ky+k, 2*k)
                b += calc_accum(black_2d_accum, kx+k, 2*k, ky+k, 2*k)
                ans = max(ans, b)
        return ans

    
    n, k = mi()
    command = [input().split() for _ in range(n)]
    
    black_command = []
    for x, y, c in command:
        x = int(x) % (2*k)
        y = int(y) % (2*k) if c == 'B' else (int(y) + k) % (2*k)
        black_command.append((x, y))


    black_2d_accum = [[0] * (2*k+1) for _ in range(2*k+1)]
    fill_2d_accum(black_2d_accum, black_command)
    
    # import pprint
    # pprint.pprint(black_2d_accum)

    print(calc_max())





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
 
hope = []
for i in range(N):
    a,b,c = input().split()
    a = int(a)
    b = int(b)
    if c == 'B':
        c = True
    else:
        c = False
    d = [a, b, c]
    hope.append(d)
 
import numpy as np
 
hope = np.array(hope)
    
for i in range(N):
    hope[i][0] %= (K*2)
    hope[i][1] %= (K*2)
    
for i in range(N):
    if hope[i][0] >= K:
        hope[i][0] -= K
        hope[i][2] = not(hope[i][2])
    
    if hope[i][1] >= K:
        hope[i][1] -= K
        hope[i][2] = not(hope[i][2])
        
import copy
 
color_map = []
map = []
 
for i in range(K):
    map.append(True)
 
for i in range(K):
    color_map.append(copy.deepcopy(map))
    
color_map = np.array(color_map)
    
def slice_x():
    temp = []
    for i in range(K):
        temp.append(not(color_map[i][0]))
    
    if K > 1:
        for i in range(K):
            for j in range(K-1):
                color_map[i][j] = color_map[i][j+1]
    
    for i in range(K):
        color_map[i][K-1] = temp[i]
        
    return
 
def slice_y():
    temp = np.copy(color_map[0])
    
    for i in range(K):
        temp[i] = not(temp[i])
    
    if K > 1:
        for i in range(K-1):
            color_map[i] = color_map[i+1]
            
    color_map[K-1] = temp
    
    return
  
black_map = np.zeros((K,K), int)
white_map = np.zeros((K,K), int)
 
for i in range(N):
    if hope[i][2] == True:
        black_map[hope[i][0]][hope[i][1]] += 1
    else:
        white_map[hope[i][0]][hope[i][1]] += 1
  
sati = 0
max_sati = 0
 
for k in range(K):
    for j in range(K):
        sati += np.sum(black_map * np.logical_not(np.logical_xor(color_map, black_map)))
        sati += np.sum(white_map * np.logical_not(np.logical_xor(color_map, white_map)))
 
        if int(N/2) >= sati:
            sati = N - sati
 
        if max_sati < sati:
            max_sati = sati
        
        sati = 0
            
        slice_x()
    slice_y()
    
print(max_sati)

Submission status: Wrong Answer

Solution code:
import gc
n, k = map(int, input().split())
k2 = k * 2
b = [[0] * (k * 3) for _ in range(k * 3)]
for i in range(n):
    x, y, c = input().split()
    x = int(x) % k2
    y = int(y) % k2
    if c == 'W':
        x = (x + k) % k2

    b[x][y] += 1
    if x < k:
        b[x + k2][y] += 1
    if y < k:
        b[x][y + k2] += 1
    if x < k and y < k:
        b[x + k2][y + k2] += 1

b_cs = [[0] * (k * 3 + 1) for _ in range(k * 3 + 1)]
for i in range(k * 3):
    for j in range(k * 3):
        b_cs[i + 1][j +
                    1] = b_cs[i + 1][j] + b_cs[i][j + 1] - b_cs[i][j] + b[i][j]


def func_b(x, y):
    return b_cs[x + k][y + k] - b_cs[x + k][y] - b_cs[x][y + k] + b_cs[x][y]


# print('black')
# print(*b, sep='\n')
# print(*b_cs, sep='\n')

ans = 0
for i in range(k + 1):
    for j in range(k):
        cand = 0
        cand += func_b(i, j)
        cand += func_b(i + k, j + k)
        # print(i, j, cand)
        ans = max(ans, cand)

print(ans)

Submission status: Wrong Answer

Solution code:
import gc
n, k = map(int, input().split())
k2 = k * 2
b = [[0] * (k * 3) for _ in range(k * 3)]
for i in range(n):
    x, y, c = input().split()
    x = int(x) % k2
    y = int(y) % k2
    if c == 'W':
        x = (x + k) % k2

    b[x][y] += 1
    if x < k:
        b[x + k2][y] += 1
    if y < k:
        b[x][y + k2] += 1
    if x < k and y < k:
        b[x + k2][y + k2] += 1

b_cs = [[0] * (k * 3 + 1) for _ in range(k * 3 + 1)]
for i in range(k * 3):
    for j in range(k * 3):
        b_cs[i + 1][j +
                    1] = b_cs[i + 1][j] + b_cs[i][j + 1] - b_cs[i][j] + b[i][j]


def func_b(x, y):
    return b_cs[x + k][y + k] - b_cs[x + k][y] - b_cs[x][y + k] + b_cs[x][y]


# print('black')
# print(*b, sep='\n')
# print(*b_cs, sep='\n')

ans = 0
for i in range(k + 1):
    for j in range(k + 1):
        cand = 0
        cand += func_b(i, j)
        cand += func_b(i + k, j + k)
        # print(i, j, cand)
        ans = max(ans, cand)

print(ans)

Submission status: Wrong Answer

Solution code:
import gc
n, k = map(int, input().split())
k2 = k * 2
b = [[0] * (k * 3 + 1) for _ in range(k * 3 + 1)]
for i in range(n):
    x, y, c = input().split()
    x = int(x) % k2
    y = int(y) % k2
    if c == 'W':
        x = (x + k) % k2

    b[x][y] += 1
    if x <= k:
        b[x + k2][y] += 1
    if y <= k:
        b[x][y + k2] += 1
    if x <= k and y <= k:
        b[x + k2][y + k2] += 1

b_cs = [[0] * (k * 3 + 2) for _ in range(k * 3 + 2)]
for i in range(k * 3 + 1):
    for j in range(k * 3 + 1):
        b_cs[i + 1][j +
                    1] = b_cs[i + 1][j] + b_cs[i][j + 1] - b_cs[i][j] + b[i][j]


def func_b(x, y):
    return b_cs[x + k][y + k] - b_cs[x + k][y] - b_cs[x][y + k] + b_cs[x][y]


# print('black')
# print(*b, sep='\n')
# print(*b_cs, sep='\n')

ans = 0
for i in range(k + 1):
    for j in range(k + 1):
        cand = 0
        cand += func_b(i, j)
        cand += func_b(i + k, j + k)
        # print(i, j, cand)
        ans = max(ans, cand)

print(ans)

Submission status: Wrong Answer

Solution code:
import gc
n, k = map(int, input().split())
k2 = k * 2
b = [[0] * (k * 3) for _ in range(k * 3)]
for i in range(n):
    x, y, c = input().split()
    x = int(x) % k2
    y = int(y) % k2
    if c == 'W':
        x = (x + k) % k2

    b[x][y] += 1
    if x < k:
        b[x + k2][y] += 1
    if y < k:
        b[x][y + k2] += 1
    if x < k and y < k:
        b[x + k2][y + k2] += 1

b_cs = [[0] * (k * 3 + 1) for _ in range(k * 3 + 1)]
for i in range(k * 3):
    for j in range(k * 3):
        b_cs[i + 1][j +
                    1] = b_cs[i + 1][j] + b_cs[i][j + 1] - b_cs[i][j] + b[i][j]


def func_b(x, y):
    return b_cs[x + k][y + k] - b_cs[x + k][y] - b_cs[x][y + k] + b_cs[x][y]


# print('black')
# print(*b, sep='\n')
# print(*b_cs, sep='\n')

ans = 0
for i in range(k):
    for j in range(k):
        cand = 0
        cand += func_b(i, j)
        cand += func_b(i + k, j + k)
        # print(i, j, cand)
        ans = max(ans, cand)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
k2 = k * 2
b = [[0] * (k * 3) for _ in range(k * 3)]
w = [[0] * (k * 3) for _ in range(k * 3)]
for i in range(n):
    x, y, c = input().split()
    x = int(x) % k2
    y = int(y) % k2
    if c == 'B':
        b[x][y] += 1
        if x < k:
            b[x + k2][y] += 1
        if y < k:
            b[x][y + k2] += 1
        if x < k and y < k:
            b[x + k2][y + k2] += 1
    else:
        w[x][y] += 1
        if x < k:
            w[x + k2][y] += 1
        if y < k:
            w[x][y + k2] += 1
        if x < k and y < k:
            w[x + k2][y + k2] += 1

b_cs = [[0] * (k * 3 + 1) for _ in range(k * 3 + 1)]
w_cs = [[0] * (k * 3 + 1) for _ in range(k * 3 + 1)]
for i in range(k * 3):
    for j in range(k * 3):
        b_cs[i + 1][j +
                    1] = b_cs[i + 1][j] + b_cs[i][j + 1] - b_cs[i][j] + b[i][j]
        w_cs[i + 1][j +
                    1] = w_cs[i + 1][j] + w_cs[i][j + 1] - w_cs[i][j] + w[i][j]


def func(cs, x, y):
    return cs[x + k][y + k] - cs[x + k][y] - cs[x][y + k] + cs[x][y]


ans = 0
for i in range(k):
    for j in range(k):
        cand = 0
        cand += func(b_cs, i, j)
        cand += func(b_cs, i + k, j + k)
        cand += func(w_cs, i + k, j)
        cand += func(w_cs, i, j + k)
        ans = max(ans, cand)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
xyc = [list(input().split()) for _ in range(n)]

b = np.zeros((2 * k, k), np.int64)

for x, y, c in xyc:
    x = int(x)
    y = int(y)

    q, r = divmod(x, k)
    if q % 2:
        y += k
    x = r

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

    y %= 2 * k

    b[y][x] += 1

b = np.vstack([b, b])
b = np.hstack([b, np.roll(b, k)])

b = np.pad(b, (1, 0), "constant")
b = np.cumsum(b, axis=0)
b = np.cumsum(b, axis=1)

cnt = b[k:, k:] - b[k:, :-k] - b[:-k, k:] + b[:-k, :-k]
ans = cnt.max()
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
xyc = [list(input().split()) for _ in range(n)]

b = np.zeros((2 * k, k), np.int64)

for x, y, c in xyc:
    x = int(x)
    y = int(y)

    q, r = divmod(x, k)
    if q % 2:
        y += k
    x = r

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

    y %= 2 * k

    b[y][x] += 1

tmp = np.vstack([b, b])
bb = np.hstack([tmp, np.roll(tmp, k)])

bb = np.pad(bb, (1, 0), "constant")
bb = np.cumsum(bb, axis=0)
bb = np.cumsum(bb, axis=1)

cnt = bb[k:, k:] - bb[k:, :-k] - bb[:-k, k:] + bb[:-k, :-k]
ans = cnt.max()
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
xyc = [list(input().split()) for _ in range(n)]

b = np.zeros((2 * k, k), np.int64)

for x, y, c in xyc:
    x = int(x)
    y = int(y)

    q, r = divmod(x, k)
    if q % 2:
        y += k
    x = r

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

    y %= 2 * k

    b[y][x] += 1

tmp = np.vstack([b, b[:k]])
bb = np.hstack([tmp, np.roll(tmp, k)])

bb = np.pad(bb, (1, 0), "constant")
bb = np.cumsum(bb, axis=0)
bb = np.cumsum(bb, axis=1)

cnt = bb[k:, k:] - bb[k:, :-k] - bb[:-k, k:] + bb[:-k, :-k]
ans = cnt.max()
print(ans)

Submission status: Wrong Answer

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

Map = [[[0]*K for i in range(K)] for j in range(2)]
for i in range(N):
  x, y, c = input().split()
  x, y = int(x), int(y)
  if c == 'B':
    c = 0
  else:
    c = 1
  nx, ny = -(-x)//K, -(-y)//K
  if (nx + ny) % 2:
    c = 1 - c
  x %= K
  y %= K
  Map[c][x][y] += 1

def get_v(c, x, y):
  global Map
  if x < 0 or y < 0:
    return 0
  else:
    return Map[c][x][y]

for c in range(2):
  for x in range(K):
    for y in range(K):
      Map[c][x][y] += get_v(c, x-1, y) + get_v(c, x, y-1) - get_v(c, x-1, y-1)

ans = 0

for x in range(K+1):
  for y in range(K+1):
    b = Map[0][K-1][K-1] - get_v(0, x-1, K-1) - get_v(0, K-1, y-1) + 2*get_v(0, x-1, y-1)
    w = get_v(1, x-1, K-1) + get_v(1, K-1, y-1) - 2*get_v(1, x-1, y-1)
    ans = max(ans, b+w)

print(ans)

Submission status: Wrong Answer

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

Map = [[[0]*K for i in range(K)] for j in range(2)]
for i in range(N):
  x, y, c = input().split()
  x, y = int(x), int(y)
  if c == 'B':
    c = 0
  else:
    c = 1
  nx, ny = x//K, y//K
  if (nx + ny) % 2:
    c = 1 - c
  x %= K
  y %= K
  Map[c][x][y] += 1

def get_v(c, x, y):
  global Map
  if x < 0 or y < 0:
    return 0
  else:
    return Map[c][x][y]

for c in range(2):
  for x in range(K):
    for y in range(K):
      Map[c][x][y] += get_v(c, x-1, y) + get_v(c, x, y-1) - get_v(c, x-1, y-1)

ans = 0
for x in range(K+1):
  for y in range(K+1):
    b = Map[0][K-1][K-1] - get_v(0, x-1, K-1) - get_v(0, K-1, y-1) + 2*get_v(0, x-1, y-1)
    w = get_v(1, x-1, K-1) + get_v(1, K-1, y-1) - 2*get_v(1, x-1, y-1)
    ans = max(ans, b+w)

print(ans)

Submission status: Wrong Answer

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

Map = [[[0]*K for i in range(K)] for j in range(2)]
for i in range(N):
  x, y, c = input().split()
  if c == 'B':
    c = 0
  else:
    c = 1
  x, y = int(x)%(2*K), int(y)%(2*K)
  if y >= K:
    x, y = (x + K)%(2*K), y - K
  if x >= K:
    x %= K
    c = 1 - c # 色を反転
  Map[c][x][y] += 1

def get_v(c, x, y):
  if x < 0 or y < 0:
    return 0
  else:
    return Map[c][x][y]

for c in range(2):
  for x in range(K):
    for y in range(K):
      Map[c][x][y] += get_v(c, x-1, y) + get_v(c, x, y-1) - get_v(c, x-1, y-1)

ans = 0
for x in range(K):
  for y in range(K):
    b = Map[0][K-1][K-1] - get_v(0, x-1, K-1) - get_v(0, K-1, y-1) + 2*get_v(0, x-1, y-1)
    w = get_v(1, x-1, K-1) + get_v(1, K-1, y-1) - 2*get_v(1, x-1, y-1)
    ans = max(ans, b+w)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
MAP = [[0 for i in range(2 * K + 1)] for j in range(2 * K + 1)]
for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    x %= 2 * K
    y %= 2 * K
    if c == 'W':
        x += K
        x %= 2 * K
    MAP[x+1][y+1] += 1
for i in range(2 * K):
    for j in range(2 * K):
        MAP[i+1][j+1] = MAP[i+1][j+1] + MAP[i+1][j] + MAP[i][j+1] - MAP[i][j]

ans = 0
for i in range(K+1):
    for j in range(K+1):
        cnt = 0
        cnt += MAP[i][j]
        cnt += MAP[i][2 * K] - MAP[i][j + K]
        cnt += MAP[2 * K][j] - MAP[i + K][j]
        cnt += MAP[i + K][j + K] - MAP[i][j + K] - MAP[i + K][j] + MAP[i][j]
        cnt += MAP[2 * K][2 * K] - MAP[i + K][2 * K] - MAP[2 * K][j + K] + MAP[i + K][j + K]
        ans = max(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
class Accumulate2D:
    def __init__(self, a):
        self.height = len(a)
        self.width = len(a[0])
        self.acc = self.accumulate(a)

    def accumulate(self,a):
        b = [[0]*(self.width+1) for i in range(self.height+1)]
        b[1][1] = a[0][0]
        for i in range(self.height):
            for j in range(self.width):
                b[i+1][j+1] = b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
        return b

    def sum(self, p, q):
        y1,x1 = p
        y2,x2 = q
        b = self.acc
        if y1>y2 or x1>x2:
            return 0
        else:
            return b[y2+1][x2+1]-b[y2+1][x1]-b[y1][x2+1]+b[y1][x1]


n,k = map(int, input().split())

kk = k*2
k3 = k*3

z = [[0]*k3 for i in range(k3)]

for i in range(n):
    x,y,c = input().split()
    x = int(x) % kk
    y = int(y) % kk
    if c=='W':
        x = (x+k)%kk
    for a in [0,1]:
        for b in [0,1]:
            if x+a*kk<k3 and y+b*kk<k3:
                z[x+a*kk][y+b*kk]+=1


z = Accumulate2D(z)

ans = 0
for i in range(k):
    for j in range(k):
        a = z.sum([i,j],[i+k-1,j+k-1])\
            + z.sum([i+k,j+k],[i+kk-1,j+kk-1])
        ans = max(ans,a)

print(ans)

Submission status: Wrong Answer

Solution code:
class Accumulate2D:
    def __init__(self, a):
        self.height = len(a)
        self.width = len(a[0])
        self.acc = self.accumulate(a)

    def accumulate(self,a):
        b = [[0]*(self.width+1) for i in range(self.height+1)]
        b[1][1] = a[0][0]
        for i in range(self.height):
            for j in range(self.width):
                b[i+1][j+1] = b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
        return b

    def sum(self, p, q):
        y1,x1 = p
        y2,x2 = q
        b = self.acc
        if y1>y2 or x1>x2:
            return 0
        else:
            return b[y2+1][x2+1]-b[y2+1][x1]-b[y1][x2+1]+b[y1][x1]


n,k = map(int, input().split())

kk = k*2
k3 = k*4

z = [[0]*k3 for i in range(k3)]

for i in range(n):
    x,y,c = input().split()
    x = int(x) % kk
    y = int(y) % kk
    if c=='W':
        x = (x+k)%kk
    for a in [0,1]:
        for b in [0,1]:
            if x+a*kk<k3 and y+b*kk<k3:
                z[x+a*kk][y+b*kk]+=1


z = Accumulate2D(z)

ans = 0
for i in range(k):
    for j in range(k):
        a = z.sum([i,j],[i+k-1,j+k-1])\
            + z.sum([i+k,j+k],[i+kk-1,j+kk-1])
        ans = max(ans,a)

print(ans)

Submission status: Wrong Answer

Solution code:
def double_accumulate(a):
    h = len(a)
    w = len(a[0])
    b = [[0]*(w+1) for i in range(h+1)]
    b[1][1] = a[0][0]
    for i in range(h):
        for j in range(w):
            b[i+1][j+1] = b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
    return b


def double_sum(b,p,q):
    y1,x1 = p
    y2,x2 = q
    if y1>y2 or x1>x2:
        return 0
    else:
        return b[y2+1][x2+1]-b[y2+1][x1]-b[y1][x2+1]+b[y1][x1]


n,k = map(int, input().split())

kk = k*2
k4 = k*4

black = [[0]*k4 for i in range(k4)]
white = [[0]*k4 for i in range(k4)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)%kk
    y = int(y)%kk
    if c == 'B':
        for a in [0,1]:
            for b in [0,1]:
                black[x+a*kk][y+b*kk]+=1
    else:
        for a in [0,1]:
            for b in [0,1]:
                white[x+a*kk][y+b*kk]+=1

B = double_accumulate(black)
W = double_accumulate(white)

ans = 0
for i in range(k):
    for j in range(k):
        b = double_sum(B,[i,j],[i+k-1,j+k-1])\
            + double_sum(B,[i+k,j+k],[i+kk-1,j+kk-1])
        w = double_sum(W,[i,j+k],[i+k-1,j+kk-1])\
            + double_sum(W,[i+k,j],[i+kk-1,j+k-1])
        ans = max(ans,b+w)

print(ans)

Submission status: Wrong Answer

Solution code:
def double_accumulate(a):
    h = len(a)
    w = len(a[0])
    b = [[0]*(w+1) for i in range(h+1)]
    b[1][1] = a[0][0]
    for i in range(h):
        for j in range(w):
            b[i+1][j+1] = b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
    return b

def double_sum(b,p,q):
    y1,x1 = p
    y2,x2 = q
    if y1>y2 or x1>x2:
        return 0
    else:
        return b[y2+1][x2+1]-b[y2+1][x1]-b[y1][x2+1]+b[y1][x1]

n,k = map(int, input().split())

kk = k*2

black = [[0]*kk for i in range(kk)]
white = [[0]*kk for i in range(kk)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)%kk
    y = int(y)%kk
    if c == 'B':
        black[x][y]+=1
    else:
        white[x][y]+=1

B = double_accumulate(black)
W = double_accumulate(white)

ans = 0
for i in range(k):
    for j in range(k):
        b = double_sum(B,[0,0],[i-1,j-1])\
            + double_sum(B,[i,j],[i+k-1,j+k-1])\
            + double_sum(B,[0,j+k],[i-1,kk-1])\
            + double_sum(B,[i+k,0],[kk-1,j-1])\
            + double_sum(B,[i+k,j+k],[kk-1,kk-1])

        w = double_sum(W,[0,j],[i-1,j+k-1])\
            + double_sum(W,[i,0],[i+k-1,j-1])\
            + double_sum(W,[i,j+k],[i+k-1,kk-1])\
            + double_sum(W,[i+k,j],[kk-1,j+k-1])

        ans = max(ans,b+w)

print(ans)

Submission status: Wrong Answer

Solution code:
def double_accumulate(a):
    h = len(a)
    w = len(a[0])
    b = [[0]*(w+1) for i in range(h+1)]
    b[1][1] = a[0][0]
    for i in range(h):
        for j in range(w):
            b[i+1][j+1] = b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]
    return b


def double_sum(b,p,q):
    return b[q[0]+1][q[1]+1]-b[q[0]+1][p[1]]-b[p[0]][q[1]+1]+b[p[0]][p[1]]

n,k = map(int, input().split())

kk = k*2

black = [[0]*kk for i in range(kk)]
white = [[0]*kk for i in range(kk)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)%kk
    y = int(y)%kk
    if c == 'B':
        black[x][y]+=1
    else:
        white[x][y]+=1

B = double_accumulate(black)
W = double_accumulate(white)

ans = 0
for i in range(k):
    for j in range(k):
        b = double_sum(B,[0,0],[i-1,j-1]) + double_sum(B,[i,j],[i+k-1,j+k-1]) + double_sum(B,[0,j+k],[i-1,kk-1]) + double_sum(B,[i+k,0],[kk-1,j-1]) + double_sum(B,[i+k,j+k],[kk-1,kk-1])
        w = double_sum(W,[0,j],[i-1,j+k-1]) + double_sum(W,[i,0],[i+k-1,j-1]) + double_sum(W,[i,j+k],[i+k-1,kk-1]) + double_sum(W,[i+k,j],[kk-1,j+k-1])
        ans = max(ans,b+w)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
X = [input().split() for _ in range(N)]

grid = [[0] * (2 * K + 1) for _ in range(2 * K + 1)]
for x, y, c in X:
    x, y = map(int, [x, y])
    if c == "W":
        y += K
    grid[x % (2 * K) + 1][y % (2 * K) + 1] += 1
        
for i in range(2 * K):
    for j in range(2 * K):
        grid[i + 1][j + 1] += grid[i][j + 1]

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

def count(x, y, i, j):
    return grid[x][y] + grid[i][j] - grid[x][j] - grid[i][y]

ans = 0
for i in range(K):
    for j in range(K):
        tmp = 0
        tmp += count(i + K, j + K, i, j)
        tmp += count(i, j, 0, 0)
        tmp += count(i, 2 * K, 0, j + K)
        tmp += count(2 * K, j, i + K, 0)
        tmp += count(2 * K, 2 * K, i + K, j + K)
    ans = max(ans, tmp, N - tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
blacks = [[0 for _ in range(2*K)] for _ in range(2*K)]

for i in range(N):
    x_, y_, c = map(str, input().split())
    x = (int(x_) + (c=='W')*K)% (2*K)
    y = int(y_) % (2*K)

    blacks[x][y] += 1
    blacks[(x+K)%(2*K)][y] -= 1
    blacks[x][(y+K)%(2*K)] -= 1
    blacks[(x+K)%(2*K)][(y+K)%(2*K)] += 1
    if x >= K:
        blacks[0][y] += 1
    if y >= K:
        blacks[x][0] += 1



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

ans = 0
for i in range(K):
    for j in range(K):
        curr = blacks[i+K][j+K]

Submission status: Wrong Answer

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

n, k = map(int,input().split())
C = [list(input().split()) for i in range(n)]
D = [[0] * (2*k) for i in range(2*k)]

E = []
for i in range(n):
    x = int(C[i][0]) % (2*k)
    y = int(C[i][1]) % (2*k)
    if C[i][2] == "W":
        x = (x+k) % (2*k)
    E.append([x, y])
    x = (x+k) % (2*k)
    y = (y+k) % (2*k)
    E.append([x, y])

for i in range(2*n):
    xx = 0
    yy = 0
    x = E[i][0]
    y = E[i][1]

    D[x][y] += 1
    if x+k > 2*k:
        xx = 1
    if y+k > 2*k:
        yy = 1
    if xx == 1 and yy == 1:
        D[0][0] += 1
        D[x-k][0] -= 1
        D[0][y-k] -= 1
        D[x-k][y-k] += 1
    elif xx == 1:
        D[0][y] += 1
        D[x-k][y] -= 1
        if y != k:
            D[x][y+k] -= 1
            D[0][y+k] -= 1
            D[x-k][y+k] += 1
    elif yy == 1:
        D[x][0] += 1
        D[x][y-k] -= 1
        if x != k:
            D[x+k][y] -= 1
            D[x+k][0] -= 1
            D[x+k][y-k] += 1
    else:
        if x != k:
            D[x+k][y] -= 1
        if y != k:
            D[x][y+k] -= 1
        if x != k and y != k:
            D[x+k][y+k] += 1
    # print(D)
    
for i in range(1, 2*k):
    D[0][i] += D[0][i-1]
    D[i][0] += D[i-1][0]

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

print(max([max(D[i]) for i in range(2*k)]))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
b=[(2*k+1)*[0]for _ in range(2*k+1)]
def add(i,j):
  global b
  b[min(max(1,i+1),2*k)][min(max(1,j+1),2*k)]+=1
  b[min(max(1,i+1+k),2*k)][min(max(1,j+1+k),2*k)]+=1
  b[min(max(1,i+1+k),2*k)][min(max(1,j+1),2*k)]-=1
  b[min(max(1,i+1),2*k)][min(max(1,j+1+k),2*k)]-=1
for _ in range(n):
  x,y,c=input().split()
  x=int(x)
  y=int(y)
  if c=="B":y+=k
  x%=2*k
  y%=2*k
  add(x,y)
  add(x+k,y+k)
  add(x+k,y-k)
  add(x-k,y+k)
  add(x-k,y-k)
  add(x+2*k,y)
  add(x-2*k,y)
  add(x,y+2*k)
  add(x,y-2*k)
ans=0
for i in range(1,2*k+1):
  for j in range(1,2*k+1):
    b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]
    ans=max(ans,b[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
b=[(2*k+1)*[0]for _ in range(2*k+1)]
def add(i,j):
  global b
  b[min(max(1,i+1),2*k)][min(max(1,j+1),2*k)]+=1
  b[min(max(1,i+1+k),2*k)][min(max(1,j+1+k),2*k)]+=1
  b[min(max(1,i+1+k),2*k)][min(max(1,j+1),2*k)]-=1
  b[min(max(1,i+1),2*k)][min(max(1,j+1+k),2*k)]-=1
for _ in range(n):
  x,y,c=input().split()
  x=int(x)
  y=int(y)
  if c=="B":y+=k
  x%=2*k
  y%=2*k
  add(x-2*k,y)
  add(x-k,y-k)
  add(x,y-2*k)
  add(x+k,y-k)
  add(x+2*k,y)
  add(x+k,y+k)
  add(x,y+2*k)
  add(x-k,y+k)
  add(x,y)
ans=0
for i in range(1,2*k+1):
  for j in range(1,2*k+1):
    b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]
    ans=max(ans,b[i][j])
print(ans)

Submission status: Wrong Answer

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

cntH = [[0] * K for _ in range(K)]
cntW = [[0] * K for _ in range(K)]
for _ in range(N):
    x, y, c = map(str, input().split())
    x = int(x); y = int(y)
    
    if c == "W":
        cntW[y % K][x % K] += 1
    else:
        cntH[y % K][x % K] += 1

# 二次元累積和
for i in range(1, K):
    cntH[0][i] += cntH[0][i - 1]
    cntW[0][i] += cntW[0][i - 1]
    cntH[i][0] += cntH[i - 1][0]
    cntW[i][0] += cntW[i - 1][0]
for i in range(1, K):
    for j in range(1, K):
        cntH[i][j] += cntH[i - 1][j] + cntH[i][j - 1]
        cntW[i][j] += cntW[i - 1][j] + cntW[i][j - 1]

ans = 0
for i in range(K):
    for j in range(K):
        cnt1 = 0
        cnt2 = 0

        # 左上
        if i != 0 and j != 0:
            cnt1 += cntW[i - 1][j - 1]
            cnt2 += cntH[i - 1][j - 1]
        # 左下(白)
        if i != K - 1 and j != 0:
            cnt1 += cntH[K - 1][j - 1]
            cnt2 += cntW[K - 1][j - 1]
            if i != 0:
                cnt1 -= cntH[i - 1][j - 1]
                cnt2 -= cntW[i - 1][j - 1]
        # 右下(黒)
        if i != K - 1 and j != K - 1:
            cnt1 += cntW[K - 1][K - 1]
            cnt2 += cntH[K - 1][K - 1]
            if i != 0:
                cnt1 -= cntW[i - 1][K - 1]
                cnt2 -= cntH[i - 1][K - 1]
            if j != 0:
                cnt1 -= cntW[K - 1][j - 1]
                cnt2 -= cntH[K - 1][j - 1]
            if i != 0 and j != 0:
                cnt1 += cntW[i - 1][j - 1]
                cnt2 += cntH[i - 1][j - 1]
        # 右上(白)
        if i != 0 and j != K - 1:
            cnt1 += cntH[i - 1][K - 1]
            cnt2 += cntW[i - 1][K - 1]
            if j != 0:
                cnt1 -= cntH[i - 1][j - 1]
                cnt2 -= cntW[i - 1][j - 1]
        
        ans = max(ans, cnt1, cnt2)

print(ans)