Problem:


 惑星探査(Planetary Exploration) 

あなたを乗せた超時空移民船は長旅の末，ついに居住可能と思われる惑星を発見した．JOI 星と名付けられたその惑星は，その名の通り「ジャングル(Jungle)」，「海(Ocean)」，「氷(Ice)」の3 種類の地形が入り組んだ過酷な惑星である．簡単な調査により，居住予定地近辺の地図が作成された．居住予定地は南北M km, 東西N km の長方形の形をしており， 1 km 四方の正方形の区画に分けられている．区画は全部でMN 個あり，北からp 行目，西からq 列目の区画を(p, q) で表す．北西の角の区画が(1, 1) であり，南東の角の区画が(M, N) である．各区画の地形は，「ジャングル」，「海」，「氷」のいずれかであり，「ジャングル」はJ, 「海」はO, 「氷」はI の英字1 文字で表される.

さて，詳細な移住計画を立てるにあたり， K 箇所の長方形領域内に「ジャングル」，「海」，「氷」がそれぞれ何区画含まれるかを調べることにした．

課題

居住予定地の情報と，調査対象となる領域の情報が与えられたとき，それぞれの領域について， 「ジャングル」，「海」，「氷」が何区画含まれているかを求めるプログラムを作成せよ．

制限

1 ≤ M ≤ 1000    居住予定地の南北の長さ(km)

1 ≤ N ≤ 1000    居住予定地の東西の長さ(km)

1 ≤ K ≤ 100000    調査対象となる領域の個数

入力

標準入力から以下の入力を読み込め．

 1 行目には整数M, N が空白を区切りとして書かれており，居住予定地が南北にM km ，東西にN km の広さであることを表す．

 2 行目には整数K が書かれており，調査対象となる領域の個数を表す．

 続くM 行には居住予定地の情報が書かれている．i + 2 行目(1 ≤ i ≤ M) には，居住予定地の北からi行目に位置するN 区画の情報を表すJ，O，I からなるN 文字の文字列が書かれている．

 続くK 行には調査対象となる領域が書かれている．j + M + 2 行目(1 ≤ j ≤ K) には， j 番目の領域を表す正整数aj, bj, cj, dj が空白を区切りとして書かれている．(aj, bj) は調査領域の北西の角の区画を，(cj, dj) は調査領域の南東の角の区画を表す．ただし，aj, bj, cj, dj は，1 ≤ aj ≤ cj ≤ M, 1 ≤ bj ≤ dj ≤ Nを満たす．

出力

標準出力に調査の結果を表すK 行を出力せよ．出力のj 行目には， j 番目の調査領域に含まれる「ジャングル」(J) の区画数，「海」(O) の区画数，「氷」(I) の区画数を表す3 つの整数を，この順に空白を区切りとして書け．

採点基準

採点用データのうち，配点の30%分については，M ≤ 50 かつK ≤ 100 を満たす．配点の50%分については，M ≤ 50 を満たす．

入出力の例

入力例
  

4 7
4
JIOJOIJ
IOJOIJO
JOIJOOI
OOJJIJO
3 5 4 7
2 2 3 6
2 2 2 2
1 1 4 7

出力例
  

1 3 2
3 5 2
0 1 0
10 11 7

この入力例では， 2 番目の領域は上図のように「ジャングル」を3 区画，「海」を5 区画，「氷」を2 区画含む．

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
4 7
4
JIOJOIJ
IOJOIJO
JOIJOOI
OOJJIJO
3 5 4 7
2 2 3 6
2 2 2 2
1 1 4 7


Sample output:
1 3 2
3 5 2
0 1 0
10 11 7

Submission status: Memory Limit Exceeded

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

d = {}

for i in range(M):
    a = raw_input()
    for j in range(N):
        d[i+1, j+1] = a[j]

dJ = {}
dO = {}
dI = {}

for i in range(M+1):
    for j in range(N+1):
        if i == 0 or j == 0:
            dJ[i, j] = dO[i, j] = dI[i, j] = 0
        elif d[i, j] == 'J':
            dJ[i, j] = dJ[i-1, j] + dJ[i, j-1] - dJ[i-1, j-1] + 1
            dO[i, j] = dO[i-1, j] + dO[i, j-1] - dO[i-1, j-1]
            dI[i, j] = dI[i-1, j] + dI[i, j-1] - dI[i-1, j-1]
        elif d[i, j] == 'O':
            dJ[i, j] = dJ[i-1, j] + dJ[i, j-1] - dJ[i-1, j-1]
            dO[i, j] = dO[i-1, j] + dO[i, j-1] - dO[i-1, j-1] + 1
            dI[i, j] = dI[i-1, j] + dI[i, j-1] - dI[i-1, j-1]
        else:
            dJ[i, j] = dJ[i-1, j] + dJ[i, j-1] - dJ[i-1, j-1]
            dO[i, j] = dO[i-1, j] + dO[i, j-1] - dO[i-1, j-1]
            dI[i, j] = dI[i-1, j] + dI[i, j-1] - dI[i-1, j-1] + 1

for _ in range(K):
    b = map(int, raw_input().split())
    # D = {}
    # D['J'] = D['O'] = D['I'] = 0
    # for i in range(b[0], b[2]+1):
        # for j in range(b[1], b[3]+1):
            # D[d[i, j]] += 1
    # print D['J'], D['O'], D['I']
    print dJ[b[2], b[3]]-dJ[b[0]-1, b[3]]-dJ[b[2], b[1]-1]+dJ[b[0]-1, b[1]-1], dO[b[2], b[3]]-dO[b[0]-1, b[3]]-dO[b[2], b[1]-1]+dO[b[0]-1, b[1]-1], dI[b[2], b[3]]-dI[b[0]-1, b[3]]-dI[b[2], b[1]-1]+dI[b[0]-1, b[1]-1]

Submission status: Memory Limit Exceeded

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

d = {}

for i in range(M):
    a = raw_input()
    for j in range(N):
        d[i+1, j+1] = a[j]

dJ = {}
dO = {}

for i in range(M+1):
    for j in range(N+1):
        if i == 0 or j == 0:
            dJ[i, j] = dO[i, j] = 0
        elif d[i, j] == 'J':
            dJ[i, j] = dJ[i-1, j] + dJ[i, j-1] - dJ[i-1, j-1] + 1
            dO[i, j] = dO[i-1, j] + dO[i, j-1] - dO[i-1, j-1]
        elif d[i, j] == 'O':
            dJ[i, j] = dJ[i-1, j] + dJ[i, j-1] - dJ[i-1, j-1]
            dO[i, j] = dO[i-1, j] + dO[i, j-1] - dO[i-1, j-1] + 1
        else:
            dJ[i, j] = dJ[i-1, j] + dJ[i, j-1] - dJ[i-1, j-1]
            dO[i, j] = dO[i-1, j] + dO[i, j-1] - dO[i-1, j-1]

for _ in range(K):
    b0, b1, b2, b3 = map(int, raw_input().split())
    nJ = dJ[b2, b3]-dJ[b0-1, b3]-dJ[b2, b1-1]+dJ[b0-1, b1-1]
    nO = dO[b2, b3]-dO[b0-1, b3]-dO[b2, b1-1]+dO[b0-1, b1-1]
    nI = (b2-b0+1)*(b3-b1+1)-nJ-nO
    print nJ, nO, nI

Submission status: Memory Limit Exceeded

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

d = {}

for i in range(M):
    a = raw_input()
    for j in range(N):
        d[i+1, j+1] = a[j]

D = {}

for i in range(M+1):
    for j in range(N+1):
        if i == 0 or j == 0:
            D[i, j] = 0, 0
        elif d[i, j] == 'J':
            D[i, j] = (D[i-1, j][0] + D[i, j-1][0] - D[i-1, j-1][0] + 1,
                       D[i-1, j][1] + D[i, j-1][1] - D[i-1, j-1][1])
        elif d[i, j] == 'O':
            D[i, j] = (D[i-1, j][0] + D[i, j-1][0] - D[i-1, j-1][0],
                       D[i-1, j][1] + D[i, j-1][1] - D[i-1, j-1][1] + 1)
        else:
            D[i, j] = (D[i-1, j][0] + D[i, j-1][0] - D[i-1, j-1][0],
                       D[i-1, j][1] + D[i, j-1][1] - D[i-1, j-1][1])

for _ in range(K):
    b0, b1, b2, b3 = map(int, raw_input().split())
    nJ = D[b2, b3][0]-D[b0-1, b3][0]-D[b2, b1-1][0]+D[b0-1, b1-1][0]
    nO = D[b2, b3][1]-D[b0-1, b3][1]-D[b2, b1-1][1]+D[b0-1, b1-1][1]
    nI = (b2-b0+1)*(b3-b1+1)-nJ-nO
    print nJ, nO, nI

Submission status: Accepted

Solution code:
N,M=map(int,raw_input().split())
K=int(raw_input())
A=[]
B=[ [[0,0,0] for j in range(M+1)] for i in range(N+1)]
for i in range(N):
    A.append(raw_input())
for i in range(1,N+1):
    for j in range(1,M+1):
        c=A[i-1][j-1]
        B[i][j][0]=B[i-1][j][0]+B[i][j-1][0]-B[i-1][j-1][0]+(c=='J')
        B[i][j][1]=B[i-1][j][1]+B[i][j-1][1]-B[i-1][j-1][1]+(c=='O')
        B[i][j][2]=B[i-1][j][2]+B[i][j-1][2]-B[i-1][j-1][2]+(c=='I')
for k in range(K):
    a,b,c,d=map(int,raw_input().split())
    aj=B[c][d][0]-B[c][b-1][0]-B[a-1][d][0]+B[a-1][b-1][0]
    ao=B[c][d][1]-B[c][b-1][1]-B[a-1][d][1]+B[a-1][b-1][1]
    ai=B[c][d][2]-B[c][b-1][2]-B[a-1][d][2]+B[a-1][b-1][2]
    print aj,ao,ai

Submission status: Accepted

Solution code:
# use dp
# python 3.

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

# answer matrix
dp_j = [[0 for i in range(n+1)]for j in range(m+1)]
dp_o = [[0 for i in range(n+1)]for j in range(m+1)]


# input row and calc dp
for i in range(1, m+1):
   row = list(input())
   # print(row)
   for j in range(1, n+1):
      dp_j[i][j] = dp_j[i-1][j] + dp_j[i][j-1] - dp_j[i-1][j-1] + (1 if row[j-1] == 'J' else 0)
      dp_o[i][j] = dp_o[i-1][j] + dp_o[i][j-1] - dp_o[i-1][j-1] + (1 if row[j-1] == 'O' else 0) 

      
for i in range(k):
   a, b, c, d = map(int, input().split())

   j_cnt = dp_j[c][d] - dp_j[a-1][d] - dp_j[c][b-1] + dp_j[a-1][b-1]
   o_cnt = dp_o[c][d] - dp_o[a-1][d] - dp_o[c][b-1] + dp_o[a-1][b-1]
   i_cnt = (abs(c-a)+1) *  (abs(d-b)+1) - j_cnt - o_cnt

   print(str(j_cnt) + ' ' + str(o_cnt) + ' ' + str(i_cnt))

Submission status: Accepted

Solution code:
M, N = map(int, input().split())
K = int(input())
P = ['_' * (N + 1) for _ in range(M + 1)]
for mi in range(1, M + 1):
    P[mi] = '_' + input()
# for p in P:
#     print('p', p)

J = [[0 for _ in range(N + 1)] for _ in range(M + 1)]
O = [[0 for _ in range(N + 1)] for _ in range(M + 1)]
I = [[0 for _ in range(N + 1)] for _ in range(M + 1)]
for i in range(1, M + 1):
    ji, oi, ii = 0, 0, 0
    for j in range(1, N + 1):
        ji += P[i][j] == 'J'
        oi += P[i][j] == 'O'
        ii += P[i][j] == 'I'
        J[i][j] = J[i - 1][j] + ji
        O[i][j] = O[i - 1][j] + oi
        I[i][j] = I[i - 1][j] + ii
# for j in J:
#     print('j', j)
# for o in O:
#     print('o', o)
# for i in I:
#     print('i', i)


def cum(mat, a, b, c, d):
    a -= 1
    b -= 1
    return mat[a][b] + mat[c][d] - mat[a][d] - mat[c][b]

for k in range(K):
    a, b, c, d = map(int, input().split())
    j = cum(J, a, b, c, d)
    o = cum(O, a, b, c, d)
    i = cum(I, a, b, c, d)
    print(j, o, i)

Submission status: Accepted

Solution code:
# coding: utf-8
M, N = list(map(int, input().split()))
q = int(input())

Map = []
for i in range(M):
    Map.append(input())

def get_slide_sum(Map, kw):
    l = []
    for r in range(M):
        tmp = []
        for c in range(N):
            ll = 0 if c == 0 else tmp[c-1]
            ul = 0 if r == 0 or c == 0 else l[r-1][c-1]
            ur = 0 if r == 0 else l[r-1][c]
            count = ll + ur - ul
            if Map[r][c] == kw:
                count+=1
            tmp.append(count)
        l.append(tmp)
    return l

J = get_slide_sum(Map, 'J')
O = get_slide_sum(Map, 'O')
I = get_slide_sum(Map, 'I')

def get_sum(inp,L):
    a, b, c, d = list(map(int, inp.split()))
    ll = 0 if a == 1 else L[a-2][d-1]
    ul = 0 if a == 1 or b == 1 else L[a-2][b-2]
    ur = 0 if b == 1 else L[c-1][b-2]
    return L[c-1][d-1] - ll - ur + ul

for i in range(q):
    inp = input()
    print(get_sum(inp, J), get_sum(inp, O), get_sum(inp, I))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560

"""
import sys
from sys import stdin
input = stdin.readline


def solve(M, N, K, field):
    dp_J = [[0] * (N+1) for _ in range(M+1)]
    dp_O = [[0] * (N+1) for _ in range(M+1)]
    dp_I = [[0] * (N+1) for _ in range(M+1)]
    for y in range(M):
        t_J = [0] * (N+1)
        t_O = [0] * (N+1)
        t_I = [0] * (N+1)
        for x in range(N):
            land = field[y][x]
            if land == 'J':
                t_J[x+1] = t_J[x] + 1
                t_O[x+1] = t_O[x]
                t_I[x+1] = t_I[x]
            elif land == 'O':
                t_J[x+1] = t_J[x]
                t_O[x+1] = t_O[x] + 1
                t_I[x+1] = t_I[x]
            else:
                t_J[x+1] = t_J[x]
                t_O[x+1] = t_O[x]
                t_I[x+1] = t_I[x] + 1

        for x in range(1, N+1):
            dp_J[y+1][x] = dp_J[y][x] + t_J[x]
            dp_O[y+1][x] = dp_O[y][x] + t_O[x]
            dp_I[y+1][x] = dp_I[y][x] + t_I[x]

    for _ in range(K):
        result = [0, 0, 0]
        y1, x1, y2, x2 = map(int, input().split())
        result[0] = dp_J[y2][x2] - dp_J[y1-1][x2] - dp_J[y2][x1-1] + dp_J[y1-1][x1-1]
        result[1] = dp_O[y2][x2] - dp_O[y1-1][x2] - dp_O[y2][x1-1] + dp_O[y1-1][x1-1]
        result[2] = dp_I[y2][x2] - dp_I[y1-1][x2] - dp_I[y2][x1-1] + dp_I[y1-1][x1-1]
        print(' '.join(map(str, result)))


def main(args):
    M, N = map(int, input().split())
    K = int(input())
    field = [input().strip() for _ in range(M)]
    solve(M, N, K, field)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560

"""
import sys
from sys import stdin
input = stdin.readline


def solve(M, N, K, field):
    dp_J = [[0] * (N+1) for _ in range(M+1)]
    dp_O = [[0] * (N+1) for _ in range(M+1)]
    dp_I = [[0] * (N+1) for _ in range(M+1)]
    for y in range(M):
        t_J = [0] * (N+1)
        t_O = [0] * (N+1)
        t_I = [0] * (N+1)
        for x in range(N):
            land = field[y][x]
            if land == 'J':
                t_J[x+1] = t_J[x] + 1
                t_O[x+1] = t_O[x]
                t_I[x+1] = t_I[x]
            elif land == 'O':
                t_J[x+1] = t_J[x]
                t_O[x+1] = t_O[x] + 1
                t_I[x+1] = t_I[x]
            else:
                t_J[x+1] = t_J[x]
                t_O[x+1] = t_O[x]
                t_I[x+1] = t_I[x] + 1

        for x in range(1, N+1):
            dp_J[y+1][x] = dp_J[y][x] + t_J[x]
            dp_O[y+1][x] = dp_O[y][x] + t_O[x]
            dp_I[y+1][x] = dp_I[y][x] + t_I[x]

    for _ in range(K):
        result = [0, 0, 0]
        y1, x1, y2, x2 = map(int, input().split())
        result[0] = dp_J[y2][x2] - dp_J[y1-1][x2] - dp_J[y2][x1-1] + dp_J[y1-1][x1-1]
        result[1] = dp_O[y2][x2] - dp_O[y1-1][x2] - dp_O[y2][x1-1] + dp_O[y1-1][x1-1]
        result[2] = dp_I[y2][x2] - dp_I[y1-1][x2] - dp_I[y2][x1-1] + dp_I[y1-1][x1-1]
        print(' '.join(map(str, result)))


def solve2(M, N, K, field):
    dp_J = [[0] * (N+1) for _ in range(M+1)]
    dp_O = [[0] * (N+1) for _ in range(M+1)]
    for y in range(M):
        t_J = [0] * (N+1)
        t_O = [0] * (N+1)
        for x in range(N):
            land = field[y][x]
            if land == 'J':
                t_J[x+1] = t_J[x] + 1
                t_O[x+1] = t_O[x]
            elif land == 'O':
                t_J[x+1] = t_J[x]
                t_O[x+1] = t_O[x] + 1
            else:
                t_J[x+1] = t_J[x]
                t_O[x+1] = t_O[x]

        for x in range(1, N+1):
            dp_J[y+1][x] = dp_J[y][x] + t_J[x]
            dp_O[y+1][x] = dp_O[y][x] + t_O[x]


    for _ in range(K):
        result = [0, 0, 0]
        y1, x1, y2, x2 = map(int, input().split())
        result[0] = dp_J[y2][x2] - dp_J[y1-1][x2] - dp_J[y2][x1-1] + dp_J[y1-1][x1-1]
        result[1] = dp_O[y2][x2] - dp_O[y1-1][x2] - dp_O[y2][x1-1] + dp_O[y1-1][x1-1]
        result[2] = (x2 - x1 + 1) * (y2 - y1 + 1) - result[0] - result[1]
        print(' '.join(map(str, result)))


def main(args):
    M, N = map(int, input().split())
    K = int(input())
    field = [input().strip() for _ in range(M)]
    solve2(M, N, K, field)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560

"""
import sys
from sys import stdin
input = stdin.readline


def solve(M, N, K, field):
    dp_J = [[0] * (N+1) for _ in range(M+1)]
    dp_O = [[0] * (N+1) for _ in range(M+1)]
    dp_I = [[0] * (N+1) for _ in range(M+1)]
    for y in range(M):
        t_J = [0] * (N+1)
        t_O = [0] * (N+1)
        t_I = [0] * (N+1)
        for x in range(N):
            land = field[y][x]
            if land == 'J':
                t_J[x+1] = t_J[x] + 1
                t_O[x+1] = t_O[x]
                t_I[x+1] = t_I[x]
            elif land == 'O':
                t_J[x+1] = t_J[x]
                t_O[x+1] = t_O[x] + 1
                t_I[x+1] = t_I[x]
            else:
                t_J[x+1] = t_J[x]
                t_O[x+1] = t_O[x]
                t_I[x+1] = t_I[x] + 1

        for x in range(1, N+1):
            dp_J[y+1][x] = dp_J[y][x] + t_J[x]
            dp_O[y+1][x] = dp_O[y][x] + t_O[x]
            dp_I[y+1][x] = dp_I[y][x] + t_I[x]

    for _ in range(K):
        result = [0, 0, 0]
        y1, x1, y2, x2 = map(int, input().split())
        result[0] = dp_J[y2][x2] - dp_J[y1-1][x2] - dp_J[y2][x1-1] + dp_J[y1-1][x1-1]
        result[1] = dp_O[y2][x2] - dp_O[y1-1][x2] - dp_O[y2][x1-1] + dp_O[y1-1][x1-1]
        result[2] = dp_I[y2][x2] - dp_I[y1-1][x2] - dp_I[y2][x1-1] + dp_I[y1-1][x1-1]
        print(' '.join(map(str, result)))


def solve3(M, N, K, field):
    dp_J = [[0] * (N+1) for _ in range(M+1)]
    dp_O = [[0] * (N+1) for _ in range(M+1)]
    for y in range(1, M+1):
        for x in range(1, N+1):
            land = field[y-1][x-1]
            if land == 'J':
                dp_J[y][x] = dp_J[y-1][x] + dp_J[y][x-1] - dp_J[y-1][x-1] + 1
                dp_O[y][x] = dp_O[y-1][x] + dp_O[y][x-1] - dp_O[y-1][x-1]
            elif land == 'O':
                dp_J[y][x] = dp_J[y-1][x] + dp_J[y][x-1] - dp_J[y-1][x-1]
                dp_O[y][x] = dp_O[y-1][x] + dp_O[y][x-1] - dp_O[y-1][x-1] + 1
            else:
                dp_J[y][x] = dp_J[y-1][x] + dp_J[y][x-1] - dp_J[y-1][x-1]
                dp_O[y][x] = dp_O[y-1][x] + dp_O[y][x-1] - dp_O[y-1][x-1]

    for _ in range(K):
        result = [0, 0, 0]
        y1, x1, y2, x2 = map(int, input().split())
        result[0] = dp_J[y2][x2] - dp_J[y1-1][x2] - dp_J[y2][x1-1] + dp_J[y1-1][x1-1]
        result[1] = dp_O[y2][x2] - dp_O[y1-1][x2] - dp_O[y2][x1-1] + dp_O[y1-1][x1-1]
        result[2] = (x2 - x1 + 1) * (y2 - y1 + 1) - result[0] - result[1]
        print(' '.join(map(str, result)))


def main(args):
    M, N = map(int, input().split())
    K = int(input())
    field = [input().strip() for _ in range(M)]
    solve3(M, N, K, field)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560

"""
import sys
from sys import stdin
input = stdin.readline


def solve(M, N, K, field):
    dp_J = [[0] * (N+1) for _ in range(M+1)]
    dp_O = [[0] * (N+1) for _ in range(M+1)]
    dp_I = [[0] * (N+1) for _ in range(M+1)]
    for y in range(M):
        t_J = [0] * (N+1)
        t_O = [0] * (N+1)
        t_I = [0] * (N+1)
        for x in range(N):
            land = field[y][x]
            if land == 'J':
                t_J[x+1] = t_J[x] + 1
                t_O[x+1] = t_O[x]
                t_I[x+1] = t_I[x]
            elif land == 'O':
                t_J[x+1] = t_J[x]
                t_O[x+1] = t_O[x] + 1
                t_I[x+1] = t_I[x]
            else:
                t_J[x+1] = t_J[x]
                t_O[x+1] = t_O[x]
                t_I[x+1] = t_I[x] + 1

        for x in range(1, N+1):
            dp_J[y+1][x] = dp_J[y][x] + t_J[x]
            dp_O[y+1][x] = dp_O[y][x] + t_O[x]
            dp_I[y+1][x] = dp_I[y][x] + t_I[x]

    for _ in range(K):
        result = [0, 0, 0]
        y1, x1, y2, x2 = map(int, input().split())
        result[0] = dp_J[y2][x2] - dp_J[y1-1][x2] - dp_J[y2][x1-1] + dp_J[y1-1][x1-1]
        result[1] = dp_O[y2][x2] - dp_O[y1-1][x2] - dp_O[y2][x1-1] + dp_O[y1-1][x1-1]
        result[2] = dp_I[y2][x2] - dp_I[y1-1][x2] - dp_I[y2][x1-1] + dp_I[y1-1][x1-1]
        print(' '.join(map(str, result)))


def solve4(M, N, K, field):
    dp = [[[0, 0] for _ in range(N+1)] for _ in range(M+1)]

    for y in range(1, M+1):
        for x in range(1, N+1):
            land = field[y-1][x-1]
            if land == 'J':
                dp[y][x][0] = dp[y-1][x][0] + dp[y][x-1][0] - dp[y-1][x-1][0] + 1
                dp[y][x][1] = dp[y-1][x][1] + dp[y][x-1][1] - dp[y-1][x-1][1]
            elif land == 'O':
                dp[y][x][0] = dp[y-1][x][0] + dp[y][x-1][0] - dp[y-1][x-1][0]
                dp[y][x][1] = dp[y-1][x][1] + dp[y][x-1][1] - dp[y-1][x-1][1] + 1
            else:
                dp[y][x][0] = dp[y-1][x][0] + dp[y][x-1][0] - dp[y-1][x-1][0]
                dp[y][x][1] = dp[y-1][x][1] + dp[y][x-1][1] - dp[y-1][x-1][1]

    for _ in range(K):
        result = [0, 0, 0]
        y1, x1, y2, x2 = map(int, input().split())
        result[0] = dp[y2][x2][0] - dp[y1-1][x2][0] - dp[y2][x1-1][0] + dp[y1-1][x1-1][0]
        result[1] = dp[y2][x2][1] - dp[y1-1][x2][1] - dp[y2][x1-1][1] + dp[y1-1][x1-1][1]
        result[2] = (x2 - x1 + 1) * (y2 - y1 + 1) - result[0] - result[1]
        print(' '.join(map(str, result)))


def main(args):
    M, N = map(int, input().split())
    K = int(input())
    field = [input().strip() for _ in range(M)]
    solve4(M, N, K, field)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
M, N = map(int, input().split())
K = int(input())
P = ['_' * (N + 1) for _ in range(M + 1)]
for mi in range(1, M + 1):
    P[mi] = '_' + input()
# for p in P:
#     print('p', p)

J = [[0 for _ in range(N + 1)] for _ in range(M + 1)]
O = [[0 for _ in range(N + 1)] for _ in range(M + 1)]
I = [[0 for _ in range(N + 1)] for _ in range(M + 1)]
for i in range(1, M + 1):
    ji, oi, ii = 0, 0, 0
    for j in range(1, N + 1):
        ji += P[i][j] == 'J'
        oi += P[i][j] == 'O'
        ii += P[i][j] == 'I'
        J[i][j] = J[i - 1][j] + ji
        O[i][j] = O[i - 1][j] + oi
        I[i][j] = I[i - 1][j] + ii
# for j in J:
#     print('j', j)
# for o in O:
#     print('o', o)
# for i in I:
#     print('i', i)


def cum(mat, a, b, c, d):
    a -= 1
    b -= 1
    return mat[a][b] + mat[c][d] - mat[a][d] - mat[c][b]


for k in range(K):
    a, b, c, d = map(int, input().split())
    j = cum(J, a, b, c, d)
    o = cum(O, a, b, c, d)
    i = cum(I, a, b, c, d)
    print(j, o, i)

Submission status: Accepted

Solution code:
m, n = map(int,input().split())
k = int(input())
mp = [input() for i in range(m)]
dp = [[[0] * 3 for j in range(n + 1)] for i in range(m + 1)]
for i in range(1, m + 1):
  for j in range(1, n + 1):
    for p in range(3):
      dp[i][j][p] = dp[i][j - 1][p] + dp[i - 1][j][p] - dp[i - 1][j - 1][p]
    if mp[i - 1][j - 1] == "J":
      dp[i][j][0] += 1
    elif mp[i - 1][j - 1] == "O":
      dp[i][j][1] += 1
    else:
      dp[i][j][2] += 1
#    print(dp[i][j])
for i in range(k):
  x1,y1,x2,y2 = map(int,input().split())
  print(dp[x2][y2][0] - dp[x1 - 1][y2][0] - dp[x2][y1 - 1][0] + dp[x1 - 1][y1 - 1][0], dp[x2][y2][1] - dp[x1 - 1][y2][1] - dp[x2][y1 - 1][1] + dp[x1 - 1][y1 - 1][1], dp[x2][y2][2] - dp[x1 - 1][y2][2] - dp[x2][y1 - 1][2] + dp[x1 - 1][y1 - 1][2])

Submission status: Accepted

Solution code:
def solve():
  m, n = map(int,input().split())
  k = int(input())
  mp = [input() for i in range(m)]
  dp = [[[0] * 3 for j in range(n + 1)] for i in range(m + 1)]
  for i in range(1, m + 1):
    for j in range(1, n + 1):
      for p in range(3):
        dp[i][j][p] = dp[i][j - 1][p] + dp[i - 1][j][p] - dp[i - 1][j - 1][p]
      if mp[i - 1][j - 1] == "J":
        dp[i][j][0] += 1
      elif mp[i - 1][j - 1] == "O":
        dp[i][j][1] += 1
      else:
        dp[i][j][2] += 1
  for i in range(k):
    x1,y1,x2,y2 = map(int,input().split())
    print(dp[x2][y2][0] - dp[x1 - 1][y2][0] - dp[x2][y1 - 1][0] + dp[x1 - 1][y1 - 1][0], dp[x2][y2][1] - dp[x1 - 1][y2][1] - dp[x2][y1 - 1][1] + dp[x1 - 1][y1 - 1][1], dp[x2][y2][2] - dp[x1 - 1][y2][2] - dp[x2][y1 - 1][2] + dp[x1 - 1][y1 - 1][2])
solve()

Submission status: Accepted

Solution code:
def solve():
  m, n = map(int,input().split())
  k = int(input())
  mp = [input() for i in range(m)]
  dp = [[[0] * 3 for j in range(n + 1)] for i in range(m + 1)]
  dic = {"J":0, "O":1, "I":2}

  for i in range(1, m + 1):
    dpi = dp[i]
    dpi_1 = dp[i - 1]

    for j in range(1, n + 1):
      dpij = dpi[j]
      dpij_1 = dpi[j - 1]
      dpi_1j = dpi_1[j]
      dpi_1j_1 = dpi_1[j - 1]

      for p in range(3):
        #dp[i][j][p] = dp[i][j - 1][p] + dp[i - 1][j][p] - dp[i - 1][j - 1][p]
        dpij[p] = dpij_1[p] + dpi_1j[p] - dpi_1j_1[p]

      #dp[i][j][mp[i - 1][j - 1]] += 1
      dpij[dic[mp[i - 1][j - 1]]] += 1
     

  for i in range(k):
    x1,y1,x2,y2 = map(int,input().split())
    dpx2 = dp[x2]
    dpx1 = dp[x1 - 1]
    dpx2y2 = dpx2[y2]
    dpx2y1 = dpx2[y1 - 1]
    dpx1y2 = dpx1[y2]
    dpx1y1 = dpx1[y1 - 1]
    #print(dp[x2][y2][0] - dp[x1 - 1][y2][0] - dp[x2][y1 - 1][0] + dp[x1 - 1][y1 - 1][0], dp[x2][y2][1] - dp[x1 - 1][y2][1] - dp[x2][y1 - 1][1] + dp[x1 - 1][y1 - 1][1], dp[x2][y2][2] - dp[x1 - 1][y2][2] - dp[x2][y1 - 1][2] + dp[x1 - 1][y1 - 1][2])
    print(dpx2y2[0] - dpx1y2[0] - dpx2y1[0] + dpx1y1[0], dpx2y2[1] - dpx1y2[1] - dpx2y1[1] + dpx1y1[1], dpx2y2[2] - dpx1y2[2] - dpx2y1[2] + dpx1y1[2])
solve()

Submission status: Accepted

Solution code:
def solve():
  m, n = map(int,input().split())
  k = int(input())
  mp = [input() for i in range(m)]
  dp = [[[0] * 3 for j in range(n + 1)] for i in range(m + 1)]
  dic = {"J":0, "O":1, "I":2}

  for i in range(1, m + 1):
    dpi = dp[i]
    dpi_1 = dp[i - 1]

    for j in range(1, n + 1):
      dpij = dpi[j]
      dpij_1 = dpi[j - 1]
      dpi_1j = dpi_1[j]
      dpi_1j_1 = dpi_1[j - 1]

      for p in range(3):
        #dp[i][j][p] = dp[i][j - 1][p] + dp[i - 1][j][p] - dp[i - 1][j - 1][p]
        dpij[p] = dpij_1[p] + dpi_1j[p] - dpi_1j_1[p]

      #dp[i][j][mp[i - 1][j - 1]] += 1
      dpij[dic[mp[i - 1][j - 1]]] += 1
     
  ans = ""
  for i in range(k):
    x1,y1,x2,y2 = map(int,input().split())
    dpx2 = dp[x2]
    dpx1 = dp[x1 - 1]
    dpx2y2 = dpx2[y2]
    dpx2y1 = dpx2[y1 - 1]
    dpx1y2 = dpx1[y2]
    dpx1y1 = dpx1[y1 - 1]
    #print(dp[x2][y2][0] - dp[x1 - 1][y2][0] - dp[x2][y1 - 1][0] + dp[x1 - 1][y1 - 1][0], dp[x2][y2][1] - dp[x1 - 1][y2][1] - dp[x2][y1 - 1][1] + dp[x1 - 1][y1 - 1][1], dp[x2][y2][2] - dp[x1 - 1][y2][2] - dp[x2][y1 - 1][2] + dp[x1 - 1][y1 - 1][2])
    ans += str(dpx2y2[0] - dpx1y2[0] - dpx2y1[0] + dpx1y1[0]) + " " + str(dpx2y2[1] - dpx1y2[1] - dpx2y1[1] + dpx1y1[1]) + " " + str(dpx2y2[2] - dpx1y2[2] - dpx2y1[2] + dpx1y1[2]) + "\n"
  ans = ans.rstrip()
  print(ans)


solve()

Submission status: Accepted

Solution code:
from pprint import pprint
m, n = map(int, raw_input().split())
k = int(raw_input())

psum = [[[0] * 3 for x in xrange(n + 1)] for y in xrange(m + 1)]

for y in xrange(m):
    line = raw_input()
    for x in xrange(n):
        for i in xrange(3):
            psum[y + 1][x + 1][i] = psum[y][x + 1][i] + psum[y + 1][x][i] - psum[y][x][i]
        psum[y + 1][x + 1][ { 'J':0, 'O':1, 'I':2 }[line[x]] ] += 1

for k_ in xrange(k):
    a, b, c, d = map(int, raw_input().split())
    j = psum[c][d][0] - psum[a - 1][d][0] - psum[c][b - 1][0] + psum[a - 1][b - 1][0]
    o = psum[c][d][1] - psum[a - 1][d][1] - psum[c][b - 1][1] + psum[a - 1][b - 1][1]
    i = psum[c][d][2] - psum[a - 1][d][2] - psum[c][b - 1][2] + psum[a - 1][b - 1][2]
    print j, o, i

Submission status: Accepted

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

D = {}

for i in range(M+1):
    D[i, 0] = 0, 0
for j in range(N+1):
    D[0, j] = 0, 0

for i in range(1, M+1):
    a = raw_input()
    for j in range(1, N+1):
        if a[j-1] == 'J':
            D[i, j] = (D[i-1, j][0] + D[i, j-1][0] - D[i-1, j-1][0] + 1,
                       D[i-1, j][1] + D[i, j-1][1] - D[i-1, j-1][1])
        elif a[j-1] == 'O':
            D[i, j] = (D[i-1, j][0] + D[i, j-1][0] - D[i-1, j-1][0],
                       D[i-1, j][1] + D[i, j-1][1] - D[i-1, j-1][1] + 1)
        else:
            D[i, j] = (D[i-1, j][0] + D[i, j-1][0] - D[i-1, j-1][0],
                       D[i-1, j][1] + D[i, j-1][1] - D[i-1, j-1][1])

for _ in range(K):
    b0, b1, b2, b3 = map(int, raw_input().split())
    nJ = D[b2, b3][0]-D[b0-1, b3][0]-D[b2, b1-1][0]+D[b0-1, b1-1][0]
    nO = D[b2, b3][1]-D[b0-1, b3][1]-D[b2, b1-1][1]+D[b0-1, b1-1][1]
    nI = (b2-b0+1)*(b3-b1+1)-nJ-nO
    print nJ, nO, nI

Submission status: Accepted

Solution code:
from array import array

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

D0 = [array('l', [0]) * (N+1) for _ in xrange(M+1)]
D1 = [array('l', [0]) * (N+1) for _ in xrange(M+1)]

for i in xrange(1, M+1):
    a = raw_input()
    for j in xrange(1, N+1):
        D0[i][j] = D0[i-1][j] + D0[i][j-1] - D0[i-1][j-1] + (a[j-1] == 'J')
        D1[i][j] = D1[i-1][j] + D1[i][j-1] - D1[i-1][j-1] + (a[j-1] == 'O')

for _ in xrange(K):
    b0, b1, b2, b3 = map(int, raw_input().split())
    nJ = D0[b2][b3]-D0[b0-1][b3]-D0[b2][b1-1]+D0[b0-1][b1-1]
    nO = D1[b2][b3]-D1[b0-1][b3]-D1[b2][b1-1]+D1[b0-1][b1-1]
    nI = (b2-b0+1)*(b3-b1+1)-nJ-nO
    print nJ, nO, nI

Submission status: Accepted

Solution code:
def count_rectangle(cnt, x1, y1, x2, y2):
    return cnt[y2][x2] - cnt[y2][x1 - 1] - cnt[y1 - 1][x2] + cnt[y1 - 1][x1 - 1]


if __name__ == '__main__':
    N, M = map(int, raw_input().split())
    K = input()
    field = []
    for i in xrange(N):
        field.append(list(raw_input()))
    cnt = dict()
    ground = ('J', 'O', 'I')
    for k in ground:
        cnt[k] = [[0] * (M + 1) for _ in xrange(N + 1)]

    for i in xrange(N):
        for j in xrange(M):
            for k in cnt:
                tmp = 1 if field[i][j] == k else 0
                cnt[k][i + 1][j + 1] = cnt[k][i + 1][j] + tmp

    for j in xrange(1, M + 1):
        for i in xrange(N):
            for k in cnt:
                cnt[k][i + 1][j] += cnt[k][i][j]
                
    for i in xrange(K):
        y1, x1, y2, x2 = map(int, raw_input().split())
        ret = []
        for k in ground:
            ret.append(count_rectangle(cnt[k], x1, y1, x2, y2))
        print ' '.join(map(str, ret))

Submission status: Accepted

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

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

joi=dict()
joi["J"]=0
joi["O"]=1
joi["I"]=2


mnj=[[0]*(n+1) for i in range(m+1)]
mno=[[0]*(n+1) for i in range(m+1)]
mni=[[0]*(n+1) for i in range(m+1)]
for i in range(1,m+1):
    mns=input()
    mnii=[0]*3
    for ii in range(1,n+1):
        mnii[joi[mns[ii-1]]]+=1
        mnj[i][ii]=mnj[i-1][ii]+mnii[0]
        mno[i][ii]=mno[i-1][ii]+mnii[1]
        mni[i][ii]=mni[i-1][ii]+mnii[2]
    
s=[0]*3
for j in range(k):
    aj,bj,cj,dj=map(int,input().split())
    aj-=1
    bj-=1
    sj=mnj[cj][dj]-mnj[aj][dj]-mnj[cj][bj]+mnj[aj][bj]
    so=mno[cj][dj]-mno[aj][dj]-mno[cj][bj]+mno[aj][bj]
    si=mni[cj][dj]-mni[aj][dj]-mni[cj][bj]+mni[aj][bj]
    print(sj,so,si)

Submission status: Accepted

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

J = [ [0]*(N+1) for _ in range(M+1) ] 
O = [ [0]*(N+1) for _ in range(M+1) ]
I = [ [0]*(N+1) for _ in range(M+1) ]

for i in range(M):
  for j in range(N):
    if maze[i][j] == "J":
      J[i+1][j+1] = 1
    elif maze[i][j] == "O":
      O[i+1][j+1] = 1
    else:
      I[i+1][j+1] = 1

for i in range(1,M+1):
  for j in range(1,N+1):
    J[i][j] += J[i-1][j]-J[i-1][j-1]+J[i][j-1]
    O[i][j] += O[i-1][j]-O[i-1][j-1]+O[i][j-1]
    I[i][j] += I[i-1][j]-I[i-1][j-1]+I[i][j-1]

for _ in range(K):
  x1,y1,x2,y2 = map(int,input().split())
  j = J[x2][y2]-J[x1-1][y2]-J[x2][y1-1]+J[x1-1][y1-1]
  o = O[x2][y2]-O[x1-1][y2]-O[x2][y1-1]+O[x1-1][y1-1]
  i = I[x2][y2]-I[x1-1][y2]-I[x2][y1-1]+I[x1-1][y1-1]
  print(j,o,i)

Submission status: Accepted

Solution code:
m, n = (int(x) for x in input().split())
k = int(input())
joi_list = [0]*m
for i in range(m):
  joi_list[i] = list(input())
c = ['J', 'O', 'I']
t = [[[0]*(n+1) for i in range(m+1)] for j in range(len(c))]

for h in range(len(c)):
  for i in range(1,m+1):
    co = 0
    for j in range(n):
      if joi_list[i-1][j] == c[h]:
        co += 1
      t[h][i][j+1] = t[h][i-1][j+1] + co

ans = [0]*len(c)
for i in range(k):
  p1, q1, p2, q2 = (int (x) for x in input().split())
  for h in range(len(c)):
    ans[h] = t[h][p2][q2]-t[h][p2][q1-1]-t[h][p1-1][q2]+t[h][p1-1][q1-1]
  print(*ans)

Submission status: Accepted

Solution code:
m,n = map(int,input().split())
k = int(input())
c = [[] for i in range(m)]
for i in range(m):
    c[i] = input()
x = ["J","O","I"]

da = [[[0]*n for _ in range(m)] for _ in range(3)]

for l in range(3):
    if c[0][0] == x[l]:
        da[l][0][0] = 1
    else:
        da[l][0][0] = 0
        
    for i in range(1,n):
        if c[0][i] == x[l]:
            da[l][0][i] = da[l][0][i-1] + 1
        else:
            da[l][0][i] = da[l][0][i-1]
            
    for i in range(1,m):
        co = 0
        for j in range(n):
            if c[i][j] == x[l]:
                co += 1
            da[l][i][j] = da[l][i-1][j] + co
            
for i in range(k):
    p,q,x,y = map(int,input().split())
    p -= 1
    q -= 1
    x -= 1
    y -= 1
    ans = [0] * 3
    for j in range(3):
        if p == 0 and q == 0:
            ans[j] = da[j][x][y]
        elif p == 0:
            ans[j] = da[j][x][y] - da[j][x][q-1]
        elif q == 0:
            ans[j] = da[j][x][y] - da[j][p-1][y]
        else:
            ans[j] = da[j][x][y] - da[j][p-1][y] - da[j][x][q-1] + da[j][p-1][q-1]
            
    print(*ans)