oj.uz

Submission #250814

# Submission time Handle Problem Language Result Execution time Memory
250814 2020-07-19T08:18:01 Z VEGAnn Raspad (COI17_raspad) C++14
0 / 100
 338 ms 13048 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100100;
const int M = 53;
ll ans = 0;
bool tp[N][M];
int n, m, pre[N * M], lft[M][M], rgt[M][M], clf[M], crt[M];
ll ans_lf[M], ans_rt[M];

int get(int x) { return (pre[x] == x ? pre[x] : pre[x] = get(pre[x])); }

void calc(int lf, int rt){
    if (lf == rt){
        ans += tp[lf][0];

        for (int j = 1; j < m; j++){
            if (!tp[lf][j]) continue;

            if (!tp[lf][j - 1])
                ans++;
        }
        return;
    }

    int ko_lf = 1, ko_rt = 1;

    int md = (lf + rt) >> 1;

    // left side

    int siz = 0;

    for (int j = 0; j < m; j++){
        int loc = md * m + j;

        pre[loc] = loc;

        if (!tp[md][j]) continue;

        siz++;

        if (j > 0 && tp[md][j - 1]) {
            pre[loc] = get(pre[loc - 1]);
            siz--;
        }
    }

    ans_lf[0] = siz;
    clf[0] = 1;

    for (int j = 0; j < m; j++)
        lft[0][j] = get(pre[md * m + j]);

    for (int row = md - 1; row >= lf; row--){
        for (int j = 0; j < m; j++){
            if (!tp[row][j]) continue;

            siz++;

            int loc = row * m + j;

            pre[loc] = loc;

            if (j > 0 && tp[row][j - 1]) {
                pre[loc] = get(pre[loc - 1]);
                siz--;
            }

            if (tp[row + 1][j] && get(loc) != get(loc + m)){
                siz--;
                pre[loc] = get(loc + m);
            }
        }

        bool was = 0;

        for (int j = 0; j < m; j++) {
            lft[ko_lf][j] = get(pre[md * m + j]);

            if (lft[ko_lf][j] != lft[ko_lf - 1][j])
                was = 1;
        }

        if (was){
            clf[ko_lf] = 1;
            ans_lf[ko_lf] = siz;
            ko_lf++;
        } else {
            clf[ko_lf - 1]++;
            ans_lf[ko_lf - 1] += siz;
        }
    }

    // right side

    siz = 0;

    for (int j = 0; j < m; j++){
        int loc = md * m + m + j;

        pre[loc] = loc;

        if (!tp[md + 1][j]) continue;

        siz++;

        if (j > 0 && tp[md + 1][j - 1]) {
            pre[loc] = get(pre[loc - 1]);
            siz--;
        }
    }

    ans_rt[0] = siz;

    crt[0] = 1;

    for (int j = 0; j < m; j++)
        rgt[0][j] = get(pre[md * m + m + j]);

    for (int row = md + 2; row <= rt; row++){
        for (int j = 0; j < m; j++){
            if (!tp[row][j]) continue;

            siz++;

            int loc = row * m + j;

            pre[loc] = loc;

            if (j > 0 && tp[row][j - 1]) {
                pre[loc] = get(pre[loc - 1]);
                siz--;
            }

            if (tp[row - 1][j] && get(loc) != get(loc - m)){
                siz--;
                pre[loc] = get(loc - m);
            }
        }

        bool was = 0;

        for (int j = 0; j < m; j++) {
            rgt[ko_rt][j] = get(pre[md * m + m + j]);

            if (rgt[ko_rt][j] != rgt[ko_rt - 1][j])
                was = 1;
        }

        if (was){
            crt[ko_rt] = 1;
            ans_rt[ko_rt] = siz;
            ko_rt++;
        } else {
            crt[ko_rt - 1]++;
            ans_rt[ko_rt - 1] += siz;
        }
    }

    for (int le = 0; le < ko_lf; le++)
    for (int ri = 0; ri < ko_rt; ri++){
        ll nw = 0, dlt = ll(crt[ri]) * ll(clf[le]);

        ans += ans_lf[le] * ll(crt[ri]) + ans_rt[ri] * ll(clf[le]);

        for (int j = 0; j < m; j++){
            pre[pre[rgt[ri][j]]] = pre[rgt[ri][j]];
            pre[pre[lft[le][j]]] = pre[lft[le][j]];
        }

        for (int j = 0; j < m; j++){
            if (!tp[md][j] || !tp[md + 1][j]) continue;

            int fi = get(pre[rgt[ri][j]]);
            int se = get(pre[lft[le][j]]);

            if (fi == se) continue;

            nw++;

            pre[fi] = se;
        }

        ans -= dlt * nw;
    }

    calc(lf, md);
    calc(md + 1, rt);
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++){
        char c; cin >> c;
        tp[i][j] = (c - '0');
    }

    calc(0, n - 1);

    cout << ans;

    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 6400 KB Output is correct
2 Incorrect 338 ms 13048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -