/*
#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;
for1(i, 1, 50) par[i] = i;
int sz1 = v1.size(); int sz2 = v2.size();
v1.pb({0, ii(0, 0)});
for1(i, 0, sz1 - 1){
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();
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
6164 KB |
Output is correct |
| 2 |
Incorrect |
468 ms |
12760 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
