結果

問題 No.440 2次元チワワ問題
ユーザー yuki681yuki681
提出日時 2016-10-30 06:18:02
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 781 ms / 5,000 ms
コード長 3,499 bytes
コンパイル時間 1,236 ms
コンパイル使用メモリ 148,264 KB
実行使用メモリ 36,708 KB
最終ジャッジ日時 2023-08-16 11:13:38
合計ジャッジ時間 8,167 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 6 ms
6,920 KB
testcase_05 AC 4 ms
5,532 KB
testcase_06 AC 3 ms
4,516 KB
testcase_07 AC 26 ms
16,092 KB
testcase_08 AC 53 ms
18,520 KB
testcase_09 AC 100 ms
27,644 KB
testcase_10 AC 28 ms
19,724 KB
testcase_11 AC 28 ms
11,988 KB
testcase_12 AC 34 ms
20,600 KB
testcase_13 AC 99 ms
29,908 KB
testcase_14 AC 8 ms
5,920 KB
testcase_15 AC 99 ms
31,272 KB
testcase_16 AC 20 ms
4,872 KB
testcase_17 AC 151 ms
36,596 KB
testcase_18 AC 149 ms
36,708 KB
testcase_19 AC 153 ms
36,520 KB
testcase_20 AC 150 ms
36,652 KB
testcase_21 AC 781 ms
36,600 KB
testcase_22 AC 766 ms
36,612 KB
testcase_23 AC 770 ms
36,684 KB
testcase_24 AC 781 ms
36,616 KB
testcase_25 AC 781 ms
36,700 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long int
using namespace std;

int H, W, Q;
char S[514][514];
int A[10010], B[10010], C[10010], D[10010];

int c[4][514][514], cw[4][514][514], cww[4][514][514], w[4][514][514];
int ans[10010];

signed main()
{
  cin >> H >> W;
  for(int i = 1; i <= H; i++){
    for(int j = 1; j <= W; j++){
      cin >> S[i][j];
    }
  }
  cin >> Q;
  for(int i = 1; i <= Q; i++){
    cin >> A[i] >> B[i] >> C[i] >> D[i];
  }


  for(int i = 1; i <= H; i++){
    for(int j = 1; j <= W; j++){
      if(S[i][j] == 'c'){
	c[0][i][j] = c[0][i][j - 1] + 1;
	cw[0][i][j] = cw[0][i][j - 1];
	cww[0][i][j] = cww[0][i][j - 1];
	w[0][i][j] = w[0][i][j - 1];
      }
      if(S[i][j] == 'w'){
	c[0][i][j] = c[0][i][j - 1];
	cw[0][i][j] = cw[0][i][j - 1] + c[0][i][j - 1];
	cww[0][i][j] = cww[0][i][j - 1] + cw[0][i][j - 1];
	w[0][i][j] = w[0][i][j - 1] + 1;
      }
    }
  }
  
  for(int i = 1; i <= Q; i++){
    for(int j = A[i]; j <= C[i]; j++){
      ans[i] += cww[0][j][D[i]] - cww[0][j][B[i] - 1] - cw[0][j][B[i] - 1] * (w[0][j][D[i]] - w[0][j][B[i] - 1]) - c[0][j][B[i] - 1] * ((w[0][j][D[i]] - w[0][j][B[i] - 1] - 1) * (w[0][j][D[i]] - w[0][j][B[i] - 1]) / 2);
    }
  }
  

  for(int i = 1; i <= H; i++){
    for(int j = W; j >= 1; j--){
      if(S[i][j] == 'c'){
	c[1][i][j] = c[1][i][j + 1] + 1;
	cw[1][i][j] = cw[1][i][j + 1];
	cww[1][i][j] = cww[1][i][j + 1];
	w[1][i][j] = w[1][i][j + 1];
      }
      if(S[i][j] == 'w'){
	c[1][i][j] = c[1][i][j + 1];
	cw[1][i][j] = cw[1][i][j + 1] + c[1][i][j + 1];
	cww[1][i][j] = cww[1][i][j + 1] + cw[1][i][j + 1];
	w[1][i][j] = w[1][i][j + 1] + 1;
      }
    }
  }

  for(int i = 1; i <= Q; i++){
    for(int j = A[i]; j <= C[i]; j++){
      ans[i] += cww[1][j][B[i]] - cww[1][j][D[i] + 1] - cw[1][j][D[i] + 1] * (w[1][j][B[i]] - w[1][j][D[i] + 1]) - c[1][j][D[i] + 1] * ((w[1][j][B[i]] - w[1][j][D[i] + 1] - 1) * (w[1][j][B[i]] - w[1][j][D[i] + 1]) / 2);
    }
  }
  

  for(int i = 1; i <= W; i++){
    for(int j = 1; j <= H; j++){
      if(S[j][i] == 'c'){
	c[2][i][j] = c[2][i][j - 1] + 1;
	cw[2][i][j] = cw[2][i][j - 1];
	cww[2][i][j] = cww[2][i][j - 1];
	w[2][i][j] = w[2][i][j - 1];
      }
      if(S[j][i] == 'w'){
	c[2][i][j] = c[2][i][j - 1];
	cw[2][i][j] = cw[2][i][j - 1] + c[2][i][j - 1];
	cww[2][i][j] = cww[2][i][j - 1] + cw[2][i][j - 1];
	w[2][i][j] = w[2][i][j - 1] + 1;
      }
    }
  }

  for(int i = 1; i <= Q; i++){
    for(int j = B[i]; j <= D[i]; j++){
      ans[i] += cww[2][j][C[i]] - cww[2][j][A[i] - 1] - cw[2][j][A[i] - 1] * (w[2][j][C[i]] - w[2][j][A[i] - 1]) - c[2][j][A[i] - 1] * ((w[2][j][C[i]] - w[2][j][A[i] - 1] - 1) * (w[2][j][C[i]] - w[2][j][A[i] - 1]) / 2);
    }
  }


  for(int i = 1; i <= W; i++){
    for(int j = H; j >= 1; j--){
      if(S[j][i] == 'c'){
	c[3][i][j] = c[3][i][j + 1] + 1;
	cw[3][i][j] = cw[3][i][j + 1];
	cww[3][i][j] = cww[3][i][j + 1];
	w[3][i][j] = w[3][i][j + 1];
      }
      if(S[j][i] == 'w'){
	c[3][i][j] = c[3][i][j + 1];
	cw[3][i][j] = cw[3][i][j + 1] + c[3][i][j + 1];
	cww[3][i][j] = cww[3][i][j + 1] + cw[3][i][j + 1];
	w[3][i][j] = w[3][i][j + 1] + 1;
      }
    }
  }

  for(int i = 1; i <= Q; i++){
    for(int j = B[i]; j <= D[i]; j++){
      ans[i] += cww[3][j][A[i]] - cww[3][j][C[i] + 1] - cw[3][j][C[i] + 1] * (w[3][j][A[i]] - w[3][j][C[i] + 1]) - c[3][j][C[i] + 1] * ((w[3][j][A[i]] - w[3][j][C[i] + 1] - 1) * (w[3][j][A[i]] - w[3][j][C[i] + 1]) / 2);
    }
  }


  for(int i = 1; i <= Q; i++){
    cout << ans[i] << endl;
  }

  return 0;
}
0