読者です 読者をやめる 読者になる 読者になる

Codeforces Good Bye 2015 C: New Year and Domino

解法

2次元の累積和。

kenkoooo.hatenablog.com

コード

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>

using namespace std;
typedef signed long long ll;

#define ALL(a) (a.begin()), (a.end())
#define UNIQUE(a) a.erase(unique(a.begin(), a.end()), a.end())

template <class T>
class CumulativeSum {
  int ny, nx;
  vector<vector<T>> sum;

 public:
  CumulativeSum(const vector<vector<T>>& a) {
    ny = a.size();
    nx = a[0].size();
    sum.assign(ny + 1, vector<T>(nx + 1, 0));
    for (int i = 0; i < ny; ++i) {
      for (int j = 0; j < nx; ++j) {
        sum[i + 1][j + 1] = a[i][j] + sum[i][j + 1] + sum[i + 1][j] - sum[i][j];
      }
    }
  }

  T getSum(int y1, int x1, int y2, int x2) {
    if (y1 > y2 || x1 > x2) return 0;
    y1 = max(y1, 0);
    x1 = max(x1, 0);
    y2 = min(y2, ny - 1);
    x2 = min(x2, nx - 1);
    return sum[y2 + 1][x2 + 1] - sum[y1][x2 + 1] - sum[y2 + 1][x1] +
           sum[y1][x1];
  }
};

int main() {
  ios::sync_with_stdio(false);
  int H, W;
  cin >> H >> W;
  vector<string> board(H);
  for (int i = 0; i < H; ++i) {
    cin >> board[i];
  }
  vector<vector<int>> right(H, vector<int>(W, 0));
  vector<vector<int>> down(H, vector<int>(W, 0));
  for (int h = 0; h < H; ++h) {
    for (int w = 0; w < W; ++w) {
      if (board[h][w] != '.') continue;
      if (h < H - 1 && board[h + 1][w] == '.') down[h][w]++;
      if (w < W - 1 && board[h][w + 1] == '.') right[h][w]++;
    }
  }

  CumulativeSum<int> cs_down(down);
  CumulativeSum<int> cs_right(right);

  int Q;
  cin >> Q;
  for (int query = 0; query < Q; ++query) {
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    r1--, c1--, r2--, c2--;

    int ret = cs_down.getSum(r1, c1, r2, c2) + cs_right.getSum(r1, c1, r2, c2);
    if (r2 < H - 1) ret -= cs_down.getSum(r2, c1, r2, c2);
    if (c2 < W - 1) ret -= cs_right.getSum(r1, c2, r2, c2);
    cout << ret << endl;
  }
}