oj.uz

Submission #250829

# Submission time Handle Problem Language Result Execution time Memory
250829 2020-07-19T09:16:19 Z VEGAnn Raspad (COI17_raspad) C++14
61 / 100
 973 ms 82552 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100100;
const int M = 210;
ll ans = 0;
bool tp[N][M];
int n, m, pre[N * M], lft[M][M], rgt[M][M], clf[M], crt[M];
int lst[N * M], ind[N * M], tt, pred[2 * M];
ll ans_lf[M], ans_rt[M];

int get(int x) { return (pre[x] == x ? pre[x] : pre[x] = get(pre[x])); }
int get_o(int x) { return (pred[x] == x ? pred[x] : pred[x] = get_o(pred[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[get(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] && get(loc) != get(loc - 1)) {
                pre[get(loc)] = get(pre[loc - 1]);
                siz--;
            }

            if (tp[row + 1][j] && get(loc) != get(loc + m)){
                siz--;
                pre[get(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[get(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] && get(loc) != get(loc - 1)) {
                pre[get(loc)] = get(pre[loc - 1]);
                siz--;
            }

            if (tp[row - 1][j] && get(loc) != get(loc - m)){
                siz--;
                pre[get(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;
        }
    }

    assert(ko_lf < M && ko_rt < M);

    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]);

        tt++;

        int indx = 0;

        for (int j = 0; j < m; j++){
            pred[j] = j;
            pred[j + m] = j + m;

            if (lst[rgt[ri][j]] != tt){
                lst[rgt[ri][j]] = tt;
                ind[rgt[ri][j]] = j;
            }

            pred[j] = ind[rgt[ri][j]];


            if (lst[lft[le][j]] != tt){
                lst[lft[le][j]] = tt;
                ind[lft[le][j]] = j + m;
            }

            pred[j + m] = ind[lft[le][j]];
        }

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

            int fi = get_o(pred[j]);
            int se = get_o(pred[j + m]);

            if (fi == se) continue;

            nw++;

            pred[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;
}

Compilation message

raspad.cpp: In function 'void calc(int, int)':
raspad.cpp:173:13: warning: unused variable 'indx' [-Wunused-variable]
         int indx = 0;
             ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 7 ms 1152 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 18 ms 1280 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 10 ms 1152 KB Output is correct
12 Correct 7 ms 1024 KB Output is correct
13 Correct 12 ms 1152 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 18808 KB Output is correct
2 Correct 363 ms 38648 KB Output is correct
3 Correct 600 ms 38904 KB Output is correct
4 Correct 141 ms 34680 KB Output is correct
5 Correct 94 ms 11820 KB Output is correct
6 Correct 385 ms 38552 KB Output is correct
7 Correct 340 ms 38664 KB Output is correct
8 Correct 301 ms 31096 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 7 ms 1152 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 18 ms 1280 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 10 ms 1152 KB Output is correct
12 Correct 7 ms 1024 KB Output is correct
13 Correct 12 ms 1152 KB Output is correct
14 Correct 167 ms 18808 KB Output is correct
15 Correct 363 ms 38648 KB Output is correct
16 Correct 600 ms 38904 KB Output is correct
17 Correct 141 ms 34680 KB Output is correct
18 Correct 94 ms 11820 KB Output is correct
19 Correct 385 ms 38552 KB Output is correct
20 Correct 340 ms 38664 KB Output is correct
21 Correct 301 ms 31096 KB Output is correct
22 Correct 973 ms 54392 KB Output is correct
23 Runtime error 236 ms 82552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -