Submission #996948

#	Time	Username	Problem	Language	Result	Execution time	Memory
996948		coolboy19521	Bitaro the Brave (JOI19_ho_t1)	C++17	50 / 100	1075 ms	77796 KiB

joi2019_ho_t1

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int sz = 3e3 + 9;

char a[sz][sz];

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int h, w;
    cin >> h >> w;

    map <int, vector <int>> os, is;
    int r = 0;

    for (int i = 1; i <= h; i ++) {
        for (int j = 1; j <= w; j ++) {
            cin >> a[i][j];

            if ('O' == a[i][j]) {
                os[i].push_back(j);
            } else if ('I' == a[i][j]) {
                is[j].push_back(i);
            }
        }
    }

    for (auto& i : os) {
        sort(begin(i.second), end(i.second));
    }

    for (auto& i : is) {
        sort(begin(i.second), end(i.second));
    }

    for (int i = 1; i <= h; i ++) {
        for (int j = 1; j <= w; j ++) {
            if ('J' == a[i][j]) {
                int oc = os[i].end() - upper_bound(begin(os[i]), end(os[i]), j);
                int ic = is[j].end() - upper_bound(begin(is[j]), end(is[j]), i);
                r += oc * ic;
            }
        }
    }

    cout << r << '\n';
}

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