QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#688911#1085. Brave Seekers of Unicorns0xyzWA 1ms5600kbC++143.6kb2024-10-30 14:15:442024-10-30 14:15:45

Judging History

你现在查看的是最新测评结果

  • [2024-10-30 14:15:45]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5600kb
  • [2024-10-30 14:15:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int _=2005;
int L[_][_],R[_][_],U[_][_],D[_][_],cl[_][_],cr[_][_],cu[_][_],cd[_][_],n,m;
char a[_][_];
ll s;
void sol(int xl,int xr,int yl,int yr){
	if(xl>=xr||yl>=yr)return;
	if(xr-xl+1>=yr-yl+1){
		int xm=xl+xr>>1;
		for(int l=yl;l<=yr;l++)
			for(int r=l+1;r<=yr;r++)cu[l][r]=cd[l][r]=0;
		for(int l=yl;l<=yr;l++){
			vector<int>e;
			for(int i=xm+1;i<=min(D[xm+1][l],xr);i++)e.push_back(R[i][l]);
			sort(e.begin(),e.end(),greater<int>());
			for(int r=l+1;r<=yr;r++)
				if(min(D[xm+1][r],xr)>=min(D[xm+1][l],xr)){
					while(e.size()&&e.back()<r)e.pop_back();
					cd[l][r]+=e.size();
				}
		}
		for(int r=yl;r<=yr;r++){
			vector<int>e;
			for(int i=xm+1;i<=min(D[xm+1][r],xr);i++)e.push_back(L[i][r]);
			sort(e.begin(),e.end());
			for(int l=r-1;l>=yl;l--)
				if(min(D[xm+1][r],xr)<min(D[xm+1][l],xr)){
					while(e.size()&&e.back()>l)e.pop_back();
					cd[l][r]+=e.size();
				}
		}
		for(int l=yl;l<=yr;l++){
			vector<int>e;
			for(int i=xm;i>=max(U[xm][l],xl);i--)e.push_back(R[i][l]);
			sort(e.begin(),e.end(),greater<int>());
			for(int r=l+1;r<=yr;r++)
				if(max(U[xm][r],xl)>=max(U[xm][l],xl)){
					while(e.size()&&e.back()<r)e.pop_back();
					cu[l][r]+=e.size();
				}
		}
		for(int r=yl;r<=yr;r++){
			vector<int>e;
			for(int i=xm;i>=max(U[xm][r],xl);i--)e.push_back(L[i][r]);
			sort(e.begin(),e.end());
			for(int l=r-1;l>=yl;l--)
				if(max(U[xm][r],xl)<max(U[xm][l],xl)){
					while(e.size()&&e.back()>l)e.pop_back();
					cu[l][r]+=e.size();
				}
		}
		for(int l=yl;l<=yr;l++)
			for(int r=l+1;r<=yr;r++)
				if(a[xm][l]==a[xm+1][l]&&a[xm][r]==a[xm+1][r])s+=cu[l][r]*cd[l][r];
		sol(xl,xm,yl,yr);sol(xm+1,xr,yl,yr);
	}else{
		int ym=yl+yr>>1;
		for(int u=xl;u<=xr;u++)
			for(int d=u+1;d<=xr;d++)cl[u][d]=cr[u][d]=0;
		for(int u=xl;u<=xr;u++){
			vector<int>e;
			for(int i=ym+1;i<=min(R[u][ym+1],yr);i++)e.push_back(D[u][i]);
			sort(e.begin(),e.end(),greater<int>());
			for(int d=u+1;d<=xr;d++)
				if(min(R[d][ym+1],yr)>=min(R[u][ym+1],yr)){
					while(e.size()&&e.back()<d)e.pop_back();
					cr[u][d]+=e.size();
				}
		}
		for(int d=xl;d<=xr;d++){
			vector<int>e;
			for(int i=ym+1;i<=min(R[d][ym+1],yr);i++)e.push_back(U[d][i]);
			sort(e.begin(),e.end());
			for(int u=d-1;u>=xl;u--)
				if(min(R[d][ym+1],yr)<min(R[u][ym+1],yr)){
					while(e.size()&&e.back()>u)e.pop_back();
					cr[u][d]+=e.size();
				}
		}
		for(int u=xl;u<=xr;u++){
			vector<int>e;
			for(int i=ym;i>=max(L[u][ym],yl);i--)e.push_back(D[u][i]);
			sort(e.begin(),e.end(),greater<int>());
			for(int d=u+1;d<=xr;d++)
				if(max(L[d][ym],yl)<=max(L[u][ym],yl)){
					while(e.size()&&e.back()<d)e.pop_back();
					cl[u][d]+=e.size();
				}
		}
		for(int d=xl;d<=xr;d++){
			vector<int>e;
			for(int i=ym;i>=max(L[d][ym],yl);i--)e.push_back(U[d][i]);
			sort(e.begin(),e.end());
			for(int u=d-1;u>=xl;u--)
				if(max(L[d][ym],yl)>max(L[u][ym],yl)){
					while(e.size()&&e.back()>u)e.pop_back();
					cl[u][d]+=e.size();
				}
		}
		for(int u=xl;u<=xr;u++)
			for(int d=u+1;d<=xr;d++)
				if(a[u][ym]==a[u][ym+1]&&a[d][ym]==a[d][ym+1])s+=cl[u][d]*cr[u][d];
		sol(xl,xr,yl,ym);sol(xl,xr,ym+1,yr);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>(a[i]+1);
	for(int i=n;i;i--)
		for(int j=m;j;j--){
			R[i][j]=a[i][j+1]==a[i][j]?R[i][j+1]:j;
			D[i][j]=a[i+1][j]==a[i][j]?D[i+1][j]:i;
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			L[i][j]=a[i][j-1]==a[i][j]?L[i][j-1]:j;
			U[i][j]=a[i-1][j]==a[i][j]?U[i-1][j]:i;
		}
	sol(1,n,1,m);
	cout<<s<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5600kb

input:

1

output:

0

result:

wrong answer 1st numbers differ - expected: '1', found: '0'