QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#688911 | #1085. Brave Seekers of Unicorns | 0xyz | WA | 1ms | 5600kb | C++14 | 3.6kb | 2024-10-30 14:15:44 | 2024-10-30 14:15:45 |
Judging History
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'