Submission #642451

#TimeUsernameProblemLanguageResultExecution timeMemory
642451jamezzzSandcastle 2 (JOI22_ho_t5)C++17
71 / 100
5095 ms28828 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #ifdef DEBUG #define getchar_unlocked getchar #endif #define sf scanf #define pf printf #define pb push_back #define all(x) x.begin(),x.end() #define lb(x,v) (lower_bound(all(x),v)-x.begin()) #define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin()); typedef vector<int> vi; inline int rd(){ int x=0; char ch=getchar_unlocked(); while(!(ch&16))ch=getchar();//keep reading while current character is whitespace while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered x=(x<<3)+(x<<1)+(ch&15); ch=getchar_unlocked(); } return x; } int h,w; int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};//UDLR vi vals; vector<vi> a; vector<vector<vi>> d,mn,mx; vector<vector<vector<vi>>> sm; int main(){ h=rd(),w=rd(); a.resize(h); for(int i=0;i<h;++i){ a[i].resize(w); for(int j=0;j<w;++j){ a[i][j]=rd(); vals.pb(a[i][j]); } } disc(vals); for(int i=0;i<h;++i){ for(int j=0;j<w;++j)a[i][j]=lb(vals,a[i][j])+1; } if(h<w){ vector<vi> b; b.resize(w); for(int i=0;i<w;++i)b[i].resize(h); for(int i=0;i<h;++i){ for(int j=0;j<w;++j)b[j][i]=a[i][j]; } swap(h,w);swap(a,b); } d.resize(h); for(int i=0;i<h;++i){ d[i].resize(w); for(int j=0;j<w;++j){ d[i][j].resize(16); } } for(int i=0;i<h;++i){ for(int j=0;j<w;++j){ for(int msk=0;msk<16;++msk){ bool valid=true; vector<int> v={0,h*w+1}; for(int k=0;k<4;++k){ if(msk&(1<<k))continue; int ni=i+dx[k],nj=j+dy[k]; if(ni<0||nj<0||ni>=h||nj>=w){ valid=false;continue; } v.pb(a[ni][nj]); } if(!valid){ d[i][j][msk]=-1; continue; } sort(all(v)); int id=lb(v,a[i][j])-1; d[i][j][msk]=v[id+1]-v[id]; } } } sm.resize(h); mx.resize(h); mn.resize(h); for(int i=0;i<h;++i){ sm[i].resize(w); mx[i].resize(w); mn[i].resize(w); vector<vi> pfx; pfx.resize(w); for(int j=0;j<w;++j){ pfx[j].resize(4); pfx[j][0]=d[i][j][0];//both open pfx[j][1]=d[i][j][1];//top close pfx[j][2]=d[i][j][2];//bottom close pfx[j][3]=d[i][j][1+2];//both close if(j==0)continue; for(int k=0;k<4;++k)pfx[j][k]+=pfx[j-1][k]; } for(int j=0;j<w;++j){ sm[i][j].resize(w); mx[i][j].resize(w); mn[i][j].resize(w); mn[i][j][j]=mx[i][j][j]=a[i][j]; for(int k=j;k<w;++k){ sm[i][j][k].resize(4); if(j==k){ sm[i][j][k][0]=d[i][j][4+8];//both open sm[i][j][k][1]=d[i][j][1+4+8];//top clsoe sm[i][j][k][2]=d[i][j][2+4+8];//bottom close sm[i][j][k][3]=d[i][j][1+2+4+8];//both close } else{ mn[i][j][k]=min(mn[i][j][k-1],a[i][k]); mx[i][j][k]=max(mx[i][j][k-1],a[i][k]); sm[i][j][k][0]=d[i][j][4]+d[i][k][8];//both open sm[i][j][k][1]=d[i][j][1+4]+d[i][k][1+8];//top close sm[i][j][k][2]=d[i][j][2+4]+d[i][k][2+8];//bottom close sm[i][j][k][3]=d[i][j][1+2+4]+d[i][k][1+2+8];//both close if(j+1==k)continue; for(int l=0;l<4;++l)sm[i][j][k][l]+=pfx[k-1][l]-pfx[j][l]; } } } } int ans=0; for(int i=0;i<w;++i){ for(int j=i;j<w;++j){ vi pfx; pfx.resize(h); for(int k=0;k<h;++k){ pfx[k]=sm[k][i][j][0]; if(k!=0)pfx[k]+=pfx[k-1]; } for(int k=0;k<h;++k){ int mnv=mn[k][i][j],mxv=mx[k][i][j]; for(int l=k;l<h;++l){ mnv=min(mnv,mn[l][i][j]); mxv=max(mxv,mx[l][i][j]); int tot=0; if(k==l)tot+=sm[k][i][j][3]; else{ tot+=sm[k][i][j][1]; tot+=sm[l][i][j][2]; if(k+1!=l)tot+=pfx[l-1]-pfx[k]; } if(tot==h*w+1+mxv-mnv)++ans; } } } } pf("%d\n",ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...