結果

問題 No.440 2次元チワワ問題
ユーザー lam6er
提出日時 2025-03-20 18:58:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,649 bytes
コンパイル時間 472 ms
コンパイル使用メモリ 82,924 KB
実行使用メモリ 88,948 KB
最終ジャッジ日時 2025-03-20 18:59:11
合計ジャッジ時間 16,100 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    H = int(input[ptr])
    ptr +=1
    W = int(input[ptr])
    ptr +=1
    
    rows = [[] for _ in range(H+1)]  # rows[1..H], each stores columns with 'c' sorted
    grid = []
    for i in range(H):
        s = input[ptr]
        ptr +=1
        grid.append(s)
        row = []
        for j in range(W):
            if s[j] == 'c':
                row.append(j+1)  # 1-based
        rows[i+1] = sorted(row)
    
    # Preprocess prefix_right (row-based, from j to W)
    prefix_right = [[0]*(W+2) for _ in range(H+2)]
    for i in range(1, H+1):
        prefix_right[i][W+1] = 0
        for j in range(W, 0, -1):
            prefix_right[i][j] = prefix_right[i][j+1] + (1 if grid[i-1][j-1] == 'w' else 0)
    
    # Preprocess prefix_left (row-based, from 1 to j)
    prefix_left = [[0]*(W+2) for _ in range(H+2)]
    for i in range(1, H+1):
        for j in range(1, W+1):
            prefix_left[i][j] = prefix_left[i][j-1] + (1 if grid[i-1][j-1] == 'w' else 0)
    
    # Preprocess prefix_down (column-based, from i to H)
    prefix_down = [[0]*(H+2) for _ in range(W+2)]
    for j in range(1, W+1):
        prefix_down[j][H+1] = 0
        for i in range(H, 0, -1):
            prefix_down[j][i] = prefix_down[j][i+1] + (1 if grid[i-1][j-1] == 'w' else 0)
    
    # Preprocess prefix_up (column-based, from 1 to i)
    prefix_up = [[0]*(H+2) for _ in range(W+2)]
    for j in range(1, W+1):
        for i in range(1, H+1):
            prefix_up[j][i] = prefix_up[j][i-1] + (1 if grid[i-1][j-1] == 'w' else 0)
    
    Q = int(input[ptr])
    ptr +=1
    for _ in range(Q):
        a = int(input[ptr])
        ptr +=1
        b = int(input[ptr])
        ptr +=1
        c = int(input[ptr])
        ptr +=1
        d = int(input[ptr])
        ptr +=1
        
        total = 0
        
        for i in range(a, c+1):
            row_c = rows[i]
            left = bisect.bisect_left(row_c, b)
            right_idx = bisect.bisect_right(row_c, d)
            for j in row_c[left:right_idx]:
                # Right direction
                start_j_r = j +1
                end_j_r = d
                if start_j_r > end_j_r:
                    x_r = 0
                else:
                    x_r = prefix_right[i][start_j_r] - prefix_right[i][end_j_r +1]
                combo_r = x_r * (x_r -1) // 2 if x_r >=2 else 0
                total += combo_r
                
                # Left direction
                end_j_l = j -1
                start_j_l = b
                if start_j_l > end_j_l:
                    x_l = 0
                else:
                    x_l = prefix_left[i][end_j_l] - prefix_left[i][start_j_l -1]
                combo_l = x_l * (x_l -1) //2 if x_l >=2 else 0
                total += combo_l
                
                # Down direction
                start_i_d = i +1
                end_i_d = c
                if start_i_d > end_i_d:
                    x_d =0
                else:
                    x_d = prefix_down[j][start_i_d] - prefix_down[j][end_i_d +1]
                combo_d = x_d * (x_d -1) //2 if x_d >=2 else 0
                total += combo_d
                
                # Up direction
                end_i_u = i -1
                start_i_u = a
                if start_i_u > end_i_u:
                    x_u =0
                else:
                    x_u = prefix_up[j][end_i_u] - prefix_up[j][start_i_u -1]
                combo_u = x_u * (x_u -1) //2 if x_u >=2 else 0
                total += combo_u
        
        print(total)

if __name__ == "__main__":
    main()
0