QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1045 | #666401 | #21696. 【NOIP Round #3】数圈圈 | cleverpenguin | cleverpenguin | Failed. | 2024-10-22 18:15:27 | 2024-10-23 22:28:20 |
Details
Extra Test:
Accepted
time: 3ms
memory: 17908kb
input:
2 2 aa aa
output:
1
result:
ok "1"
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#666401 | #21696. 【NOIP Round #3】数圈圈 | cleverpenguin | 100 ✓ | 770ms | 227420kb | C++14 | 3.7kb | 2024-10-22 18:13:39 | 2024-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;
}