oj.uz

Submission #250842

# Submission time Handle Problem Language Result Execution time Memory
250842 2020-07-19T09:37:31 Z VEGAnn Raspad (COI17_raspad) C++14
100 / 100
 2516 ms 69624 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];
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 upd(int (&mas)[M]){
    tt++;

    int indx = 0;

    for (int j = 0; j < m; j++){
        if (lst[mas[j]] != tt){
            lst[mas[j]] = tt;
            ind[mas[j]] = indx++;
        }

        mas[j] = ind[mas[j]];
    }
}

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

    upd(lft[0]);

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

        upd(lft[ko_lf]);

        for (int j = 0; j < m; j++) {
            if (tp[md][j] && lft[ko_lf][j] != lft[ko_lf - 1][j]) {
                was = 1;
                break;
            }
        }

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

    upd(rgt[0]);

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

        upd(rgt[ko_rt]);

        for (int j = 0; j < m; j++) {
            if (tp[md + 1][j] && rgt[ko_rt][j] != rgt[ko_rt - 1][j]) {
                was = 1;
                break;
            }
        }

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

        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] + m] != tt){
                lst[lft[le][j] + m] = tt;
                ind[lft[le][j] + m] = j + m;
            }

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

        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:202: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 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 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 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 9 ms 896 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 17 ms 1024 KB Output is correct
10 Correct 6 ms 896 KB Output is correct
11 Correct 12 ms 1024 KB Output is correct
12 Correct 8 ms 896 KB Output is correct
13 Correct 11 ms 896 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 11256 KB Output is correct
2 Correct 467 ms 23288 KB Output is correct
3 Correct 675 ms 23288 KB Output is correct
4 Correct 209 ms 20856 KB Output is correct
5 Correct 121 ms 7288 KB Output is correct
6 Correct 476 ms 23288 KB Output is correct
7 Correct 394 ms 23288 KB Output is correct
8 Correct 356 ms 18808 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 9 ms 896 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 17 ms 1024 KB Output is correct
10 Correct 6 ms 896 KB Output is correct
11 Correct 12 ms 1024 KB Output is correct
12 Correct 8 ms 896 KB Output is correct
13 Correct 11 ms 896 KB Output is correct
14 Correct 196 ms 11256 KB Output is correct
15 Correct 467 ms 23288 KB Output is correct
16 Correct 675 ms 23288 KB Output is correct
17 Correct 209 ms 20856 KB Output is correct
18 Correct 121 ms 7288 KB Output is correct
19 Correct 476 ms 23288 KB Output is correct
20 Correct 394 ms 23288 KB Output is correct
21 Correct 356 ms 18808 KB Output is correct
22 Correct 1150 ms 42024 KB Output is correct
23 Correct 2484 ms 64356 KB Output is correct
24 Correct 2516 ms 69296 KB Output is correct
25 Correct 1368 ms 69376 KB Output is correct
26 Correct 1067 ms 69368 KB Output is correct
27 Correct 1281 ms 56512 KB Output is correct
28 Correct 1865 ms 56824 KB Output is correct
29 Correct 1883 ms 69496 KB Output is correct
30 Correct 1078 ms 69352 KB Output is correct
31 Correct 1052 ms 69624 KB Output is correct
32 Correct 1456 ms 69432 KB Output is correct
33 Correct 1342 ms 61304 KB Output is correct
34 Correct 1744 ms 62328 KB Output is correct