#include <bits/stdc++.h>
using namespace std;
const int nx=1e3+5;
#define ll long long
struct info
{
ll l, r, h;
info(ll l, ll r, ll h): l(l), r(r), h(h){}
};
ll n, m, a[nx][nx], r[nx][nx], lst, res, cur;
stack<info> s;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=n ;i++) for (int j=1; j<=m; j++) cin>>a[i][j];
for (int i=1; i<=n; i++)
{
for (int j=m; j>=1; j--)
{
if (a[i][j]==a[i][j+1]) r[i][j]=r[i][j+1]+1;
else r[i][j]=1;
}
}
for (int j=1; j<=m; j++)
{
for (int i=1; i<=n; i++)
{
if (a[i][j]!=a[i-1][j])
{
cur=0;
lst=i-1;
while (!s.empty()) s.pop();
}
while (!s.empty()&&s.top().h>=r[i][j]) cur-=(s.top().r-s.top().l+1)*s.top().h, s.pop();
if (s.empty()) s.push(info(lst+1, i, r[i][j])), cur+=(i-lst)*r[i][j];
else s.push(info(s.top().r+1, i, r[i][j])), cur+=(i-s.top().r)*r[i][j];
res+=cur;
}
}
cout<<res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |