oj.uz

Submission #642443

# Submission time Handle Problem Language Result Execution time Memory
642443 2022-09-19T12:58:45 Z jamezzz Sandcastle 2 (JOI22_ho_t5) C++17
71 / 100
 5000 ms 37668 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){
		mx[i].resize(w);
		mn[i].resize(w);
		for(int j=0;j<w;++j){
			mx[i][j].resize(w);
			mn[i][j].resize(w);
		}
	}
	for(int i=0;i<h;++i){
		sm[i].resize(w);
		for(int j=0;j<w;++j){
			sm[i][j].resize(w);
			for(int k=0;k<w;++k)sm[i][j][k].resize(4);
		}
		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){
			mn[i][j][j]=mx[i][j][j]=a[i][j];
			for(int k=j;k<w;++k){
				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 5059 ms 24464 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 7 ms 1028 KB Output is correct
8 Correct 7 ms 1024 KB Output is correct
9 Correct 10 ms 3796 KB Output is correct
10 Correct 10 ms 3440 KB Output is correct
11 Correct 9 ms 1008 KB Output is correct
12 Correct 12 ms 1008 KB Output is correct
13 Correct 11 ms 4052 KB Output is correct
14 Correct 8 ms 2516 KB Output is correct
15 Correct 12 ms 3388 KB Output is correct
16 Correct 12 ms 3412 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 7 ms 1028 KB Output is correct
8 Correct 7 ms 1024 KB Output is correct
9 Correct 10 ms 3796 KB Output is correct
10 Correct 10 ms 3440 KB Output is correct
11 Correct 9 ms 1008 KB Output is correct
12 Correct 12 ms 1008 KB Output is correct
13 Correct 11 ms 4052 KB Output is correct
14 Correct 8 ms 2516 KB Output is correct
15 Correct 12 ms 3388 KB Output is correct
16 Correct 12 ms 3412 KB Output is correct
17 Correct 131 ms 3712 KB Output is correct
18 Correct 133 ms 24160 KB Output is correct
19 Correct 156 ms 7244 KB Output is correct
20 Correct 156 ms 36224 KB Output is correct
21 Correct 134 ms 37568 KB Output is correct
22 Correct 138 ms 37668 KB Output is correct
23 Correct 151 ms 36340 KB Output is correct
24 Correct 109 ms 26324 KB Output is correct
25 Correct 138 ms 33380 KB Output is correct
26 Correct 144 ms 35136 KB Output is correct
27 Correct 146 ms 33356 KB Output is correct
28 Correct 146 ms 35172 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 7 ms 1028 KB Output is correct
8 Correct 7 ms 1024 KB Output is correct
9 Correct 10 ms 3796 KB Output is correct
10 Correct 10 ms 3440 KB Output is correct
11 Correct 9 ms 1008 KB Output is correct
12 Correct 12 ms 1008 KB Output is correct
13 Correct 11 ms 4052 KB Output is correct
14 Correct 8 ms 2516 KB Output is correct
15 Correct 12 ms 3388 KB Output is correct
16 Correct 12 ms 3412 KB Output is correct
17 Correct 131 ms 3712 KB Output is correct
18 Correct 133 ms 24160 KB Output is correct
19 Correct 156 ms 7244 KB Output is correct
20 Correct 156 ms 36224 KB Output is correct
21 Correct 134 ms 37568 KB Output is correct
22 Correct 138 ms 37668 KB Output is correct
23 Correct 151 ms 36340 KB Output is correct
24 Correct 109 ms 26324 KB Output is correct
25 Correct 138 ms 33380 KB Output is correct
26 Correct 144 ms 35136 KB Output is correct
27 Correct 146 ms 33356 KB Output is correct
28 Correct 146 ms 35172 KB Output is correct
29 Execution timed out 5062 ms 24508 KB Time limit exceeded
30 Halted 0 ms 0 KB -