oj.uz

Submission #642445

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

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 5021 ms 24492 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 0 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 0 ms 340 KB Output is correct
7 Correct 9 ms 1024 KB Output is correct
8 Correct 8 ms 980 KB Output is correct
9 Correct 9 ms 2988 KB Output is correct
10 Correct 12 ms 2772 KB Output is correct
11 Correct 13 ms 988 KB Output is correct
12 Correct 11 ms 980 KB Output is correct
13 Correct 8 ms 3156 KB Output is correct
14 Correct 5 ms 2004 KB Output is correct
15 Correct 9 ms 2764 KB Output is correct
16 Correct 9 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 0 ms 340 KB Output is correct
7 Correct 9 ms 1024 KB Output is correct
8 Correct 8 ms 980 KB Output is correct
9 Correct 9 ms 2988 KB Output is correct
10 Correct 12 ms 2772 KB Output is correct
11 Correct 13 ms 988 KB Output is correct
12 Correct 11 ms 980 KB Output is correct
13 Correct 8 ms 3156 KB Output is correct
14 Correct 5 ms 2004 KB Output is correct
15 Correct 9 ms 2764 KB Output is correct
16 Correct 9 ms 2644 KB Output is correct
17 Correct 159 ms 3916 KB Output is correct
18 Correct 112 ms 18744 KB Output is correct
19 Correct 127 ms 5976 KB Output is correct
20 Correct 137 ms 27784 KB Output is correct
21 Correct 120 ms 28756 KB Output is correct
22 Correct 137 ms 28868 KB Output is correct
23 Correct 111 ms 27664 KB Output is correct
24 Correct 99 ms 20268 KB Output is correct
25 Correct 154 ms 25620 KB Output is correct
26 Correct 139 ms 26968 KB Output is correct
27 Correct 168 ms 25548 KB Output is correct
28 Correct 118 ms 26884 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 0 ms 340 KB Output is correct
7 Correct 9 ms 1024 KB Output is correct
8 Correct 8 ms 980 KB Output is correct
9 Correct 9 ms 2988 KB Output is correct
10 Correct 12 ms 2772 KB Output is correct
11 Correct 13 ms 988 KB Output is correct
12 Correct 11 ms 980 KB Output is correct
13 Correct 8 ms 3156 KB Output is correct
14 Correct 5 ms 2004 KB Output is correct
15 Correct 9 ms 2764 KB Output is correct
16 Correct 9 ms 2644 KB Output is correct
17 Correct 159 ms 3916 KB Output is correct
18 Correct 112 ms 18744 KB Output is correct
19 Correct 127 ms 5976 KB Output is correct
20 Correct 137 ms 27784 KB Output is correct
21 Correct 120 ms 28756 KB Output is correct
22 Correct 137 ms 28868 KB Output is correct
23 Correct 111 ms 27664 KB Output is correct
24 Correct 99 ms 20268 KB Output is correct
25 Correct 154 ms 25620 KB Output is correct
26 Correct 139 ms 26968 KB Output is correct
27 Correct 168 ms 25548 KB Output is correct
28 Correct 118 ms 26884 KB Output is correct
29 Execution timed out 5052 ms 24520 KB Time limit exceeded
30 Halted 0 ms 0 KB -