oj.uz

Submission #545445

# Submission time Handle Problem Language Result Execution time Memory
545445 2022-04-04T14:17:24 Z baokhue232005 Raspad (COI17_raspad) C++17
100 / 100
 2047 ms 45364 KB 
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option

#include<bits/stdc++.h>
using namespace std;

#define all(flg) flg.begin(), flg.end()
#define int long long
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define eb emplace_back
#define ii pair<int, int>
#define iii pair<int, ii>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 5000055;
const int cum = maxN - 52;
const ll oo = 1e18 + 7;
int n;
int x, y, z, k, m;

bitset<51> a[maxN];
int ans = 0;
int par[maxN];
int cnt;

int find(int i){
    if(i == par[i]) return i;
    else return par[i] = find(par[i]);
}

void renit(int rw){
    for1(i, cum + 1, cum + 50) par[i] = i;
    a[rw][m] = 0;
    cnt = cum;
    for1(i, 0, m - 1) if(a[rw][i]){
        int x = rw * m - i;
        if(!a[rw][i + 1]){
            ++cnt;
            par[x] = cnt;
        }
        else{
            par[x] = x - 1;
        }
    }
}

int vole; int mlim; int compo;
bitset<51> prv; int rprw;
bitset<51> cur; int rcur;
vector<iii> v1, v2;
vector<iii> stf;


void tabu(int cockrow){
    cur = a[cockrow]; rcur = cockrow; --mlim;
    for2(i, m - 1, 0) if(cur[i]) ++compo;
    for2(i, m - 1, 0) if(cur[i] && prv[i]){
        x = find(rcur * m - i);
        y = find(rprw * m - i);
        if(x != y){
            par[x] = y; --compo;
        }
    }
    for2(i, m - 1, 1) if(cur[i] && cur[i - 1]){
        x = find(rcur * m - i);
        y = find(rcur * m - (i - 1));
        if(x != y){
            if(x > cum && y > cum) stf.pb({mlim, {x - cum, y - cum}});
            if(x > y) swap(x, y);
            par[x] = y;
            --compo;
        }
    }
    ans += compo * vole;
    rprw = rcur; prv = cur;
}

void dnc(int le, int ri){
    if(le > ri) return;
    int mid = (le + ri) / 2;
    dnc(le, mid - 1);
    dnc(mid + 1, ri);
    for1(i, (le - 1) * m + 1, ri * m) par[i] = i;
    renit(mid);
    ans += (cnt - cum) * (ri - mid + 1) * (mid - le + 1);

    renit(mid);
    stf.clear();
    compo = 0;
    mlim = ri - mid + 1;
    vole = mid - le + 1;
    prv = a[mid]; rprw = mid;
    for1(i, mid + 1, ri) tabu(i);
    v1 = stf;

    renit(mid);
    stf.clear();
    compo = 0;
    mlim = mid - le + 1;
    vole = ri - mid + 1;
    prv = a[mid]; rprw = mid;
    for2(i, mid - 1, le) tabu(i);
    v2 = stf;


    int sz1 = v1.size(); int sz2 = v2.size();
    v1.pb({0, ii(0, 0)});

    for1(i, 0, sz1 - 1){
        for1(i, 1, 50) par[i] = i;
        for1(j, 0, i){
            par[find(v1[j].se.fi)] =
                find(v1[j].se.se);
        }
        int dsi = v1[i].fi - v1[i + 1].fi;
        for(auto cc : v2){
            x = find(cc.se.fi);
            y = find(cc.se.se);
            z = cc.fi;
            if(x == y){
                ans += dsi * z;
            }
            else par[x] = y;
        }
    }
    // cout << le << " " << ri << " " << ans << endl;
}

signed main(){
    // freopen(".inp", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for1(i, 1, n){
        cin >> a[i];
    }
    dnc(1, n);
    cout << ans << endl;
}

Compilation message

raspad.cpp: In function 'void dnc(long long int, long long int)':
raspad.cpp:116:30: warning: unused variable 'sz2' [-Wunused-variable]
  116 |     int sz1 = v1.size(); int sz2 = v2.size();
      |                              ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 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 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 6 ms 708 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 12 ms 732 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 9 ms 724 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 7 ms 732 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 6928 KB Output is correct
2 Correct 505 ms 14412 KB Output is correct
3 Correct 654 ms 14416 KB Output is correct
4 Correct 174 ms 13004 KB Output is correct
5 Correct 133 ms 4548 KB Output is correct
6 Correct 484 ms 14304 KB Output is correct
7 Correct 261 ms 14308 KB Output is correct
8 Correct 351 ms 11568 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 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 6 ms 708 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 12 ms 732 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 9 ms 724 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 7 ms 732 KB Output is correct
14 Correct 171 ms 6928 KB Output is correct
15 Correct 505 ms 14412 KB Output is correct
16 Correct 654 ms 14416 KB Output is correct
17 Correct 174 ms 13004 KB Output is correct
18 Correct 133 ms 4548 KB Output is correct
19 Correct 484 ms 14304 KB Output is correct
20 Correct 261 ms 14308 KB Output is correct
21 Correct 351 ms 11568 KB Output is correct
22 Correct 1113 ms 29252 KB Output is correct
23 Correct 2047 ms 45240 KB Output is correct
24 Correct 1805 ms 45132 KB Output is correct
25 Correct 1215 ms 45240 KB Output is correct
26 Correct 635 ms 45236 KB Output is correct
27 Correct 1256 ms 36404 KB Output is correct
28 Correct 1671 ms 36428 KB Output is correct
29 Correct 1800 ms 45264 KB Output is correct
30 Correct 611 ms 45292 KB Output is correct
31 Correct 598 ms 45120 KB Output is correct
32 Correct 577 ms 45364 KB Output is correct
33 Correct 1008 ms 40000 KB Output is correct
34 Correct 1393 ms 40804 KB Output is correct