結果

問題 No.3807 Crossword Key with Cropping (Hard)
ユーザー kidodesu
提出日時 2026-11-14 16:40:38
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 4,019 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 86 ms
コンパイル使用メモリ 64,364 KB
実行使用メモリ 125,012 KB
最終ジャッジ日時 2026-11-14 16:41:56
合計ジャッジ時間 77,327 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31 TLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    h, w = map(int, input().split())
    S = "".join(["#"*(w+2)] + ["#"+input()+"#" for _ in range(h)] + ["#"*(w+2)])
    h += 2
    w += 2
    A = [0] * (h+1)*(w+1)
    B = [0] * (h+1)*(w+1)
    C = [0] * (h+1)*(w+1)
    D = [0] * (h+1)*(w+1)
    E = [0] * (h+1)*(w+1)
    F = [0] * (h+1)*(w+1)
    G = [0] * (h+1)*(w+1)
    H = [0] * (h+1)*(w+1)
    I = [0] * (h+1)*(w+1)
    J = [0] * (h+1)*(w+1)
    K = [0] * (h+1)*(w+1)
    W = w+1

    for y in range(1, h-1):
        base = (y+1)*W + 1
        row = y*w
        for x in range(1, w-1):
            p = base + x
            q = p - W
            A[p] += A[p-1] + A[q] - A[q-1]
            B[p] += B[p-1] + B[q] - B[q-1]
            C[p] += C[p-1] + C[q] - C[q-1]
            D[p] += D[p-1] + D[q] - D[q-1]
            E[p] += E[p-1] + E[q] - E[q-1]
            F[p] += F[p-1] + F[q] - F[q-1]
            G[p] += G[p-1] + G[q] - G[q-1]
            H[p] += H[p-1] + H[q] - H[q-1]
            I[p] += I[p-1] + I[q] - I[q-1]
            J[p] += J[p-1] + J[q] - J[q-1]
            K[p] += K[p-1] + K[q] - K[q-1]
            s = row + x
            s2 = S[s]
            if s2 != ".":
                continue
            s0, s1, s3, s4 = S[s-w], S[s-1], S[s+1], S[s+w]
            t024 = s0+s2+s4
            t123 = s1+s2+s3
            if t024 == "#.." or t123 == "#.." or s0+s1+s2+s3+s4 == "##.##":
                A[p] += 1
            if t024 == "#.." or s2+s3 == "..":
                B[p] += 1
            if t024 == "#..":
                C[p] += 1
            if t123 == "#.." or s2+s4 == "..":
                D[p] += 1
            if t123 == "#..":
                E[p] += 1
            if s0+s2+s3+s4 == "#.##":
                F[p] += 1
            if s0+s1+s2+s4 == "##.#":
                G[p] += 1
            if s1+s2+s3+s4 == "#.##":
                H[p] += 1
            if s0+s1+s2+s3 == "##.#":
                I[p] += 1
            if t024 == "#.#":
                J[p] += 1
            if t123 == "#.#":
                K[p] += 1

    out = []
    for _ in range(int(input())):
        y0, x0, y1, x1 = map(int, input().split())
        y1, x1 = y1+1, x1+1
        Y0 = y0*W
        Y0p = Y0 + W
        Y1 = y1*W
        Y1m = Y1 - W
        r0 = y0*w
        r1 = (y1-1)*w
        ans = 0
        if 2 < min(y1-y0, x1-x0):
            ans += A[Y1m+x1-1]+A[Y0p+x0+1]-A[Y1m+x0+1]-A[Y0p+x1-1]
        if 2 < y1-y0:
            if 1 < x1-x0:
                ans += B[Y1m+x0+1]-B[Y1m+x0]-B[Y0p+x0+1]+B[Y0p+x0]
            ans += C[Y1m+x1]-C[Y1m+x1-1]-C[Y0p+x1]+C[Y0p+x1-1]
        if 2 < x1-x0:
            if 1 < y1-y0:
                ans += D[Y0p+x1-1]-D[Y0+x1-1]-D[Y0p+x0+1]+D[Y0+x0+1]
            ans += E[Y1+x1-1]-E[Y1m+x1-1]-E[Y1+x0+1]+E[Y1m+x0+1]

        if 1 < y1-y0 and 1 < x1-x0:
            if S[r0+x0]+S[r0+x0+1]+S[r0+w+x0] == ".##" or S[r0+x0]+S[r0+x0+1] == ".." or S[r0+x0]+S[r0+w+x0] == "..":
                ans += 1
            if S[r0+x1-1]+S[r0+x1-2]+S[r0+w+x1-1] == ".##" or S[r0+x1-1]+S[r0+w+x1-1] == "..":
                ans += 1
            if S[r1+x0]+S[r1-w+x0]+S[r1+x0+1] == ".##" or S[r1+x0]+S[r1+x0+1] == "..":
                ans += 1
            if S[r1+x1-1]+S[r1-w+x1-1]+S[r1+x1-2] == ".##":
                ans += 1
            ans += F[Y1m+x0+1]-F[Y1m+x0]-F[Y0p+x0+1]+F[Y0p+x0]
            ans += G[Y1m+x1]-G[Y1m+x1-1]-G[Y0p+x1]+G[Y0p+x1-1]
            ans += H[Y0p+x1-1]-H[Y0+x1-1]-H[Y0p+x0+1]+H[Y0+x0+1]
            ans += I[Y1+x1-1]-I[Y1m+x1-1]-I[Y1+x0+1]+I[Y1m+x0+1]
        elif 1 < y1-y0:
            if S[r0+x0] == ".":
                ans += 1
            if S[r1-w+x0]+S[r1+x0] == "#.":
                ans += 1
            ans += J[Y1m+x0+1]-J[Y1m+x0]-J[Y0p+x0+1]+J[Y0p+x0]
        elif 1 < x1-x0:
            if S[r0+x0] == ".":
                ans += 1
            if S[r0+x1-2]+S[r0+x1-1] == "#.":
                ans += 1
            ans += K[Y0p+x1-1]-K[Y0+x1-1]-K[Y0p+x0+1]+K[Y0+x0+1]
        else:
            if S[r0+x0] == ".":
                ans += 1
        print(ans)

main()
0