oj.uz

Submission #545481

# Submission time Handle Problem Language Result Execution time Memory
545481 2022-04-04T15:01:09 Z tranxuanbach Raspad (COI17_raspad) C++17
100 / 100
 3814 ms 12788 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 14 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 23 ms 340 KB Output is correct
10 Correct 7 ms 340 KB Output is correct
11 Correct 20 ms 448 KB Output is correct
12 Correct 9 ms 424 KB Output is correct
13 Correct 15 ms 396 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 3568 KB Output is correct
2 Correct 842 ms 6796 KB Output is correct
3 Correct 1175 ms 7700 KB Output is correct
4 Correct 365 ms 7620 KB Output is correct
5 Correct 225 ms 2508 KB Output is correct
6 Correct 924 ms 7500 KB Output is correct
7 Correct 695 ms 6964 KB Output is correct
8 Correct 671 ms 6216 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 14 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 23 ms 340 KB Output is correct
10 Correct 7 ms 340 KB Output is correct
11 Correct 20 ms 448 KB Output is correct
12 Correct 9 ms 424 KB Output is correct
13 Correct 15 ms 396 KB Output is correct
14 Correct 401 ms 3568 KB Output is correct
15 Correct 842 ms 6796 KB Output is correct
16 Correct 1175 ms 7700 KB Output is correct
17 Correct 365 ms 7620 KB Output is correct
18 Correct 225 ms 2508 KB Output is correct
19 Correct 924 ms 7500 KB Output is correct
20 Correct 695 ms 6964 KB Output is correct
21 Correct 671 ms 6216 KB Output is correct
22 Correct 2012 ms 9156 KB Output is correct
23 Correct 3814 ms 12744 KB Output is correct
24 Correct 3590 ms 12228 KB Output is correct
25 Correct 2536 ms 12788 KB Output is correct
26 Correct 1465 ms 10392 KB Output is correct
27 Correct 2388 ms 10844 KB Output is correct
28 Correct 2964 ms 11276 KB Output is correct
29 Correct 3300 ms 12700 KB Output is correct
30 Correct 1491 ms 10388 KB Output is correct
31 Correct 1452 ms 10432 KB Output is correct
32 Correct 1869 ms 10656 KB Output is correct
33 Correct 2284 ms 11460 KB Output is correct
34 Correct 2773 ms 11272 KB Output is correct