Submission #775852

#	Time	Username	Problem	Language	Result	Execution time	Memory
775852		gun_gan	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	583 ms	75116 KiB

joi2019_ho_t1

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

const int MX = 3e3 + 7;
int N, M;
vector<int> vert[MX], hori[MX];
vector<pair<int, int>> pos;

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      cin >> N >> M;
      for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                  char c;
                  cin >> c;

                  if(c == 'J') {
                        pos.push_back({i, j});
                  } else if(c == 'O') {
                        hori[i].push_back(j);
                  } else {
                        vert[j].push_back(i);
                  }     
            }
      }

      ll ans = 0;
      for(auto [x, y] : pos) {
            auto p = lower_bound(hori[x].begin(), hori[x].end(), y) - hori[x].begin();
            auto q = lower_bound(vert[y].begin(), vert[y].end(), x) - vert[y].begin();

            ans += 1LL * (hori[x].size() - p) * (vert[y].size() - q);
      }

      cout << ans << '\n';
            
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50