Submission #1263952

#TimeUsernameProblemLanguageResultExecution timeMemory
1263952thewizardmanBitaro the Brave (JOI19_ho_t1)C++20
100 / 100
248 ms98988 KiB
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;

int n, m, O[3000][3000], I[3000][3000];
ll ans;
string s;
vector<pii> J;

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> s;
    for (int j = 0; j < m; j++) {
      if (s[j] == 'J') J.push_back({i, j});
      else if (s[j] == 'O') O[i][j]++;
      else if (s[j] == 'I') I[i][j]++;
    }
  }
  for (int i = 0; i < n; i++) for (int j = m-1; j > 0; j--) {
    int l = (j & (j+1)) - 1;
    if (l >= 0) O[i][l] += O[i][j];
  }
  for (int j = 0; j < m; j++) for (int i = n-1; i > 0; i--) {
    int l = (i & (i+1)) - 1;
    if (l >= 0) I[l][j] += I[i][j];
  }
  for (const auto &[x, y]: J) {
    int a = 0, b = 0;
    for (int j = y; j < m; j = j | (j+1)) a += O[x][j];
    for (int i = x; i < n; i = i | (i+1)) b += I[i][y];
    ans += (ll) a * b;
  }
  cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...