#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
using namespace std;
struct PlatUnion
{
PlatUnion(long long after_, long long i1_, long long j1_, long long i2_, long long j2_)
: after(after_)
, i1(i1_)
, j1(j1_)
, i2(i2_)
, j2(j2_)
{}
long long after, i1, j1, i2, j2;
};
bool operator<(const PlatUnion& lhs, const PlatUnion& rhs) { return lhs.after < rhs.after; }
long long n, m;
vector< vector<char> > a;
vector<PlatUnion> upds_;
struct Dsu
{
public:
Dsu()
: count(0)
, hard(false)
{}
void SetHard(Dsu& rhs)
{
for (auto it = par.begin(); it != par.end(); ++it)
plats.insert(it->first);
swap(*this, rhs);
count = 0;
}
void MakeSet(long long x, long long y)
{
// cerr << "Make (" << x << ", " << y << ")\n";
++count;
par[make_pair(x, y)] = make_pair(x, y);
}
pair<long long, long long> GetSet(long long x, long long y)
{
pair<long long, long long> p = make_pair(x, y);
if (par[p] == p)
return p;
return par[p] = GetSet(par[p].first, par[p].second);
}
void Union(long long x1, long long y1, long long x2, long long y2)
{
pair<long long, long long> p1 = GetSet(x1, y1);
pair<long long, long long> p2 = GetSet(x2, y2);
if (p1 == p2)
return;
// cerr << "Union (" << x1 << ", " << y1 << ") and (" << x2 << ", " << y2 << ")\n";
if (sz[p1] > sz[p2])
swap(p1, p2);
sz[p2] += sz[p1];
par[p1] = p2;
--count;
}
long long Count() { return count; }
bool hard;
set< pair<long long, long long> > plats;
long long count;
map<pair<long long, long long>, pair<long long, long long>> par;
map<pair<long long, long long>, long long> sz;
};
void TryPlatUnion(vector< pair<long long, long long> >& plats, Dsu dsu, vector<PlatUnion>& platUnions,
long long i1, long long j1, long long i2, long long j2, long long after)
{
long long plat1 = -1, plat2 = -1;
for (long long i = 0; i < plats.size(); ++i)
if (dsu.GetSet(plats[i].first, plats[i].second) == dsu.GetSet(i1, j1))
plat1 = i;
else if (dsu.GetSet(plats[i].first, plats[i].second) == dsu.GetSet(i2, j2))
plat2 = i;
if (plat1 == -1 || plat2 == -1)
return;
platUnions.push_back(PlatUnion(after, plats[plat1].first, plats[plat1].second,
plats[plat2].first, plats[plat2].second));
}
long long PrefAns(long long l, long long r, long long platform = -1, Dsu dsu_ = Dsu())
{
long long res = 0;
Dsu dsu;
vector< pair<long long, long long> > plats;
bool hard = false;
if (platform != -1)
for (long long j = 0; j < m; ++j)
{
if (a[platform][j] == 1)
dsu.MakeSet(platform, j);
if (j && a[platform][j - 1] == 1)
dsu.Union(platform, j, platform, j - 1);
else
plats.push_back(make_pair(platform, j));
}
else if (dsu_.Count())
{
hard = true;
dsu.SetHard(dsu_);
}
upds_.clear();
for (long long i = l; i <= r; ++i)
{
for (long long j = 0; j < m; ++j)
if (a[i][j] == '1')
{
dsu.MakeSet(i, j);
const long long di[] = {-1, 0};
const long long dj[] = {0, -1};
for (long long d = 0; d < 2; ++d)
{
long long i1 = i + di[d], j1 = j + dj[d];
if (i1 >= l && i1 <= i && j1 >= 0 && j1 < m && a[i1][j1] == '1')
{
if (!hard)
TryPlatUnion(plats, dsu, upds_, i, j, i1, j1, i - l);
dsu.Union(i, j, i1, j1);
}
}
}
// cerr << "**************dsu size: " << dsu.Size() << endl;
res += dsu.Count();
}
/*
char I;
cin >> I;
*/
return res;
}
long long SuffAns(long long l, long long r, long long platform = -1, Dsu dsu_ = Dsu())
{
long long res = 0;
Dsu dsu;
vector< pair<long long, long long> > plats;
bool hard = false;
if (platform != -1)
for (long long j = 0; j < m; ++j)
{
if (a[platform][j] == 1)
dsu.MakeSet(platform, j);
if (j && a[platform][j - 1] == 1)
dsu.Union(platform, j, platform, j - 1);
else
plats.push_back(make_pair(platform, j));
}
else if (dsu_.Count())
{
hard = true;
dsu.SetHard(dsu_);
}
if (l == 0 && r == 0 && hard)
cerr << "";
upds_.clear();
for (long long i = r; i >= l; --i)
{
for (long long j = 0; j < m; ++j)
if (a[i][j] == '1')
{
dsu.MakeSet(i, j);
const long long di[] = {1, 0};
const long long dj[] = {0, -1};
for (long long d = 0; d < 2; ++d)
{
long long i1 = i + di[d], j1 = j + dj[d];
if (i1 >= i && (i1 <= r || (i1 == r + 1 && (hard || platform != -1))) && j1 >= 0 && j1 < m && a[i1][j1] == '1')
{
if (!hard)
TryPlatUnion(plats, dsu, upds_, i, j, i1, j1, r - i);
dsu.Union(i, j, i1, j1);
}
}
}
// cerr << "**************dsu size: " << dsu.Size() << endl;
res += dsu.Count();
}
/*
char I;
cin >> I;
*/
return res;
}
long long Solve(long long vl, long long vr)
{
if (vl == vr)
return PrefAns(vl, vr);
long long vm = vl + (vr - vl) / 2;
long long ans = Solve(vl, vm) + Solve(vm + 1, vr);
SuffAns(vl, vm, vm + 1);
vector<PlatUnion> upds;
upds.swap(upds_);
upds.push_back(PlatUnion(vm - vl + 1, -1, -1, -1, -1));
Dsu dsu;
for (long long j = 0; j < m; ++j)
if (a[vm][j] == '1')
{
dsu.MakeSet(vm, j);
if (j && a[vm][j - 1] == '1')
dsu.Union(vm, j, vm, j - 1);
}
for (auto upd = upds.begin(); upd != upds.end(); ++upd)
{
if (next(upd) != upds.end())
dsu.Union(upd->i1, upd->j1, upd->i2, upd->j2);
ans += (upd->after - (upd == upds.begin() ? 0 : std::prev(upd)->after)) * PrefAns(vm + 1, vr, -1, dsu);
}
PrefAns(vm + 1, vr, vm);
upds.swap(upds_);
upds.push_back(PlatUnion(vr - vm, -1, -1, -1, -1));
dsu = Dsu();
for (long long j = 0; j < m; ++j)
if (a[vm + 1][j] == '1')
{
dsu.MakeSet(vm + 1, j);
if (j && a[vm + 1][j - 1] == '1')
dsu.Union(vm + 1, j, vm + 1, j - 1);
}
for (auto upd = upds.begin(); upd != upds.end(); ++upd)
{
if (next(upd) != upds.end())
dsu.Union(upd->i1, upd->j1, upd->i2, upd->j2);
ans += (upd->after - (upd == upds.begin() ? 0 : std::prev(upd)->after)) * SuffAns(vl, vm, -1, dsu);
}
// ans -= (PrefAns(vm, vm + 1) + PrefAns(vm + 1, vm + 1));
// ans += (vm - vl + 1) * PrefAns(vm + 1, vr);
// ans += (vr - vm) * SuffAns(vl, vm);
// cout << "Solve(" << vl << ", " << vr << ") returns " << ans << endl;
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
a.resize(n, vector<char>(m));
for (long long i = 0; i < n; ++i)
for (long long j = 0; j < m; ++j)
cin >> a[i][j];
/*
long long ans = 0;
for (long long i = 0; i < n; ++i)
ans += SuffAns(0, i);
cout << ans << endl;
*/
cout << Solve(0, n - 1) << endl;
char I;
cin >> I;
}
Compilation message
raspad.cpp: In constructor 'Dsu::Dsu()':
raspad.cpp:69:12: warning: 'Dsu::count' will be initialized after [-Wreorder]
long long count;
^~~~~
raspad.cpp:67:7: warning: 'bool Dsu::hard' [-Wreorder]
bool hard;
^~~~
raspad.cpp:28:2: warning: when initialized here [-Wreorder]
Dsu()
^~~
raspad.cpp: In function 'void TryPlatUnion(std::vector<std::pair<long long int, long long int> >&, Dsu, std::vector<PlatUnion>&, long long int, long long int, long long int, long long int, long long int)':
raspad.cpp:78:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (long long i = 0; i < plats.size(); ++i)
~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
1295 ms |
916 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
1295 ms |
916 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
6073 ms |
4024 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
1295 ms |
916 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
