結果

問題 No.3807 Crossword Key with Cropping (Hard)
ユーザー kidodesu
提出日時 2026-11-14 16:21:05
言語 Codon
(0.20.6)
コンパイル:
codon build -release -exe -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 4,268 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,812 ms
コンパイル使用メモリ 489,224 KB
実行使用メモリ 55,768 KB
最終ジャッジ日時 2026-11-14 16:22:10
合計ジャッジ時間 64,707 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    h, w = list(map(int, input().split()))
    S = ["#"*(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):
        for x in range(1, w-1):
            A[(y+1)*W+x+1] += A[(y+1)*W+x]+A[y*W+x+1]-A[y*W+x]
            B[(y+1)*W+x+1] += B[(y+1)*W+x]+B[y*W+x+1]-B[y*W+x]
            C[(y+1)*W+x+1] += C[(y+1)*W+x]+C[y*W+x+1]-C[y*W+x]
            D[(y+1)*W+x+1] += D[(y+1)*W+x]+D[y*W+x+1]-D[y*W+x]
            E[(y+1)*W+x+1] += E[(y+1)*W+x]+E[y*W+x+1]-E[y*W+x]
            F[(y+1)*W+x+1] += F[(y+1)*W+x]+F[y*W+x+1]-F[y*W+x]
            G[(y+1)*W+x+1] += G[(y+1)*W+x]+G[y*W+x+1]-G[y*W+x]
            H[(y+1)*W+x+1] += H[(y+1)*W+x]+H[y*W+x+1]-H[y*W+x]
            I[(y+1)*W+x+1] += I[(y+1)*W+x]+I[y*W+x+1]-I[y*W+x]
            J[(y+1)*W+x+1] += J[(y+1)*W+x]+J[y*W+x+1]-J[y*W+x]
            K[(y+1)*W+x+1] += K[(y+1)*W+x]+K[y*W+x+1]-K[y*W+x]
            s0, s1, s2, s3, s4 = S[y-1][x], S[y][x-1], S[y][x], S[y][x+1], S[y+1][x]
            if s0+s2+s4 == "#.." or s1+s2+s3 == "#.." or s0+s1+s2+s3+s4 == "##.##":
                A[(y+1)*W+x+1] += 1
            if s0+s2+s4 == "#.." or s2+s3 == "..":
                B[(y+1)*W+x+1] += 1
            if s0+s2+s4 == "#..":
                C[(y+1)*W+x+1] += 1
            if s1+s2+s3 == "#.." or s2+s4 == "..":
                D[(y+1)*W+x+1] += 1
            if s1+s2+s3 == "#..":
                E[(y+1)*W+x+1] += 1
            if s0+s2+s3+s4 == "#.##":
                F[(y+1)*W+x+1] += 1
            if s0+s1+s2+s4 == "##.#":
                G[(y+1)*W+x+1] += 1
            if s1+s2+s3+s4 == "#.##":
                H[(y+1)*W+x+1] += 1
            if s0+s1+s2+s3 == "##.#":
                I[(y+1)*W+x+1] += 1
            if s0+s2+s4 == "#.#":
                J[(y+1)*W+x+1] += 1
            if s1+s2+s3 == "#.#":
                K[(y+1)*W+x+1] += 1

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

        if 1 < y1-y0 and 1 < x1-x0:
            if S[y0][x0]+S[y0][x0+1]+S[y0+1][x0] == ".##" or S[y0][x0]+S[y0][x0+1] == ".." or S[y0][x0]+S[y0+1][x0] == "..":
                ans += 1
            if S[y0][x1-1]+S[y0][x1-2]+S[y0+1][x1-1] == ".##" or S[y0][x1-1]+S[y0+1][x1-1] == "..":
                ans += 1
            if S[y1-1][x0]+S[y1-2][x0]+S[y1-1][x0+1] == ".##" or S[y1-1][x0]+S[y1-1][x0+1] == "..":
                ans += 1
            if S[y1-1][x1-1]+S[y1-2][x1-1]+S[y1-1][x1-2] == ".##":
                ans += 1
            ans += F[(y1-1)*W+x0+1]-F[(y1-1)*W+x0]-F[(y0+1)*W+x0+1]+F[(y0+1)*W+x0]
            ans += G[(y1-1)*W+x1]-G[(y1-1)*W+x1-1]-G[(y0+1)*W+x1]+G[(y0+1)*W+x1-1]
            ans += H[(y0+1)*W+x1-1]-H[y0*W+x1-1]-H[(y0+1)*W+x0+1]+H[y0*W+x0+1]
            ans += I[y1*W+x1-1]-I[(y1-1)*W+x1-1]-I[y1*W+x0+1]+I[(y1-1)*W+x0+1]
        elif 1 < y1-y0:
            if S[y0][x0] == ".":
                ans += 1
            if S[y1-2][x0]+S[y1-1][x0] == "#.":
                ans += 1
            ans += J[(y1-1)*W+x0+1]-J[(y1-1)*W+x0]-J[(y0+1)*W+x0+1]+J[(y0+1)*W+x0]
        elif 1 < x1-x0:
            if S[y0][x0] == ".":
                ans += 1
            if S[y0][x1-2]+S[y0][x1-1] == "#.":
                ans += 1
            ans += K[(y0+1)*W+x1-1]-K[y0*W+x1-1]-K[(y0+1)*W+x0+1]+K[y0*W+x0+1]
        else:
            if S[y0][x0] == ".":
                ans += 1
        print(ans)

main()
0