Submission #545481

#	Time	Username	Problem	Language	Result	Execution time	Memory
545481		tranxuanbach	Raspad (COI17_raspad)	C++17	100 / 100	3814 ms	12788 KiB

raspad

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
 
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;
 
const int N = 1e5 + 5, M = 50 + 2;
 
struct disjoint_set_union{
    int par[2 * M], val[2 * M];
 
    void reset(int len){
        fill(par + 1, par + len + 1, -1);
        fill(val + 1, val + len + 1, 0);
    }
 
    int root(int x){
        return par[x] < 0 ? x : (par[x] = root(par[x]));
    }
 
    pii ansmerge;
 
    bool merge(int x, int y){
        if ((x = root(x)) == (y = root(y))){
            return 0;
        }
        if (par[x] > par[y]){
            swap(x, y);
        }
        par[x] += par[y];
        par[y] = x;
        ansmerge = make_pair(val[x], val[y]);
        if (val[x] == 0){
            val[x] = val[y];
        }
        else if (val[y] == 0){
 
        }
        else{
            val[x] = min(val[x], val[y]);
        }
        return 1;
    }
} dsu[3];
 
int n, m;
char a[N][M];
 
ll ans;

int root[N * M];
int pos[2 * M];
 
void find_interval(const vector <pair <int, pii>> &a, vector <pair <int, pii>> &b){
    b.clear();
    int l = 0;
    ForE(r, 1, isz(a)){
        if (r == isz(a) or a[r].fi != a[r - 1].fi){
            b.emplace_back(a[l].fi, make_pair(l, r - 1));
            l = r;
        }
    }
}
 
void divide_and_conquer(int l, int r){
    if (l == r){
        ForE(j, 1, m){
            if (a[l][j - 1] == '0' and a[l][j] == '1'){
                ans++;
            }
        }
        return;
    }
 
    int mid = (l + r) >> 1;
    divide_and_conquer(l, mid);
    divide_and_conquer(mid + 1, r);
 
    vector <pair <int, pii>> mergel = {{mid, {0, 0}}}, merger = {{mid + 1, {0, 0}}};
    {
        int ctridx = 0;
        dsu[mid & 1].reset(2 * m);
        ForE(j, 1, m){
            if (a[mid][j] != '1'){
                continue;
            }
            dsu[mid & 1].val[j] = ++ctridx;
            if (a[mid][j - 1] == '1'){
                dsu[mid & 1].merge(j - 1, j);
            }
        }
 
        int idx_colmid = ctridx;
        int cnt = 0;
 
        FordE(i, mid - 1, l){
            int ii = i & 1;
            dsu[ii].reset(2 * m);
            ForE(j, 1, m){
                root[dsu[ii ^ 1].val[dsu[ii ^ 1].root(j)]] = j + m;
            }
            ForE(j, 1, m){
                dsu[ii].val[j + m] = dsu[ii ^ 1].val[dsu[ii ^ 1].root(j)];
                dsu[ii].merge(j + m, root[dsu[ii ^ 1].val[dsu[ii ^ 1].root(j)]]);
            }
            ForE(j, 1, m){
                if (a[i][j] != '1'){
                    continue;
                }
                if (a[i + 1][j] == '1'){
                    dsu[ii].merge(j, j + m);
                }
                else{
                    dsu[ii].val[j] = ++ctridx;
                    cnt++;
                }
                if (a[i][j - 1] == '1'){
                    if (dsu[ii].merge(j - 1, j)){
                        if (dsu[ii].ansmerge.fi > idx_colmid or dsu[ii].ansmerge.se > idx_colmid){
                            cnt--;
                        }
                        else{
                            mergel.emplace_back(i, dsu[ii].ansmerge);
                        }
                    }
                }
            }
            ans += (ll)cnt * (r - mid);
        }
    }
    // cout << "STEP 1 " << l << ' ' << r << ' ' << ans << endl;
    {
        int ctridx = 0;
        dsu[(mid + 1) & 1].reset(2 * m);
        ForE(j, 1, m){
            if (a[mid + 1][j] != '1'){
                continue;
            }
            dsu[(mid + 1) & 1].val[j] = ++ctridx;
            if (a[mid + 1][j - 1] == '1'){
                dsu[(mid + 1) & 1].merge(j - 1, j);
            }
        }
 
        int idx_colmid = ctridx;
        int cnt = 0;
 
        ForE(i, mid + 2, r){
            int ii = i & 1;
            dsu[ii].reset(2 * m);
            ForE(j, 1, m){
                root[dsu[ii ^ 1].val[dsu[ii ^ 1].root(j)]] = j + m;
            }
            ForE(j, 1, m){
                dsu[ii].val[j + m] = dsu[ii ^ 1].val[dsu[ii ^ 1].root(j)];
                dsu[ii].merge(j + m, root[dsu[ii ^ 1].val[dsu[ii ^ 1].root(j)]]);
            }
            ForE(j, 1, m){
                if (a[i][j] != '1'){
                    continue;
                }
                if (a[i - 1][j] == '1'){
                    dsu[ii].merge(j, j + m);
                }
                else{
                    dsu[ii].val[j] = ++ctridx;
                    cnt++;
                }
                if (a[i][j - 1] == '1'){
                    if (dsu[ii].merge(j - 1, j)){
                        if (dsu[ii].ansmerge.fi > idx_colmid or dsu[ii].ansmerge.se > idx_colmid){
                            cnt--;
                        }
                        else{
                            merger.emplace_back(i, dsu[ii].ansmerge);
                        }
                    }
                }
            }
            ans += (ll)cnt * (mid - l + 1);
        }
    }
    // cout << "STEP 2 " << l << ' ' << r << ' ' << ans << endl;
 
    // cout << "MERGEL" << endl;
    // Fora(elem, mergel){
    //     cout << elem.fi << ' ' << elem.se.fi << ' ' << elem.se.se << endl;
    // }
    // cout << "MERGER" << endl;
    // Fora(elem, merger){
    //     cout << elem.fi << ' ' << elem.se.fi << ' ' << elem.se.se << endl;
    // }
    vector <pair <int, pii>> itvmergel, itvmerger;
    find_interval(mergel, itvmergel);
    find_interval(merger, itvmerger);
 
    For(il, 0, isz(itvmergel)){
        int lenl = itvmergel[il].fi - (il == isz(itvmergel) - 1 ? l - 1 : itvmergel[il + 1].fi);
        dsu[2].reset(2 * m);
        int cnt = 0, itr = 0;
        ForE(j, 1, m){
            if (a[mid][j - 1] == '0' and a[mid][j] == '1'){
                itr++;
                cnt++;
                pos[j] = itr;
                dsu[2].val[itr] = itr;
            }
            else if (a[mid][j] == '1'){
                itr++;
                pos[j] = pos[j - 1];
            }
        }
 
        if (il != 0){
            ForE(til, 1, itvmergel[il].se.se){
                if (dsu[2].merge(mergel[til].se.fi, mergel[til].se.se)){
                    cnt--;
                }
            }
        }
 
        itr = m;
        ForE(j, 1, m){
            if (a[mid + 1][j - 1] == '0' and a[mid + 1][j] == '1'){
                itr++;
                cnt++;
                pos[j + m] = itr;
                dsu[2].val[itr] = itr;
            }
            else if (a[mid + 1][j] == '1'){
                itr++;
                pos[j + m] = pos[j + m - 1];
            }
            if (a[mid][j] == '1' and a[mid + 1][j] == '1'){
                if (dsu[2].merge(pos[j], pos[j + m])){
                    cnt--;
                }
            }
        }
        For(ir, 0, isz(itvmerger)){
            int lenr = (ir == isz(itvmerger) - 1 ? r + 1 : itvmerger[ir + 1].fi) - itvmerger[ir].fi;
            if (ir != 0){
                ForE(tir, itvmerger[ir].se.fi, itvmerger[ir].se.se){
                    if (dsu[2].merge(merger[tir].se.fi + m, merger[tir].se.se + m)){
                        cnt--;
                    }
                }
            }
            // cout << "ADD ANS " << il << ' ' << ir << ' ' << lenl << ' ' << lenr << ' ' << cnt << endl;
            ans += (ll)lenl * lenr * cnt;
        }
    }
    // cout << "STEP 3 " << l << ' ' << r << ' ' << ans << endl;
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n >> m;
    ForE(i, 1, n){
        ForE(j, 1, m){
            cin >> a[i][j];
        }
    }
 
    ForE(i, 1, n){
        a[i][0] = a[i][m + 1] = '0';
    }
 
    divide_and_conquer(1, n);
    cout << ans << endl;
}
 
/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
 
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
 
--------------------------------------------------|
==================================================+
*/

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 35 / 35
• Subtask 4: 39 / 39