Submission #1273763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273763		nanaseyuzuki	Bitaro the Brave (JOI19_ho_t1)	C++20	100 / 100	608 ms	132840 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 3e3 + 5, bm = (1 << 11) + 1, mod = 1e9 + 7, offset = 5e4;
const int inf = 1e18, base = 311;

int h, w;
char a[mn][mn];
vector <int> col[mn], row[mn];

void solve(){
    cin >> h >> w;
    vector <pii> xet;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> a[i][j];
            if(a[i][j] == 'J') xet.push_back({i, j});
            if(a[i][j] == 'O') row[i].push_back(j);
            if(a[i][j] == 'I') col[j].push_back(i);
        }
    }
    for(int i = 1; i <= h; i++) sort(all(row[i]));
    for(int j = 1; j <= w; j++) sort(all(col[j]));
    int res = 0;
    for(auto [i, j] : xet){
        int num_row = row[i].end() - upper_bound(all(row[i]), j);
        int num_col = col[j].end() - upper_bound(all(col[j]), i);
        res += num_row * num_col;
    }
    cout << res << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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