[JOI精進録] 難易度5「惑星探査」(第10回日本情報オリンピック 本選A)

問題リンク

atcoder.jp

問題概要

この惑星には3種類の地形がある。以下のクエリが個与えられるので、答えなさい。
・(,)、(,)の長方形領域に各地形がどれだけ含まれているか

解説

AC解法 (100/100点)

地形ごとに二次元累積和を持ち、クエリごとにで答えられるようにすればよいです。

ACコード

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

int main(){
  int m,n,q; cin >> m >> n >> q;
  char c;
  vector J(m+1,vector<int>(n+1)),O=J,I=J;
  for (int i(0);i < m;++i) for (int k(0);k < n;++k){
    cin >> c;
    J[i+1][k+1]=J[i+1][k]+J[i][k+1]-J[i][k]+(c=='J');
    O[i+1][k+1]=O[i+1][k]+O[i][k+1]-O[i][k]+(c=='O');
    I[i+1][k+1]=I[i+1][k]+I[i][k+1]-I[i][k]+(c=='I');
  }
  while(q--){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    cout << J[c][d]-J[c][b-1]-J[a-1][d]+J[a-1][b-1] << ' ';
    cout << O[c][d]-O[c][b-1]-O[a-1][d]+O[a-1][b-1] << ' ';
    cout << I[c][d]-I[c][b-1]-I[a-1][d]+I[a-1][b-1] << '\n';
  }
  cout.flush();
}

提出結果

atcoder.jp