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:
# 2K * 2Kの正方形で一周するので、
# (X,Y) -> (X % 2K, Y % 2K)に言い換えることが出来る
# Wの表とBの表を別々で持つ
# それぞれの表で二次元累積和を持ち、範囲に対する得点を求められるようにする
# 黒いK * Kの正方形の左下隅を1000 * 1000通り全探索して最大値を求める

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
white = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
black = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
# 黒を数えるときは、同時に白を数えて、白全体の数から引く
white_all = 0
black_all = 0
for i in range(N):
  x,y,c = readline().split()
  x,y = int(x) % (2 * K),int(y) % (2 * K)
  if c == "W":
    white[x + 1][y + 1] += 1
    white_all += 1
  else:
    black[x + 1][y + 1] += 1
    black_all += 1
  
for i in range(1, len(white)):
  for j in range(1, len(white[i])):
    white[i][j] += white[i][j - 1]
    
for j in range(1, len(white)):
  for i in range(1, len(white[j])):
    white[i][j] += white[i - 1][j]

for i in range(1, len(black)):
  for j in range(1, len(black[i])):
    black[i][j] += black[i][j - 1]
    
for j in range(1, len(black)):
  for i in range(1, len(black[j])):
    black[i][j] += black[i - 1][j]


# cases = ((0,0),(K,K),(-K,-K),(K,-K),(-K,K),(-K * 2,-K * 2),(K * 2,K * 2),(-K * 2,0),(K * 2,0),(0,K * 2),(0,-K * 2))
cases = ((0,0),(K,K),(-K,-K),(K,-K),(-K,K))
ans = 0
#test = {}

#for i in range(1, 2 * K + 1):
#  for j in range(1, 2 * K + 1):
#    test[(i,j)] = False
  
for i in range(1, K + 1):
  for j in range(1, K + 1):
#    check = False
#    if i == 2 and j == 3:
#      check = True
    # 基本となる黒の正方形の左下隅・右上は以下の通り
    # (i,j),(i + K - 1, j + K - 1)
    # これに対して、
    # i,jともに +Kしたもの
    # i,jともに -Kしたもの
    # iは+K,jは-Kしたもの
    # iは-K,jは+Kしたもの
    # が考えられる範囲となる
    # なお、最小値は1,1、最大値は2 * K,2 * Kとなる
    black_cnt = 0
    white_cnt = 0
    for c in cases:
      x1 = i + c[0]
      y1 = j + c[1]
      x2 = x1 + K - 1
      y2 = y1 + K - 1
#      if check:
#        print("before",x1,y1,x2,y2)
        
#      if x2 <= 0 or y2 <= 0:
#        continue
#      if x2 >= 2 * K + 1 or y2 >= 2 * K + 1:
#        continue
      x1 = max(1, x1)
      y1 = max(1, y1)
      x2 = min(2 * K, x2)
      y2 = min(2 * K, y2)
#      if check:
#        print("after",x1,y1,x2,y2)
      if x1 > x2 or y1 > y2:
        continue
        
      # その領域の黒と白の数を数える
      black_cnt += black[x2][y2] - black[x2][y1 - 1] - black[x1 - 1][y2] + black[x1 - 1][y1 - 1]
      white_cnt += white[x2][y2] - white[x2][y1 - 1] - white[x1 - 1][y2] + white[x1 - 1][y1 - 1]
      
#      test[(x1,y1)] = True
      
    point = max(black_cnt + (white_all - white_cnt),white_cnt + (black_all - black_cnt))
    if ans < point:
      ans = point
    
#for key,value in test.items():
#  if not value:
#    print(key)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
_3K = 3 * K
_2K = 2 * K
G = np.zeros((_2K, _3K), dtype='int64') # 後から 2K * K に圧縮する
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    # 2K * 2K の黒の希望に置き換え
    if c == 'B':
        x = x % _2K
        y = y % _2K
    else:
        x = (x + K) % _2K
        y = y % _2K
    # さらに、 2K * K の黒の希望に圧縮する
    if (y >= K) and (x >= K):
        x -= K
        y -= K
    if (y >= K) and (x < K):
        x += K
        y -= K
    # 塗り方は右下がどのマスに来るかの 2K * K 通り
    # → 最終的に 2K * K のグリッドで表すことができる
    # 各希望を満たす塗り方は K * K 通り
    # → 2K * K のグリッド内の希望を満たす K * K マスに 1 を加算すれば、
    #   全希望の加算後には各マス＝各塗り方がいくつの希望を満たすかがわかる
    # K * K マスに 1 を加算するには o(K^2) かかってしまう
    # → いもす法を使う
    # 塗り方を 3K * 2K の範囲で考えて累積和をとった後、 2K * K の範囲に圧縮する
    G[y, x] += 1
    G[y+K, x+K] += 1
    G[y+K, x] -= 1
    G[y, x+K] -= 1

# 3K * 2K の範囲の累積和をとる
G = G.cumsum(axis=1).cumsum(axis=0)
# 2K * K の範囲に圧縮
G = G[:K, :_2K] + G[K:_2K, K:_3K] + np.concatenate((G[:K, _2K:_3K], G[K:_2K, :K]), axis=1)
ans = G.max()
print(ans)

Submission status: Accepted

Solution code:
import sys
from pprint import *
N,K=map(int,input().split())
input=sys.stdin.readline
dpb=[[0 for _ in range(2*K+1)] for _ in range(2*K+1)]
def getmatnum(x1,y1,x2,y2,mat):#左上を(x1,y1)右下を(x2,y2)にしてmatの中の左上~右下の領域の和を算出
    return mat[y2][x2]-mat[y1][x2]-mat[y2][x1]+mat[y1][x1]

for i in range(N):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    #print(x,y,c)
    if c=="W":
        dpb[(y%(2*K))+1][((x+K)%(2*K))+1]=dpb[(y%(2*K))+1][((x+K)%(2*K))+1]+1
    else:
        dpb[(y % (2*K))+1][(x % (2*K))+1] = dpb[(y % (2*K))+1][(x % (2*K))+1] + 1
#pprint(dpw)
#pprint(dpb)

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

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

ans=0
for i in range(K):
    for j in range(K):
        k=i+K
        l=j+K
        b1=getmatnum(0,0,i,j,dpb)+getmatnum(k,0,2*K,j,dpb)+getmatnum(i,j,k,l,dpb)+getmatnum(0,l,i,2*K,dpb)+getmatnum(k,l,2*K,2*K,dpb)
        b2=getmatnum(i,0,k,j,dpb)+getmatnum(0,j,i,l,dpb)+getmatnum(k,j,2*K,l,dpb)+getmatnum(i,l,k,2*K,dpb)
        ans=max(ans,b1,b2)

        #print(i,j,k,l)
print(ans)
        #
#pprint(dpw)
#pprint(dpb)

Submission status: Accepted

Solution code:
import sys
from pprint import *
N,K=map(int,input().split())
input=sys.stdin.readline
dpb=[[0 for _ in range(2*K+1)] for _ in range(2*K+1)]
def getmatnum(x1,y1,x2,y2,mat):#左上を(x1,y1)右下を(x2,y2)にしてmatの中の左上~右下の領域の和を算出
    if (x2==0)or(y2==0):
        return 0
    else:
        if (x1==-1):
            x1=0
        if (y1==-1):
            y1=0
        return mat[y2][x2]-mat[y1][x2]-mat[y2][x1]+mat[y1][x1]

for i in range(N):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    #print(x,y,c)
    if c=="W":
        dpb[(y%(2*K))+1][((x+K)%(2*K))+1]=dpb[(y%(2*K))+1][((x+K)%(2*K))+1]+1
    else:
        dpb[(y % (2*K))+1][(x % (2*K))+1] = dpb[(y % (2*K))+1][(x % (2*K))+1] + 1
#pprint(dpw)
#pprint(dpb)

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

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

ans=0
for i in range(K):
    for j in range(K):
        k=i+K
        l=j+K
        b1=getmatnum(-1,-1,i,j,dpb)+getmatnum(k,-1,2*K,j,dpb)+getmatnum(i,j,k,l,dpb)+getmatnum(-1,l,i,2*K,dpb)+getmatnum(k,l,2*K,2*K,dpb)
        b2=getmatnum(i,-1,k,j,dpb)+getmatnum(-1,j,i,l,dpb)+getmatnum(k,j,2*K,l,dpb)+getmatnum(i,l,k,2*K,dpb)
        ans=max(ans,b1,b2)

        #print(i,j,k,l)
print(ans)
        #
#pprint(dpw)
#pprint(dpb)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
X, Y, C = [], [], []
for _ in range(n):
  x, y, c = input().split()
  X.append(int(x)%(2*k))
  Y.append(int(y)%(2*k))
  C.append(c=="B")
G = [[0]*k for _ in range(k)]
cnt = 0
for x, y, c in zip(X, Y, C):
  if (x >= k and y < k) or (x < k and y >= k):
    x += k
    c ^= 1
  x %= k
  y %= k
  G[x][y] += (-1)**c
  cnt += c
for i in range(k):
  for j in range(k-1):
    G[i][j+1] += G[i][j]
for j in range(k):
  for i in range(k-1):
    G[i+1][j] += G[i][j]
ans = 0
for i in range(k):
  for j in range(k):
    temp = G[k-1][k-1] - G[i][k-1] - G[k-1][j] + G[i][j]*2 + cnt
    ans = max(ans, temp, n-temp)
print(ans)

Submission status: Accepted

Solution code:
def calc(lx,ly,rx,ry):
  if rx<0 or ry<0 or lx>rx or ly>ry:
    return 0
  ret=acum[ry*2*k+rx]
  if lx!=0:
    ret-=acum[ry*2*k+lx-1]
  if ly!=0:
    ret-=acum[(ly-1)*2*k+rx]
  if lx!=0 and ly!=0:
    ret+=acum[(ly-1)*2*k+lx-1]
  return ret

n,k=map(int,input().split())
board=[0]*(4*k*k)
acum=[0]*(4*k*k)
for _ in range(n):
  x,y,c=input().split()
  x,y=int(x)%(2*k),int(y)%(2*k)
  if c=='B':
    board[y*2*k+x]+=1
  if c=='W':
    y+=k
    y%=2*k
    board[y*2*k+x]+=1
for i in range(2*k):
  for j in range(2*k):
    acum[i*2*k+j]=board[i*2*k+j]
    if i!=0:
      acum[i*2*k+j]+=acum[(i-1)*2*k+j]
    if j!=0:
      acum[i*2*k+j]+=acum[i*2*k+j-1]
    if i!=0 and j!=0:
      acum[i*2*k+j]-=acum[(i-1)*2*k+j-1]
ans=0
for i in range(k):
  for j in range(k):
    tmp1=0
    lx,ly=i,j
    rx,ry=lx+k-1,ly+k-1
    #1個目のマス
    tmp1+=calc(lx,ly,rx,ry)
    #左上のマス
    tlx,tly=0,0
    trx,ttry=lx-1,ly-1
    tmp1+=calc(tlx,tly,trx,ttry)
    #右上のマス
    tlx,tly=rx+1,0
    trx,ttry=2*k-1,ly-1
    tmp1+=calc(tlx,tly,trx,ttry)
    #左下のマス
    tlx,tly=0,ry+1
    trx,ttry=lx-1,2*k-1
    tmp1+=calc(tlx,tly,trx,ttry)
    #右下のマス
    tlx,tly=rx+1,ry+1
    trx,ttry=2*k-1,2*k-1
    tmp1+=calc(tlx,tly,trx,ttry)
    tmp2=0
    #上のマス
    tlx,tly=lx,0
    trx,ttry=rx,ly-1
    tmp2+=calc(tlx,tly,trx,ttry)
    #左のマス
    tlx,tly=0,ly
    trx,ttry=lx-1,ry
    tmp2+=calc(tlx,tly,trx,ttry)
    #右のマス
    tlx,tly=rx+1,ly
    trx,ttry=2*k-1,ry
    tmp2+=calc(tlx,tly,trx,ttry)
    #下のマス
    tlx,tly=lx,ry+1
    trx,ttry=rx,2*k-1
    tmp2+=calc(tlx,tly,trx,ttry)
    ans=max(ans,tmp1,tmp2)
print(ans)

Submission status: Accepted

Solution code:
def calcb(lx,ly,rx,ry):
  if rx<0 or ry<0 or lx>rx or ly>ry:
    return 0
  ret=acum1[ry*2*k+rx]
  if lx!=0:
    ret-=acum1[ry*2*k+lx-1]
  if ly!=0:
    ret-=acum1[(ly-1)*2*k+rx]
  if lx!=0 and ly!=0:
    ret+=acum1[(ly-1)*2*k+lx-1]
  return ret

def calcw(lx,ly,rx,ry):
  if rx<0 or ry<0 or lx>rx or ly>ry:
    return 0
  ret=acum2[ry*2*k+rx]
  if lx!=0:
    ret-=acum2[ry*2*k+lx-1]
  if ly!=0:
    ret-=acum2[(ly-1)*2*k+rx]
  if lx!=0 and ly!=0:
    ret+=acum2[(ly-1)*2*k+lx-1]
  return ret

n,k=map(int,input().split())
board1=[0]*(4*k*k)
board2=[0]*(4*k*k)
acum1=[0]*(4*k*k)
acum2=[0]*(4*k*k)
for _ in range(n):
  x,y,c=input().split()
  x,y=int(x)%(2*k),int(y)%(2*k)
  if c=='B':
    board1[y*2*k+x]+=1
  if c=='W':
    board2[y*2*k+x]+=1
for i in range(2*k):
  for j in range(2*k):
    acum1[i*2*k+j]=board1[i*2*k+j]
    acum2[i*2*k+j]=board2[i*2*k+j]
    if i!=0:
      acum1[i*2*k+j]+=acum1[(i-1)*2*k+j]
      acum2[i*2*k+j]+=acum2[(i-1)*2*k+j]
    if j!=0:
      acum1[i*2*k+j]+=acum1[i*2*k+j-1]
      acum2[i*2*k+j]+=acum2[i*2*k+j-1]
    if i!=0 and j!=0:
      acum1[i*2*k+j]-=acum1[(i-1)*2*k+j-1]
      acum2[i*2*k+j]-=acum2[(i-1)*2*k+j-1]
ans=0
for i in range(k):
  for j in range(k):
    tmp1=0
    tmp2=0
    lx,ly=i,j
    rx,ry=lx+k-1,ly+k-1
    #1個目のマス
    tmp1+=calcb(lx,ly,rx,ry)
    tmp2+=calcw(lx,ly,rx,ry)
    #左上のマス
    tlx,tly=0,0
    trx,ttry=lx-1,ly-1
    tmp1+=calcb(tlx,tly,trx,ttry)
    tmp2+=calcw(tlx,tly,trx,ttry)
    #右上のマス
    tlx,tly=rx+1,0
    trx,ttry=2*k-1,ly-1
    tmp1+=calcb(tlx,tly,trx,ttry)
    tmp2+=calcw(tlx,tly,trx,ttry)
    #左下のマス
    tlx,tly=0,ry+1
    trx,ttry=lx-1,2*k-1
    tmp1+=calcb(tlx,tly,trx,ttry)
    tmp2+=calcw(tlx,tly,trx,ttry)
    #右下のマス
    tlx,tly=rx+1,ry+1
    trx,ttry=2*k-1,2*k-1
    tmp1+=calcb(tlx,tly,trx,ttry)
    tmp2+=calcw(tlx,tly,trx,ttry)
    #上のマス
    tlx,tly=lx,0
    trx,ttry=rx,ly-1
    tmp1+=calcw(tlx,tly,trx,ttry)
    tmp2+=calcb(tlx,tly,trx,ttry)
    #左のマス
    tlx,tly=0,ly
    trx,ttry=lx-1,ry
    tmp1+=calcw(tlx,tly,trx,ttry)
    tmp2+=calcb(tlx,tly,trx,ttry)
    #右のマス
    tlx,tly=rx+1,ly
    trx,ttry=2*k-1,ry
    tmp1+=calcw(tlx,tly,trx,ttry)
    tmp2+=calcb(tlx,tly,trx,ttry)
    #下のマス
    tlx,tly=lx,ry+1
    trx,ttry=rx,2*k-1
    tmp1+=calcw(tlx,tly,trx,ttry)
    tmp2+=calcb(tlx,tly,trx,ttry)
    ans=max(ans,tmp1,tmp2)
print(ans)

Submission status: Accepted

Solution code:
def main():

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

    C = [[0]*(2*k) for _ in range(2*k)]

    for i in range(n):
        x, y, c = map(str, input().split())
        x, y = int(x), int(y)
        if c == 'W':
            y += k
        C[y%(2*k)][x%(2*k)] += 1

    #print(C)
    s = [[0]*(2*k+1) for _ in range(2*k+1)]
    for i in range(2*k):
        for j in range(2*k):
            s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + C[i][j]

    #print(s)

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

    ans = 0
    for i in range(k):
        for j in range(k):
            temp = 0
            temp += count(0, j, 0, i)
            temp += count(j, j+k, i, i+k)
            temp += count(0, j, i+k, 2*k)
            temp += count(j+k, 2*k, 0, i)
            temp += count(j+k, 2*k, i+k, 2*k)
            ans = max(ans, max(temp, n-temp))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

C = [[0]*(2*k) for _ in range(2*k)]

for i in range(n):
    x, y, c = map(str, input().split())
    x, y = int(x), int(y)
    if c == 'W':
        y += k
    C[y%(2*k)][x%(2*k)] += 1

#print(C)
s = [[0]*(2*k+1) for _ in range(2*k+1)]
for i in range(2*k):
    for j in range(2*k):
        s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + C[i][j]

#print(s)

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

ans = 0
for i in range(k):
    for j in range(k):
        temp = 0
        temp += count(0, j, 0, i)
        temp += count(j, j+k, i, i+k)
        temp += count(0, j, i+k, 2*k)
        temp += count(j+k, 2*k, 0, i)
        temp += count(j+k, 2*k, i+k, 2*k)
        ans = max(ans, max(temp, n-temp))
print(ans)

Submission status: Accepted

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

N,K = list(map(int,input().split()))
data = [list(map(str, input().split())) for _ in range(N)]
base = 10**6

BW_data = [[0 for i in range(2*K)] for i in range(2*K)]

for x,y,c in data:
  x,y = int(x)%(2*K),int(y)%(2*K)
  if c == "B":
    BW_data[y][x] += 1
  else:
    BW_data[y][x] += base

def ACC2(l):
  H = len(l)
  W = len(l[0])
  ret = [[0]*(W+1) for i in range(H+1)]
  for i in range(H):
    for j in range(W):
      ret[i+1][j+1] = ret[i+1][j] + ret[i][j+1] - ret[i][j] + l[i][j]
  return ret

def RANGE_SUM_in_ACC(l,h1,h2,w1,w2):
  return l[h2][w2]-l[h2][w1]-l[h1][w2]+l[h1][w1]

BW_ACC = ACC2(BW_data)

BW_res = [[0 for i in range(2*K)] for i in range(K)]

for j in range(K):
  for i in range(2*K):
    if i<K:
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,j,j+K,i,i+K)
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,0,max(0,j),0,max(0,i))
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,0,max(0,j),min(2*K,i+K),2*K)
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,min(2*K,j+K),2*K,0,max(0,i))
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,min(2*K,j+K),2*K,min(2*K,i+K),2*K)
    else:
      BW_res[j][i] = BW_ACC[-1][-1]-BW_res[j][i-K]
      
ans = 0
for j in range(K):
  for i in range(2*K):
    ans = max(ans,BW_res[j][i]%base+BW_res[j][(i+K)%(2*K)]//base)
print(ans)

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
data = [list(map(str, input().split())) for _ in range(N)]
base = 10**6

BW_data = [[0 for i in range(2*K)] for i in range(2*K)]

for x,y,c in data:
  x,y = int(x)%(2*K),int(y)%(2*K)
  if c == "B":
    BW_data[y][x] += 1
  else:
    BW_data[y][x] += base

def ACC2(l):
  H = len(l)
  W = len(l[0])
  ret = [[0]*(W+1) for i in range(H+1)]
  for i in range(H):
    for j in range(W):
      ret[i+1][j+1] = ret[i+1][j] + ret[i][j+1] - ret[i][j] + l[i][j]
  return ret

def RANGE_SUM_in_ACC(l,h1,h2,w1,w2):
  return l[h2][w2]-l[h2][w1]-l[h1][w2]+l[h1][w1]

BW_ACC = ACC2(BW_data)

BW_res = [[0 for i in range(2*K)] for i in range(K)]

for j in range(K):
  for i in range(2*K):
    if i<K:
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,j,j+K,i,i+K)
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,0,max(0,j),0,max(0,i))
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,0,max(0,j),min(2*K,i+K),2*K)
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,min(2*K,j+K),2*K,0,max(0,i))
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,min(2*K,j+K),2*K,min(2*K,i+K),2*K)
    else:
      BW_res[j][i] = BW_ACC[-1][-1]-BW_res[j][i-K]
      
ans = 0
for j in range(K):
  for i in range(2*K):
    ans = max(ans,BW_res[j][i]%base+BW_res[j][(i+K)%(2*K)]//base)
print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

#############
# Main Code #
#############

N,K = IL()
data = SLL(N)
base = 10**6

BW_data = [[0 for i in range(2*K)] for i in range(2*K)]

for x,y,c in data:
  x,y = int(x)%(2*K),int(y)%(2*K)
  if c == "B":
    BW_data[y][x] += 1
  else:
    BW_data[y][x] += base

def ACC2(l):
  H = len(l)
  W = len(l[0])
  ret = [[0]*(W+1) for i in range(H+1)]
  for i in range(H):
    for j in range(W):
      ret[i+1][j+1] = ret[i+1][j] + ret[i][j+1] - ret[i][j] + l[i][j]
  return ret

def RANGE_SUM_in_ACC(l,h1,h2,w1,w2):
  return l[h2][w2]-l[h2][w1]-l[h1][w2]+l[h1][w1]

BW_ACC = ACC2(BW_data)

BW_res = [[0 for i in range(2*K)] for i in range(K)]

for j in range(K):
  for i in range(2*K):
    if i<K:
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,j,j+K,i,i+K)
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,0,max(0,j),0,max(0,i))
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,0,max(0,j),min(2*K,i+K),2*K)
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,min(2*K,j+K),2*K,0,max(0,i))
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,min(2*K,j+K),2*K,min(2*K,i+K),2*K)
    else:
      BW_res[j][i] = BW_ACC[-1][-1]-BW_res[j][i-K]
      
ans = 0
for j in range(K):
  for i in range(2*K):
    ans = max(ans,BW_res[j][i]%base+BW_res[j][(i+K)%(2*K)]//base)
print(ans)

Submission status: Accepted

Solution code:
from numpy import *
N,K = map(int,input().split())
M = zeros((3*K,3*K),int)
L = 2*K
O = 0

for n in range(N):
  x,y,c = input().split()
  x = int(x)%L
  y = int(y)%L
  t = c=="W"
  M[x,y]+=1-2*t
  O+=t

for n in range(2):
  M[L:] = M[:K]
  M = cumsum(M,axis=0)
  M[:L] = M[K:]-M[:L]
  M = M.T
  
M = M[:L,:L]
print(O+(M+roll(roll(M,K,axis=0),K,axis=1)).max())

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
import numpy as np
#対称性を利用して点を単位格子K*2Kに圧縮
_2K, _4K = 2*K, 4*K
shape = (_2K,_4K) #後でK*2Kに圧縮
Grd = np.zeros(shape, dtype='int64')
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        x, y = x%_2K, y%_2K
    else: 
        x, y = (x+K)%_2K, y%_2K
    #点について、2K*2K -> K*2Kの調整。次は等価、(K+i,K+j)と(i,j),(i,K+j)と(i+K,j)
    if x >= K and y >= K: x -= K; y -= K
    if x < K and y >= K: x += K; y -= K
    #この点がK*Kの黒色正方形内に入る。正方形を特徴づけるには頂点の座標１つだけで十分。
    #⇒１つの点はK*K個の塗り方に+1の影響を与える。
    #毎回K**2のマスにアクセスするとTLEするため、後で累積和(計算量O(K**2))を取った時に+1される範囲が等しくなるように調整する(隣接差分を取る)。
    #K=3の場合
    #[[1 1 1 0 0 0]    [[ 1 0 0 -1 0 0 0]
    # [1 1 1 0 0 0]     [ 0 0 0  0 0 0 0]
    # [1 1 1 0 0 0]  => [ 0 0 0  0 0 0 0]
    # [0 0 0 0 0 0]     [-1 0 0  1 0 0 0]
    # [0 0 0 0 0 0]     [ 0 0 0  0 0 0 0]
    # [0 0 0 0 0 0]]    [ 0 0 0  0 0 0 0]
    #                   [ 0 0 0  0 0 0 0]
    
    Grd[y, x] += 1
    Grd[y+K, x+K] += 1
    Grd[y+K, x] += -1
    Grd[y, x+K] += -1
del x, y, c

#2重累積和計算
Grd = Grd.cumsum(axis=1).cumsum(axis=0)
#2K*4K -> K*2Kへ圧縮
Grd = Grd[:,:_2K] +Grd[:,_2K:_4K]
Grd = Grd[:K,:] +np.concatenate((Grd[K:_2K,K:_2K],Grd[K:_2K,:K]),axis=1) 

ans = Grd.max()
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
import numpy as np
#対称性を利用して点を単位格子K*2Kに圧縮
_2K, _4K = 2*K, 4*K
shape = (_2K+1,_4K+1) #後でK*2Kに圧縮
Grd = np.zeros(shape,dtype='int64')
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        x, y = x%_2K, y%_2K
    else: 
        x, y = (x+K)%_2K, y%_2K
    #点について、2K*2K -> K*2Kの調整。次は等価、(K+i,K+j)==(i,j),(i,K+j)==(i+K,j)
    if x >= K and y >= K: x -= K; y -= K
    if x < K and y >= K: x += K; y -= K
    #この点がK*Kの黒色正方形内に入る。正方形を特徴づけるには左下の座標だけで十分。
    #⇒１つの点はK**2個の塗り方に+1の影響を与える。
    #毎回2K**2のマスにアクセスするとTLEするため、あとで累積和(計算量O(K**2))を取った時に+1される範囲が等しくなるように調整する(隣接差分を取る)。
    #K=3の場合
    #[[1 1 1 0 0 0]    [[ 1 0 0 -1 0 0  0]
    # [1 1 1 0 0 0]     [ 0 0 0  0 0 0  0]
    # [1 1 1 0 0 0]  => [ 0 0 0  0 0 0  0]
    # [0 0 0 0 0 0]     [-1 0 0  1 0 0  0]
    # [0 0 0 0 0 0]     [ 0 0 0  0 0 0  0]
    # [0 0 0 0 0 0]]    [ 0 0 0  0 0 0  0]
    #                   [ 0 0 0  0 0 0  0]
    
    Grd[y, x] += 1
    Grd[y+K, x+K] += 1
    Grd[y+K, x] += -1
    Grd[y, x+K] += -1
del x, y, c

#2重累積和計算
Grd = Grd.cumsum(axis=1).cumsum(axis=0)
#2K*4K -> K*2Kへ圧縮
Grd = Grd[:,:_2K] +Grd[:,_2K:_4K]
Grd = Grd[:K,:] +np.concatenate((Grd[K:_2K,K:_2K],Grd[K:_2K,:K]),axis=1) 

ans = Grd.max()
print(ans)

Submission status: Accepted

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

# あとで開区間な累積和を取るので、K+1。
want_white = [[0] * (K+1) for _ in range(K+1)]
want_black = [[0] * (K+1) for _ in range(K+1)]

for _ in range(N):
    x_str, y_str, c_str = input().split()
    x = int(x_str)
    y = int(y_str)
    c = 1 if c_str == 'B' else 0

    x %= 2 * K
    y %= 2 * K
    if x >= K:
        x -= K
        c ^= 1
    if y >= K:
        y -= K
        c ^= 1

    if c:
        want_black[x+1][y+1] += 1
    else:
        want_white[x+1][y+1] += 1

# 累積和
for i in range(K+1):
    for j in range(K):
        want_black[i][j+1] += want_black[i][j]
        want_white[i][j+1] += want_white[i][j]

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

# (h, w)が黒の左下になるとして、全探索。
ans = 0
for h in range(K+1):
    for w in range(K+1):
        count = want_black[-1][-1] - want_black[h][-1] - want_black[-1][w] + 2 * want_black[h][w]
        count += want_white[h][-1] + want_white[-1][w] - 2 * want_white[h][w]
        ans = max(ans, count, N - count)

print(ans)

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np

def main():
    N, K = map(int, sys.stdin.buffer.readline().split())
    XYC = sys.stdin.buffer.read().split()
    X, Y, C = np.array(XYC[::3], dtype=np.int64), np.array(XYC[1::3], dtype=np.int64), np.array(XYC[2::3])==b"B"
    solve(N, K, X, Y, C)

def solve(N, K, X, Y, C):
    M = np.zeros((K*2+1, K*4), dtype=np.int64)
    for x, y, c in zip(X, Y, C):
        if c:
            x += K
        x %= 2*K
        y %= 2*K
        if x >= K and y >= K:
            x -= K
            y -= K
        elif y >= K:
            y -= K
            x += K
        M[y, x] += 1
        M[y, (x+2*K)%(4*K)] += 1
        M[y+K, x+K] += 1
        M[y+K, (x+3*K)%(4*K)] += 1
        if y == 0:
            M[2*K, x] += 1
            M[2*K, (x+2*K)%(4*K)] += 1
    for y in range(2*K):
        for x in range(4*K):
            M[y+1, x] += M[y, x]
    for y in range(2*K+1):
        for x in range(4*K-1):
            M[y, x+1] += M[y, x]
    ans = max([M[y+K, x+K]+M[y, x]-M[y+K, x]-M[y, x+K] for y in range(K+1) for x in range(2*K+1)])
    print(ans)

numba_compile([
    [solve, "void(i8,i8,i8[:],i8[:],b1[:])"],
])

main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = [[0] * k for _ in range(2 * k + 1)]
for _ in range(n):
    x, y, c = input().split()
    x, y = int(x), int(y)
    x -= (x // (2 * k)) * (2 * k)
    y -= (y // (2 * k)) * (2 * k)
    if x >= k and y >= k:
        x -= k
        y -= k
    elif y >= k:
        x += k
        y -= k
    if c == "B":
        if x >= k:
            x -= k
        else:
            x += k
    s[x + 1][y] += 1
for i in range(2 * k):
    for j in range(k):
        s[i + 1][j] += s[i][j]
ans = 0
for i in range(k):
    cnt = 0
    for j in range(k):
        cnt += (s[i + k][j] - s[i][j])
    ans = max(ans, cnt, n - cnt)
    for j in range(k):
        cnt -= (2 * (s[i + k][j] - s[i][j]))
        cnt += s[2 * k][j]
        ans = max(ans, cnt, n - cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
import array
input = sys.stdin.readline
N,K = map(int,input().split())
xyc = []
for i in range(N):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    xyc.append([x % (2*K), y % (2*K), c])

wmap = [array.array('I',[0]*3*K) for i in [0]*3*K]
hmap = [array.array('I',[0]*3*K) for i in [0]*3*K]
for x,y,c in xyc:
    if c == 'W':
        wmap[y][x] += 1
        if y < K:
            wmap[y+2*K][x] += 1
        if x < K:
            wmap[y][x+2*K] += 1
        if x < K and y < K:
            wmap[y+2*K][x+2*K] += 1
    else:
        hmap[y][x] += 1
        if x < K:
            hmap[y][x+2*K] += 1
        if y < K:
            hmap[y+2*K][x] += 1
        if x < K and y < K:
            hmap[y+2*K][x+2*K] += 1

def accum(L):
    res = [0]*(len(L)+1)
    res[1] = L[0]
    for i in range(2,len(L)+1):
        res[i] = res[i-1] + L[i-1]
    return res
wcumsum = [array.array('I',[0]*(3*K+1))] + [array.array('I',accum(row)) for row in wmap]
hcumsum = [array.array('I',[0]*(3*K+1))] + [array.array('I',accum(row)) for row in hmap]

for y in range(1,3*K+1):
    for x in range(3*K+1):
        wcumsum[y][x] += wcumsum[y-1][x]
        hcumsum[y][x] += hcumsum[y-1][x]

def cs2(m, ltx, lty, rbx, rby):
    S = m[rby-1][rbx-1]
    S -= m[rby-1][ltx-1]
    S -= m[lty-1][rbx-1]
    S += m[lty-1][ltx-1]
    return S

ans = 0
for y in range(1,K+1):
    for x in range(1,K+1):
        ltw = cs2(wcumsum,x,y,x+K, y+K)
        rbw = cs2(wcumsum,x+K,y+K,x+2*K, y+2*K)
        lbh = cs2(hcumsum,x,y+K,x+K, y+2*K)
        rth = cs2(hcumsum,x+K,y,x+2*K, y+K)
        temp = ltw + rbw + lbh + rth
        ans = max(ans,temp)

        ltw = cs2(hcumsum,x,y,x+K, y+K)
        rbw = cs2(hcumsum,x+K,y+K,x+2*K, y+2*K)
        lbh = cs2(wcumsum,x,y+K,x+K, y+2*K)
        rth = cs2(wcumsum,x+K,y,x+2*K, y+K)
        temp = ltw + rbw + lbh + rth
        ans = max(ans,temp)

print(ans)

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


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

ww=[[0]*(2*k+1) for i in range(2*k+1)]
bb=[[0]*(2*k+1) for i in range(2*k+1)]

for i in range(n):
    x,y,c=xyc[i]
    x,y=int(x),int(y)
    if c=="W":
        ww[x%(2*k)+1][y%(2*k)+1]+=1
    else:
        bb[x%(2*k)+1][y%(2*k)+1]+=1

for i in range(2*k):
    for j in range(2*k):
        ww[i+1][j+1]=ww[i+1][j+1]+ww[i+1][j]+ww[i][j+1]-ww[i][j]
        bb[i+1][j+1]=bb[i+1][j+1]+bb[i+1][j]+bb[i][j+1]-bb[i][j]
# print(ww)

def cnt(i1,i2,j1,j2,lst):
    return lst[i2+1][j2+1]-lst[i1+1][j2+1]-lst[i2+1][j1+1]+lst[i1+1][j1+1]

ans=0
for i in range(k+1):
    for j in range(k+1):
        w,b=0,0
        # 左下
        w+=cnt(-1, i-1, -1, j-1, ww)
        # 中央
        w+=cnt(i-1, i+k-1, j-1, j+k-1, ww)
        # 左上
        w+=cnt(-1, i-1, j+k-1, 2*k-1, ww)
        # 右下
        w+=cnt(i+k-1, 2*k-1, -1, j-1, ww)
        # 右上
        w+=cnt(i+k-1, 2*k-1, j+k-1, 2*k-1, ww)

        b+=cnt(-1, i-1, j-1, j+k-1, bb)
        b+=cnt(i-1, i+k-1, -1, j-1, bb)
        b+=cnt(i+k-1, 2*k-1, j-1, j+k-1, bb)
        b+=cnt(i-1, i+k-1, j+k-1, 2*k-1, bb)
        # print(w,b)
        ans=max(ans,w+b)
ww,bb=copy.deepcopy(bb),copy.deepcopy(ww)
for i in range(k+1):
    for j in range(k+1):
        w,b=0,0
        # 左下
        w+=cnt(-1, i-1, -1, j-1, ww)
        # 中央
        w+=cnt(i-1, i+k-1, j-1, j+k-1, ww)
        # 左上
        w+=cnt(-1, i-1, j+k-1, 2*k-1, ww)
        # 右下
        w+=cnt(i+k-1, 2*k-1, -1, j-1, ww)
        # 右上
        w+=cnt(i+k-1, 2*k-1, j+k-1, 2*k-1, ww)

        b+=cnt(-1, i-1, j-1, j+k-1, bb)
        b+=cnt(i-1, i+k-1, -1, j-1, bb)
        b+=cnt(i+k-1, 2*k-1, j-1, j+k-1, bb)
        b+=cnt(i-1, i+k-1, j+k-1, 2*k-1, bb)
        # print(w,b)
        ans=max(ans,w+b)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



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

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    if c=="B":
        x += k
    x %= 2*k
    y %= 2*k
    v[x][y] += 1
#     v[x][y+2*k] += 1
#     v[x+2*k][y] += 1
#     v[x+2*k][y+2*k] += 1
def cumsum2(v):
    # v: h*wの2次元リスト
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
cumsum2(v)

def sub(c, i, j):
    i %= 2*k
    j %= 2*k
    l = []
    if i<=k and j<=k:
        l = [[i,i+k,j,j+k]]
    elif i>k and j<=k:
        l = [[i,2*k,j,j+k], [0,i-k,j,j+k]]
    elif i<=k and j>k:
        l = [[i,i+k,j,2*k], [i,i+k,0,j-k]]
    else:
        l = [[i,2*k,j,2*k], [0,i-k,j,2*k], [i,2*k,0,j-k], [0,i-k,0,j-k]]
    return sum((c[z][w] - c[z][y] - c[x][w] + c[x][y]) for x,z,y,w in l)
ans = -1
for i in range(2*k):
    for j in range(2*k-i):
        val0 = sub(v, i,j) + sub(v, i+k, j+k)
#         val0 = v[i+k][j+k]-v[i+k][j]-v[i][j+k]+v[i][j] + v[i+2*k][j+2*k]-v[i+2*k][j+k]-v[i+k][j+2*k]+v[i+k][j+k]
#         val1 = v[i+2*k][j+k]-v[i+2*k][j]-v[i+k][j+k]+v[i+k][j] + v[i+k][j+2*k]-v[i+k][j+k]-v[i][j+2*k]+v[i][j+k]
        ans = max(ans, val0)
print(ans)