oj.uz

Submission #642441

# Submission time Handle Problem Language Result Execution time Memory
642441 2022-09-19T12:55:42 Z jamezzz Sandcastle 2 (JOI22_ho_t5) C++17
71 / 100
 5000 ms 37748 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define psf push_front
#define ppb pop_back
#define ppf pop_front
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

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){
					mnto(mnv,mn[l][i][j]);
					mxto(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 5053 ms 24468 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 468 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 468 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 980 KB Output is correct
8 Correct 8 ms 1040 KB Output is correct
9 Correct 10 ms 3796 KB Output is correct
10 Correct 10 ms 3412 KB Output is correct
11 Correct 10 ms 980 KB Output is correct
12 Correct 10 ms 1008 KB Output is correct
13 Correct 10 ms 4048 KB Output is correct
14 Correct 6 ms 2596 KB Output is correct
15 Correct 11 ms 3412 KB Output is correct
16 Correct 10 ms 3396 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 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 980 KB Output is correct
8 Correct 8 ms 1040 KB Output is correct
9 Correct 10 ms 3796 KB Output is correct
10 Correct 10 ms 3412 KB Output is correct
11 Correct 10 ms 980 KB Output is correct
12 Correct 10 ms 1008 KB Output is correct
13 Correct 10 ms 4048 KB Output is correct
14 Correct 6 ms 2596 KB Output is correct
15 Correct 11 ms 3412 KB Output is correct
16 Correct 10 ms 3396 KB Output is correct
17 Correct 140 ms 3712 KB Output is correct
18 Correct 142 ms 24088 KB Output is correct
19 Correct 117 ms 7260 KB Output is correct
20 Correct 141 ms 36248 KB Output is correct
21 Correct 146 ms 37748 KB Output is correct
22 Correct 149 ms 37684 KB Output is correct
23 Correct 137 ms 36240 KB Output is correct
24 Correct 111 ms 26324 KB Output is correct
25 Correct 166 ms 33388 KB Output is correct
26 Correct 161 ms 35176 KB Output is correct
27 Correct 146 ms 33324 KB Output is correct
28 Correct 149 ms 35180 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 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 980 KB Output is correct
8 Correct 8 ms 1040 KB Output is correct
9 Correct 10 ms 3796 KB Output is correct
10 Correct 10 ms 3412 KB Output is correct
11 Correct 10 ms 980 KB Output is correct
12 Correct 10 ms 1008 KB Output is correct
13 Correct 10 ms 4048 KB Output is correct
14 Correct 6 ms 2596 KB Output is correct
15 Correct 11 ms 3412 KB Output is correct
16 Correct 10 ms 3396 KB Output is correct
17 Correct 140 ms 3712 KB Output is correct
18 Correct 142 ms 24088 KB Output is correct
19 Correct 117 ms 7260 KB Output is correct
20 Correct 141 ms 36248 KB Output is correct
21 Correct 146 ms 37748 KB Output is correct
22 Correct 149 ms 37684 KB Output is correct
23 Correct 137 ms 36240 KB Output is correct
24 Correct 111 ms 26324 KB Output is correct
25 Correct 166 ms 33388 KB Output is correct
26 Correct 161 ms 35176 KB Output is correct
27 Correct 146 ms 33324 KB Output is correct
28 Correct 149 ms 35180 KB Output is correct
29 Execution timed out 5068 ms 24456 KB Time limit exceeded
30 Halted 0 ms 0 KB -