oj.uz

Submission #642451

# Submission time Handle Problem Language Result Execution time Memory
642451 2022-09-19T13:12:11 Z jamezzz Sandcastle 2 (JOI22_ho_t5) C++17
71 / 100
 5000 ms 28828 KB 
#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);
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 5095 ms 24480 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 8 ms 1032 KB Output is correct
8 Correct 8 ms 980 KB Output is correct
9 Correct 8 ms 3028 KB Output is correct
10 Correct 8 ms 2644 KB Output is correct
11 Correct 11 ms 1108 KB Output is correct
12 Correct 9 ms 980 KB Output is correct
13 Correct 8 ms 3104 KB Output is correct
14 Correct 6 ms 2004 KB Output is correct
15 Correct 8 ms 2772 KB Output is correct
16 Correct 8 ms 2644 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 8 ms 1032 KB Output is correct
8 Correct 8 ms 980 KB Output is correct
9 Correct 8 ms 3028 KB Output is correct
10 Correct 8 ms 2644 KB Output is correct
11 Correct 11 ms 1108 KB Output is correct
12 Correct 9 ms 980 KB Output is correct
13 Correct 8 ms 3104 KB Output is correct
14 Correct 6 ms 2004 KB Output is correct
15 Correct 8 ms 2772 KB Output is correct
16 Correct 8 ms 2644 KB Output is correct
17 Correct 151 ms 3704 KB Output is correct
18 Correct 115 ms 18740 KB Output is correct
19 Correct 125 ms 5972 KB Output is correct
20 Correct 119 ms 27900 KB Output is correct
21 Correct 115 ms 28708 KB Output is correct
22 Correct 115 ms 28828 KB Output is correct
23 Correct 134 ms 27652 KB Output is correct
24 Correct 90 ms 20180 KB Output is correct
25 Correct 149 ms 25616 KB Output is correct
26 Correct 114 ms 26940 KB Output is correct
27 Correct 160 ms 25620 KB Output is correct
28 Correct 115 ms 26964 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 8 ms 1032 KB Output is correct
8 Correct 8 ms 980 KB Output is correct
9 Correct 8 ms 3028 KB Output is correct
10 Correct 8 ms 2644 KB Output is correct
11 Correct 11 ms 1108 KB Output is correct
12 Correct 9 ms 980 KB Output is correct
13 Correct 8 ms 3104 KB Output is correct
14 Correct 6 ms 2004 KB Output is correct
15 Correct 8 ms 2772 KB Output is correct
16 Correct 8 ms 2644 KB Output is correct
17 Correct 151 ms 3704 KB Output is correct
18 Correct 115 ms 18740 KB Output is correct
19 Correct 125 ms 5972 KB Output is correct
20 Correct 119 ms 27900 KB Output is correct
21 Correct 115 ms 28708 KB Output is correct
22 Correct 115 ms 28828 KB Output is correct
23 Correct 134 ms 27652 KB Output is correct
24 Correct 90 ms 20180 KB Output is correct
25 Correct 149 ms 25616 KB Output is correct
26 Correct 114 ms 26940 KB Output is correct
27 Correct 160 ms 25620 KB Output is correct
28 Correct 115 ms 26964 KB Output is correct
29 Execution timed out 5018 ms 24472 KB Time limit exceeded
30 Halted 0 ms 0 KB -