Submission #529443

#	Time	Username	Problem	Language	Result	Execution time	Memory
529443		leu_naut	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	409 ms	109640 KiB

joi2019_ho_t1

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 3e3;
const int MOD = 1e9 + 7;
const ll oo = 1e18;


int n,m;
char a[N + 5][N + 5];
int bit[2][N + 5][N + 5];
vector <int> cntJ[N + 5];

void upd(int x, int tp, int z)
{
    for (; x <= N; x += x & -x) bit[z][tp][x]++;
}

int get(int x, int tp, int z)
{
    int ans = 0;
    while (x > 0) {
        ans += bit[z][tp][x];
        x -= x & -x;
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);  cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; ++j) {
            a[i][j] = s[j - 1];
            if (a[i][j] == 'O') upd(j,i,0);
            else if (a[i][j] == 'I') upd(i,j,1);
            else cntJ[j].push_back(i);
        }
    }

    ll ans = 0;

    for (int j = 1; j <= m; ++j) {
        for (int i : cntJ[j]) {
            ll tmpI = get(n,j,1) - get(i,j,1);
            ll tmpO = get(m,i,0) - get(j,i,0);
            //cout << j << ' ' << i << ' ' << tmpI << ' ' << tmpO << '\n';
            ans = ans + tmpI * tmpO;
        }
    }
    cout << ans;
}

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