QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1048#666893#21696. 【NOIP Round #3】数圈圈wth2026xiangqizhenFailed.2024-10-22 20:29:202024-10-23 22:51:04

Details

the score gained by the hacked submission is not 100.
IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#666893#21696. 【NOIP Round #3】数圈圈xiangqizhen97 1659ms909872kbC++145.2kb2024-10-22 20:20:102024-10-23 22:49:55

answer

#include<bits/stdc++.h>
#define int long long
#define f(i,j,n) for(long long i=j;i<=n;i++)
#define updmax(a,b) a=max(a,b)
#define updmin(a,b) a=min(a,b)
#define pb push_back
#define XQZ
using namespace std;
int n,m;
const int S=2010*2;
const int N=2010;
char mp[2010][2010];
struct abc{
	int u,d,l,r;
	int tgv=0,tg_re=0,sum=0;
}Tree[N*N*4];
#define zs(k) k<<2
#define ys(k) k<<2|1
#define zx(k) k<<2|2
#define yx(k) k<<2|3
#define midy ((Tree[k].u+Tree[k].d)>>1)
#define midx ((Tree[k].l+Tree[k].r)>>1)
#define uns(k) ((k)>=(N*N*4-1)||Tree[k].u>Tree[k].d||Tree[k].l>Tree[k].r)
#define ist(k,up,down,lft,rght) (Tree[k].d>=up&&Tree[k].u<=down&&Tree[k].l<=rght&&Tree[k].r>=lft)
#define ctn(k,up,down,lft,rght) (Tree[k].d<=down&&Tree[k].u>=up&&Tree[k].l>=lft&&Tree[k].r<=rght)
inline void build(int k,int up,int down,int lft,int rght){
	Tree[k].u=up,Tree[k].d=down,Tree[k].l=lft,Tree[k].r=rght;
	if(uns(k))return;
	if(up==down&&lft==rght){Tree[k].sum=0;return;}
	int ms=(up+down)>>1,ls=(lft+rght)>>1;
	build(zs(k),up,ms,lft,ls);
	build(ys(k),up,ms,ls+1,rght);
	build(zx(k),ms+1,down,lft,ls);
	build(yx(k),ms+1,down,ls+1,rght);
}
inline void push(int k){Tree[k].sum=0,Tree[k].tgv=0,Tree[k].tg_re=1;}
inline void upd(int k,int v){
	if(Tree[k].tg_re){
		f(j,0,3)if(!uns(k<<2|j))push(k<<2|j);
		Tree[k].tg_re=0;
	}
	Tree[k].sum+=(Tree[k].r-Tree[k].l+1)*(Tree[k].d-Tree[k].u+1)*v,Tree[k].tgv+=v;
}
inline void pushdown(int k){
	if(Tree[k].tgv){
		f(j,0,3)if(!uns(k<<2|j))upd(k<<2|j,Tree[k].tgv);
		Tree[k].tgv=0;
	}
	if(Tree[k].tg_re){
		f(j,0,3)if(!uns(k<<2|j))push(k<<2|j);
		Tree[k].tg_re=0;
	}
}
inline void pushup(int k){Tree[k].sum=0;f(j,0,3)if(!uns(k<<2|j))Tree[k].sum+=Tree[k<<2|j].sum;}
inline void modify(int k,int up,int down,int lft,int rght,int v){
	if(uns(k))return;
	if(!ist(k,up,down,lft,rght))return;
	if(ctn(k,up,down,lft,rght)){
		upd(k,v);return;
	}
	pushdown(k);
	if(lft<=midx){
		if(up<=midy){
			Tree[k].sum-=Tree[zs(k)].sum;
			modify(zs(k),up,down,lft,rght,v);
			Tree[k].sum+=Tree[zs(k)].sum;
		}
		if(down>midy&&Tree[k].u!=Tree[k].d){
			Tree[k].sum-=Tree[zx(k)].sum;
			modify(zx(k),up,down,lft,rght,v);
			Tree[k].sum+=Tree[zx(k)].sum;
		}
	}
	if(rght>midx&&Tree[k].l!=Tree[k].r){
		if(up<=midy){
			Tree[k].sum-=Tree[ys(k)].sum;
			modify(ys(k),up,down,lft,rght,v);
			Tree[k].sum+=Tree[ys(k)].sum;
		}
		if(down>midy&&Tree[k].u!=Tree[k].d){
			Tree[k].sum-=Tree[yx(k)].sum;
			modify(yx(k),up,down,lft,rght,v);
			Tree[k].sum+=Tree[yx(k)].sum;
		}
	}
}
inline void modi_re(int k,int up,int down,int lft,int rght){
	if(ctn(k,up,down,lft,rght)){
		push(k);return;
	}
	pushdown(k);
	if(lft<=midx){
		if(up<=midy){
			Tree[k].sum-=Tree[zs(k)].sum;
			modi_re(zs(k),up,down,lft,rght);
			Tree[k].sum+=Tree[zs(k)].sum;
		}
		if(down>midy&&Tree[k].u!=Tree[k].d){
			Tree[k].sum-=Tree[zx(k)].sum;
			modi_re(zx(k),up,down,lft,rght);
			Tree[k].sum+=Tree[zx(k)].sum;
		}
	}
	if(rght>midx&&Tree[k].l!=Tree[k].r){
		if(up<=midy){
			Tree[k].sum-=Tree[ys(k)].sum;
			modi_re(ys(k),up,down,lft,rght);
			Tree[k].sum+=Tree[ys(k)].sum;
		}
		if(down>midy&&Tree[k].u!=Tree[k].d){
			Tree[k].sum-=Tree[yx(k)].sum;
			modi_re(yx(k),up,down,lft,rght);
			Tree[k].sum+=Tree[yx(k)].sum;
		}
	}
}
inline int ask(int k,int up,int down,int lft,int rght){
	if(uns(k))return 0;
	if(!ist(k,up,down,lft,rght))return 0;
	if(ctn(k,up,down,lft,rght)){
		return Tree[k].sum;
	}
	pushdown(k);
	int sc=0;
	f(j,0,3)sc+=ask(k<<2|j,up,down,lft,rght);return sc;
}
int dp[2010];
namespace sss{
	int dp[2010][2010];
	bitset<2010> bs[2010];
	bitset<2010> bsp[2010];
	void gs(){
		int ans=0;
		f(i,1,n){
			for(int l=1;l<=m;l++){
				if(!(i>1&&mp[i-1][l]==mp[i][l])){bs[l].reset();}
				if(!(i>1&&mp[i-1][l]==mp[i][l])){bsp[l].reset();}
			}
			int lst=0;
			for(int k=1;k<=m;k++){
				if(mp[i][k]!=mp[i][k-1]){
					lst=k;
				}
				for(int j=k-1;j>=lst;j--){
					if(!bs[j][k]||!bsp[k][j]){
						dp[j][k]=1;
						bs[j][k]=1;
						bsp[k][j]=1;
						continue;
					}
					ans+=dp[j][k];
					dp[j][k]++;
				}
			}
		}
		cout<<ans<<endl;
	}
}
int cnt=0;
const int base=10000;
inline void gs(){
	scanf("%lld%lld",&n,&m);
	char s=0;
	int cnt=0;
	f(i,1,n)f(j,1,m){
		char c=getchar();
		while(c>'z'||c<'a')c=getchar();
		mp[i][j]=c;
		if(s==0)s=mp[i][j];
		if(s!=mp[i][j])s=18;
		cnt+=(i==1||mp[i][j]!=mp[i-1][j]);
	}
	if(s!=18){
		cout<<(n*(n-1)/2*m*(m-1)/2)<<endl;return;
	}
//	cout<<cnt<<endl;
	if(cnt==n*m){cout<<0<<endl;return;}
	if(cnt>=base){sss::gs();return;}
	build(1,1,m,1,m);
	int ans=0;
	f(i,1,n){
		int lst=1;
		f(l,1,m){
			if(i<=1||mp[i][l]!=mp[i-1][l]){
				dp[l]=0;
				++cnt;
			}else{
				if(lst<=l-1){
					modi_re(1,lst,l-1,1,m);
					modi_re(1,1,m,lst,l-1);
				}
				lst=l+1;
			}
		}
		if(lst<=m){
			modi_re(1,lst,m,1,m);
			modi_re(1,1,m,lst,m);
		}
		lst=0;
		int sum=0;
		for(int k=1;k<=m;k++){
			if(mp[i][k]!=mp[i][k-1]){
				ans+=(ask(1,lst,k-1,lst,k-1)-sum)/2;
				modify(1,lst,k-1,lst,k-1,1);
				lst=k;
				sum=0;
			}
			sum+=dp[k];
		}
		ans+=(ask(1,lst,m,lst,m)-sum)/2;
		modify(1,lst,m,lst,m,1);
		f(k,1,m)dp[k]++;
	}
	cout<<ans<<endl;
}
signed main(){
//	freopen("jx.out","r",stdin);
	gs();
	return 0;
}