QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1045#666401#21696. 【NOIP Round #3】数圈圈cleverpenguincleverpenguinFailed.2024-10-22 18:15:272024-10-23 22:28:20

Details

Extra Test:

Accepted
time: 3ms
memory: 17908kb

input:

2 2
aa
aa

output:

1

result:

ok "1"

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#666401#21696. 【NOIP Round #3】数圈圈cleverpenguin100 ✓770ms227420kbC++143.7kb2024-10-22 18:13:392024-10-23 22:49:17

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,u[2005][2005],p[2005][2005],t2[2005][2005];
int l[2005][2005],r[2005][2005],t1[2005][2005];
int lef[2005][2005],ans;
char ch[2005][2005];
void solve(int a,int b,int c,int d){
	if(a>=c||b>=d)return ;
	int mid;
	if(c-a>d-b){
		mid=a+c>>1;
		solve(a,b,mid,d);
		solve(mid+1,b,c,d);
		for(int j=b;j<=d;j++){
			for(int i=b;i<=d;i++)lef[j][i]=0;
		}
		for(int j=b;j<=d;j++){
			for(int i=b-1;i<=d+1;i++)t1[j][i]=t2[j][i]=0;
		}
		for(int j=b;j<=d;j++){
			for(int i=max(a,u[mid][j]);i<=mid;i++){
				t1[j][min(r[i][j],d)]++;
				t2[j][max(l[i][j],b)]++;
			}
			for(int i=d;i>=b;i--)t1[j][i]+=t1[j][i+1];
			for(int i=b;i<=d;i++)t2[j][i]+=t2[j][i-1];
		}
		for(int j=b;j<=d;j++){
			for(int i=j+1;i<=d;i++){
				if(u[mid][j]>=u[mid][i]){
					lef[j][i]=t1[j][i];
				}else{
					lef[j][i]=t2[i][j];
				}
			}
		}
		for(int j=b;j<=d;j++){
			for(int i=b-1;i<=d+1;i++)t1[j][i]=t2[j][i]=0;
		}
		for(int j=b;j<=d;j++){
			for(int i=mid+1;i<=min(c,p[mid+1][j]);i++){
				t1[j][min(r[i][j],d)]++;
				t2[j][max(l[i][j],b)]++;
			}
			for(int i=d;i>=b;i--)t1[j][i]+=t1[j][i+1];
			for(int i=b;i<=d;i++)t2[j][i]+=t2[j][i-1];
		}
		for(int j=b;j<=d;j++){
			for(int i=j+1;i<=d;i++){
				if(ch[mid][j]!=ch[mid+1][j]||ch[mid][i]!=ch[mid+1][i])continue;
				if(p[mid+1][j]<=p[mid+1][i]){
					ans+=lef[j][i]*t1[j][i];
				}else{
					ans+=lef[j][i]*t2[i][j];
				}
			}
		}
//		cout<<"1 ";
	}else{
		mid=b+d>>1;
		solve(a,b,c,mid);
		solve(a,mid+1,c,d);
		for(int j=a;j<=c;j++){
			for(int i=a;i<=c;i++)lef[j][i]=0;
		}
		for(int j=a;j<=c;j++){
			for(int i=a-1;i<=c+1;i++)t1[j][i]=t2[j][i]=0;
		}
		for(int j=a;j<=c;j++){
			for(int i=max(b,l[j][mid]);i<=mid;i++){
//				cout<<min(p[j][i],c)<<" ";
//				cout<<max(u[j][i],a)<<' '<<j<<" "<<i<<"\n";
				t1[j][min(p[j][i],c)]++;
				t2[j][max(u[j][i],a)]++;
			}
			for(int i=c;i>=a;i--)t1[j][i]+=t1[j][i+1];
			for(int i=a;i<=c;i++)t2[j][i]+=t2[j][i-1];
		}
		for(int j=a;j<=c;j++){
			for(int i=j+1;i<=c;i++){
				if(l[j][mid]>=l[i][mid]){
					lef[j][i]=t1[j][i];
//					cout<<i<<" "<<j<<" "<<lef[j][i]<<" 1\n"; 
				}else{
					lef[j][i]=t2[i][j];
//					cout<<i<<" "<<j<<" "<<lef[j][i]<<" 2\n";
				}
			}
		}
		for(int j=a;j<=c;j++){
			for(int i=a-1;i<=c+1;i++)t1[j][i]=t2[j][i]=0;
		}
		for(int j=a;j<=c;j++){
			for(int i=mid+1;i<=min(d,r[j][mid+1]);i++){
//				cout<<min(p[j][i],c)<<" ";
//				cout<<max(u[j][i],a)<<' '<<j<<" "<<i<<"\n";
				t1[j][min(p[j][i],c)]++;
				t2[j][max(u[j][i],a)]++;
			}
			for(int i=c;i>=a;i--)t1[j][i]+=t1[j][i+1];
			for(int i=a;i<=c;i++)t2[j][i]+=t2[j][i-1];
		}
		for(int j=a;j<=c;j++){
			for(int i=j+1;i<=c;i++){
				if(ch[j][mid+1]!=ch[j][mid]||ch[i][mid]!=ch[i][mid+1])continue;
				if(r[j][mid+1]<=r[i][mid+1]){
					ans+=lef[j][i]*t1[j][i];
//					cout<<i<<" "<<j<<" "<<lef[j][i]<<' '<<t1[j][i]<<" 1\n";
				}else{
					ans+=lef[j][i]*t2[i][j];
//					cout<<i<<" "<<j<<" "<<lef[j][i]<<' '<<t2[i][j]<<" 2\n";
				}
			}
		}
//		cout<<"2 ";
	}
//	cout<<ans<<" "<<mid<<" "<<a<<' '<<c<<' '<<b<<" "<<d<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>ch[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(ch[i][j]==ch[i][j-1])l[i][j]=l[i][j-1];
			else l[i][j]=j;
			if(ch[i][j]==ch[i-1][j])u[i][j]=u[i-1][j];
			else u[i][j]=i;
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=m;j>=1;j--){
			if(ch[i][j]==ch[i][j+1])r[i][j]=r[i][j+1];
			else r[i][j]=j;
			if(ch[i][j]==ch[i+1][j])p[i][j]=p[i+1][j];
			else p[i][j]=i;
		}
	}
	solve(1,1,n,m);
	cout<<ans;
	return 0;
}