結果
| 問題 | No.440 2次元チワワ問題 |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-03-31 17:40:26 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 2,075 ms / 5,000 ms |
| コード長 | 7,480 bytes |
| コンパイル時間 | 279 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 109,428 KB |
| 最終ジャッジ日時 | 2025-03-31 17:41:55 |
| 合計ジャッジ時間 | 16,081 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 26 |
ソースコード
def main():import sysinput = sys.stdin.read().split()idx = 0H = int(input[idx]); idx +=1W = int(input[idx]); idx +=1grid = []for _ in range(H):s = input[idx].strip()idx +=1grid.append(s)# Preprocess row_prefix and col_prefix# For right and leftrow_prefix = []for i in range(H):pre = [0]*(W+1)for j in range(1, W+1):pre[j] = pre[j-1] + (1 if grid[i][j-1] == 'w' else 0)row_prefix.append(pre)# For right direction: cnt_c_r, sum_rf_r, sum_rf_sq_rcnt_c_r = []sum_rf_r = []sum_rf_sq_r = []for i in range(H):cnt = [0]*(W+1)sum_rf = [0]*(W+1)sum_sq = [0]*(W+1)for j in range(1, W+1):cnt[j] = cnt[j-1]sum_rf[j] = sum_rf[j-1]sum_sq[j] = sum_sq[j-1]if grid[i][j-1] == 'c':cnt[j] +=1sum_rf[j] += row_prefix[i][j]sum_sq[j] += (row_prefix[i][j])**2cnt_c_r.append(cnt)sum_rf_r.append(sum_rf)sum_rf_sq_r.append(sum_sq)# For left direction: sum_row_prev# sum_rp_l[i][j] is sum of row_prefix[i][k-1] for k in 1..j where s[i][k-1] is 'c'sum_rp_l = []sum_rp_sq_l = []cnt_c_l = []for i in range(H):cnt = [0]*(W+1)sum_rp = [0]*(W+1)sum_sq = [0]*(W+1)for j in range(1, W+1):cnt[j] = cnt[j-1]sum_rp[j] = sum_rp[j-1]sum_sq[j] = sum_sq[j-1]if grid[i][j-1] == 'c':cnt[j] +=1rp = row_prefix[i][j-1]sum_rp[j] += rpsum_sq[j] += rp * rpcnt_c_l.append(cnt)sum_rp_l.append(sum_rp)sum_rp_sq_l.append(sum_sq)# Preprocess col_prefix for up and downcol_prefix = []for j in range(W):pre = [0]*(H+1)for i in range(1, H+1):pre[i] = pre[i-1] + (1 if grid[i-1][j] == 'w' else 0)col_prefix.append(pre)# For down direction: cnt_ccol_d, sum_cf_d, sum_cf_sq_dcnt_ccol_d = []sum_cf_d = []sum_cf_sq_d = []for j in range(W):cnt = [0]*(H+1)sum_cf = [0]*(H+1)sum_sq = [0]*(H+1)for i in range(1, H+1):cnt[i] = cnt[i-1]sum_cf[i] = sum_cf[i-1]sum_sq[i] = sum_sq[i-1]if grid[i-1][j] == 'c':cnt[i] +=1sum_cf[i] += col_prefix[j][i]sum_sq[i] += (col_prefix[j][i])**2cnt_ccol_d.append(cnt)sum_cf_d.append(sum_cf)sum_cf_sq_d.append(sum_sq)# For up directioncnt_ccol_u = []sum_cp_u = []sum_cp_sq_u = []for j in range(W):cnt = [0]*(H+1)sum_cp = [0]*(H+1)sum_sq = [0]*(H+1)for i in range(1, H+1):cnt[i] = cnt[i-1]sum_cp[i] = sum_cp[i-1]sum_sq[i] = sum_sq[i-1]if grid[i-1][j] == 'c':cnt[i] +=1cp = col_prefix[j][i-1]sum_cp[i] += cpsum_sq[i] += cp * cpcnt_ccol_u.append(cnt)sum_cp_u.append(sum_cp)sum_cp_sq_u.append(sum_sq)Q = int(input[idx]); idx +=1for _ in range(Q):a = int(input[idx])-1; idx +=1b = int(input[idx])-1; idx +=1c = int(input[idx])-1; idx +=1d = int(input[idx])-1; idx +=1a_row = ac_row = cb_col = bd_col = dres = 0# Right directionfor i in range(a_row, c_row+1):# j: b_col <= j <= d_colj_min = b_col +1 # 0-based j in grid is j+1 in 1-basedj_max = d_col +1 # converted to 1-based for the row_prefixj_min_1based = b_col +1j_max_1based = d_col +1current_row = row_prefix[i]current_row_d = current_row[d_col+1]# get count of 'c' in row[i], columns [b_col..d_col] (0-based)# to 1-based: [b_col+1, d_col+1]cnt = cnt_c_r[i][j_max_1based] - cnt_c_r[i][j_min_1based -1]if cnt ==0:continuesum_rf = sum_rf_r[i][j_max_1based] - sum_rf_r[i][j_min_1based -1]sum_rf_sq = sum_rf_sq_r[i][j_max_1based] - sum_rf_sq_r[i][j_min_1based -1]sum_k = current_row_d * cnt - sum_rfsum_k_squared = (current_row_d * current_row_d) * cnt - 2 * current_row_d * sum_rf + sum_rf_sqcontribution = (sum_k_squared - sum_k) //2res += contribution# Left directionfor i in range(a_row, c_row+1):j_min = b_colj_max = d_col# j: from j_min+1 (0-based) to j_max+1 (1-based)j_min_1based = (b_col) +1j_max_1based = (d_col) +1current_row = row_prefix[i]# Left k is row[i][b..j-1] where j is in [b..d]prev_val = row_prefix[i][b_col] if b_col >=0 else 0# for j in [b_col..d_col], s[i][j] == 'c'# sum_row_prev for j's columns (0-based)cnt = cnt_c_l[i][j_max_1based] - cnt_c_l[i][j_min_1based -1]if cnt ==0:continuesum_rp = sum_rp_l[i][j_max_1based] - sum_rp_l[i][j_min_1based -1]sum_rp_sq = sum_rp_sq_l[i][j_max_1based] - sum_rp_sq_l[i][j_min_1based -1]sum_k = sum_rp - prev_val * cntsum_k_squared = sum_rp_sq - 2 * prev_val * sum_rp + (prev_val **2) * cntcontribution = (sum_k_squared - sum_k) //2res += contribution# Down directionfor j in range(b_col, d_col +1):# i from a_row to c_row, where s[i][j] == 'c'# compute for each i in a_row <= i <= c_row# down k: i+1 to c_row in the same column ji_min = a_rowi_max = c_rowif i_min <0 or i_max >=H:continuecurrent_col = col_prefix[j]current_col_c = current_col[c_row +1]cnt = cnt_ccol_d[j][i_max +1] - cnt_ccol_d[j][i_min]if cnt ==0:continuesum_cf = sum_cf_d[j][i_max +1] - sum_cf_d[j][i_min]sum_cf_sq = sum_cf_sq_d[j][i_max +1] - sum_cf_sq_d[j][i_min]sum_k = current_col_c * cnt - sum_cfsum_k_squared = (current_col_c **2)*cnt - 2*current_col_c*sum_cf + sum_cf_sqcontribution = (sum_k_squared - sum_k) //2res += contribution# Up directionfor j in range(b_col, d_col +1):# i in a_row <= i <=c_row, and s[i][j] == 'c'# up k: from a to i-1 in column ja_prev = a_rowcurrent_col = col_prefix[j]if a_prev -1 <0:current_col_a_prev = 0else:current_col_a_prev = current_col[a_prev]cnt = cnt_ccol_u[j][c_row +1] - cnt_ccol_u[j][a_prev]if cnt ==0:continuesum_cp = sum_cp_u[j][c_row +1] - sum_cp_u[j][a_prev]sum_cp_sq = sum_cp_sq_u[j][c_row +1] - sum_cp_sq_u[j][a_prev]sum_k = sum_cp - current_col_a_prev * cntsum_k_squared = sum_cp_sq - 2 * current_col_a_prev * sum_cp + (current_col_a_prev **2) * cntcontribution = (sum_k_squared - sum_k) //2res += contributionprint(res)if __name__ == '__main__':main()