This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define mid (l+r)/2
#define ii pair < long long , int >
#define fi first
#define se second
using namespace std;
const int N=1055;
int a[N][N];
ii tree[N*4][N];
int lazy[N*4][N];
int n,m;
long long ans;
void propa(int l , int r , int node , int j)
{
if(lazy[node][j]==-1)
return ;
if(l!=r)
{
lazy[node*2][j]=lazy[node][j];
lazy[node*2+1][j]=lazy[node][j];
}
tree[node][j].fi=lazy[node][j]*(r-l+1);
tree[node][j].se=lazy[node][j];
lazy[node][j]=-1;
}
void update(int l , int r , int node , int x , int y , int val , int j)
{
propa(l,r,node,j);
if(x>r||l>y||x>y)
return ;
if(x<=l&&r<=y)
{
lazy[node][j]=val;
propa(l,r,node,j);
return ;
}
update(l,mid,node*2,x,y,val,j);
update(1+mid,r,1+node*2,x,y,val,j);
tree[node][j].fi=tree[node*2][j].fi+tree[node*2+1][j].fi;
tree[node][j].se=max(tree[node*2][j].se,tree[node*2+1][j].se);
}
ll query(int l , int r , int node , int x , int y , int j)
{
propa(l,r,node,j);
if(x>r||l>y||x>y)
return 0;
if(x<=l&&r<=y)
return tree[node][j].fi;
return query(l,mid,node*2,x,y,j)+query(mid+1,r,node*2+1,x,y,j);
}
int sch(int l , int r , int node , int val , int j)
{
propa(l,r,node,j);
// cout<<l<<' '<<r<<' '<<val<<' '<<tree[node][j].se<<endl;
if(l==r)
return l;
propa(l,mid,node*2,j);
// cout<<l<<' '<<mid<<' '<<val<<' '<<tree[node*2][j].se<<endl;
if(tree[node*2][j].se>=val)
return sch(l,mid,node*2,val,j);
else
return sch(mid+1,r,node*2+1,val,j);
}
void bs(int i , int j , int c)
{
// cout<<i<<' '<<j<<endl;
int l=sch(0,n-1,1,c,j);
update(0,n-1,1,l,i,c,j);
ans+=query(0,n-1,1,0,i,j);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(lazy,-1,sizeof lazy);
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
for(int i=0;i<n;i++)
{
int cnt=1;
for(int j=0;j<m;j++)
{
if(j)
{
if(a[i][j-1]==a[i][j])
cnt++;
else
cnt=1;
}
if(i)
{
if(a[i-1][j]!=a[i][j])
update(0,n-1,1,0,n-1,0,j);
update(0,n-1,1,i,i,cnt,j);
bs(i,j,cnt);
}
else
{
ans+=cnt;
update(0,n-1,1,i,i,cnt,j);
}
}
}
cout<<ans<<endl;
return 0;
}
/*
5 5
1 2 3 4 5
5 2 2 1 4
1 3 5 9 7
2 1 2 1 2
3 4 3 5 6
*/
# | 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... |