Submission #642457

#	Time	Username	Problem	Language	Result	Execution time	Memory
642457		jamezzz	Sandcastle 2 (JOI22_ho_t5)	C++17	100 / 100	1616 ms	442608 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("-O3")
#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;
}

#define maxn 50005

int h,w;
map<int,int> cnt;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};//UDLR
vi vals;
vector<vi> a;
vector<vector<vi>> d;
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};
				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]=a[i][j]-v[id];
				if(id==v.size()-1)d[i][j][msk]+=h*w+1-a[i][j];
			}
		}
	}
	sm.resize(h);
	for(int i=0;i<h;++i){
		sm[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);
			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 close
					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{
					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){
			int offset=0;
			for(int k=0;k<h;++k){
				if(sm[k][i][j][3]==h*w+1)++ans;
				if(sm[k][i][j][2]!=-1){
					int goal=h*w+1-sm[k][i][j][2];
					if(cnt.find(goal-offset)!=cnt.end())ans+=cnt[goal-offset];
				}
				if(sm[k][i][j][0]!=-1)offset+=sm[k][i][j][0];
				int add=sm[k][i][j][1];
				if(cnt.find(add-offset)==cnt.end())cnt[add-offset]=0;
				++cnt[add-offset];
			}
			cnt.clear();
		}
	}
	pf("%d\n",ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:90:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     if(id==v.size()-1)d[i][j][msk]+=h*w+1-a[i][j];
      |        ~~^~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 56 / 56
• Subtask 5: 20 / 20