#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100100;
const int M = 110;
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 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]);
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]);
if (lft[ko_lf][j] != lft[ko_lf - 1][j])
was = 1;
}
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]);
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]);
if (rgt[ko_rt][j] != rgt[ko_rt - 1][j])
was = 1;
}
if (was){
crt[ko_rt] = 1;
ans_rt[ko_rt] = siz;
ko_rt++;
} else {
crt[ko_rt - 1]++;
ans_rt[ko_rt - 1] += siz;
}
}
assert(ko_rt < m + m);
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]] != tt){
lst[lft[le][j]] = tt;
ind[lft[le][j]] = j + m;
}
pred[j + m] = ind[lft[le][j]];
}
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:173:13: warning: unused variable 'indx' [-Wunused-variable]
int indx = 0;
^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
9 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
20 ms |
1152 KB |
Output is correct |
| 10 |
Correct |
4 ms |
896 KB |
Output is correct |
| 11 |
Correct |
10 ms |
1024 KB |
Output is correct |
| 12 |
Correct |
7 ms |
896 KB |
Output is correct |
| 13 |
Correct |
11 ms |
1024 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
207 ms |
13980 KB |
Output is correct |
| 2 |
Correct |
367 ms |
28676 KB |
Output is correct |
| 3 |
Runtime error |
146 ms |
36344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
9 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
20 ms |
1152 KB |
Output is correct |
| 10 |
Correct |
4 ms |
896 KB |
Output is correct |
| 11 |
Correct |
10 ms |
1024 KB |
Output is correct |
| 12 |
Correct |
7 ms |
896 KB |
Output is correct |
| 13 |
Correct |
11 ms |
1024 KB |
Output is correct |
| 14 |
Correct |
207 ms |
13980 KB |
Output is correct |
| 15 |
Correct |
367 ms |
28676 KB |
Output is correct |
| 16 |
Runtime error |
146 ms |
36344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Halted |
0 ms |
0 KB |
- |
