제출 #1277640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277640		MasterDebater	Sandcastle 2 (JOI22_ho_t5)	C++20	100 / 100	453 ms	17448 KiB

Main

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pb push_back
const ll x[4]={0,0,1,-1},y[4]={-1,1,0,0},INF=1e8;
ll n,m,ans,ans2;
vvi a,f[16],dp[16];
unordered_map<ll,ll>mp;
void rotiraj(){
	vvi b;
	for(int i=0;i<m;i++){
		b.pb({});
		for(int j=0;j<n;j++)b.back().pb(a[j][i]);
	}
	a=b;
	swap(n,m);
	return;
}
void inpt(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		a.pb({});
		for(int j=0;j<m;j++){
			int x;
			cin>>x;
			a.back().pb(x);
		}
	}
	return;
}
void sazimanje(){
	ll cnt=1;
	vi v;
	unordered_map<ll,ll>un;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)v.pb(a[i][j]);
	
	sort(v.begin(),v.end());
	un[v[0]]=cnt++;
	for(int i=1;i<v.size();i++)if(v[i]!=v[i-1])un[v[i]]=cnt++;
	
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j]=un[a[i][j]];
	return;
}
void precompute(){
	for(int k=0;k<16;k++){
		for(int i=0;i<n;i++){
			f[k].pb({});
			dp[k].pb({});
			
			for(int j=0;j<m;j++){
				
				vi v;
				v.pb(0);
				f[k].back().pb(0);
				dp[k].back().pb(0);
				
				for(int q=0;q<4;q++)if((k>>q)&1 and i+x[q]>=0 and i+x[q]<n and j+y[q]>=0 and j+y[q]<m)v.pb(a[i+x[q]][j+y[q]]);
				sort(v.begin(),v.end());
				f[k][i][j]=a[i][j];
				if(v.back()<a[i][j])f[k][i][j]=INF;
				f[k][i][j]-=*(--lower_bound(v.begin(),v.end(),a[i][j]));
				
				if(i==0 and j==0)dp[k][i][j]=f[k][i][j];
				else if(i==0)dp[k][i][j]=f[k][i][j]+dp[k][i][j-1];
				else if(j==0)dp[k][i][j]=f[k][i][j]+dp[k][i-1][j];
				else dp[k][i][j]=f[k][i][j]+dp[k][i-1][j]+dp[k][i][j-1]-dp[k][i-1][j-1];
			}
		}
	}
	return;
}
ll pref(int a,int b,int c,int d,int ind){
	if(a>c or b>d)return 0;
	if(a==0 and b==0)return dp[ind][c][d];
	if(a==0)return dp[ind][c][d]-dp[ind][c][b-1];
	if(b==0)return dp[ind][c][d]-dp[ind][a-1][d];
	return dp[ind][c][d]-dp[ind][c][b-1]-dp[ind][a-1][d]+dp[ind][a-1][b-1];
}
void prav1(){
	ll cnt=1;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++){
		if(j==m-1 or a[i][j+1]>a[i][j])ans+=cnt*(cnt-1)/2,cnt=1;
		else cnt++;
	}
	for(int i=0;i<n;i++)for(int j=0;j<m;j++){
		if(j==m-1 or a[i][j+1]<a[i][j])ans+=cnt*(cnt-1)/2,cnt=1;
		else cnt++;
	}
	for(int j=0;j<m;j++)for(int i=0;i<n;i++){
		if(i==n-1 or a[i+1][j]>a[i][j])ans+=cnt*(cnt-1)/2,cnt=1;
		else cnt++;
	}
	for(int j=0;j<m;j++)for(int i=0;i<n;i++){
		if(i==n-1 or a[i+1][j]<a[i][j])ans+=cnt*(cnt-1)/2,cnt=1;
		else cnt++;
	}
	return;
}
void prav(){
	for(int i1=0;i1<n;i1++)for(int i2=i1+1;i2<n;i2++){
		mp.clear();
		ll sum=0;
		for(int j=0;j<m;j++){
			ll temp=sum;
			
			temp+=f[5][i1][j]+f[9][i2][j]+pref(i1+1,j,i2-1,j,13);
			ans+=mp[INF-temp];
			
			sum+=f[7][i1][j]+f[11][i2][j]+pref(i1+1,j,i2-1,j,15);
			
			temp=-sum+f[6][i1][j]+f[10][i2][j]+pref(i1+1,j,i2-1,j,14);
			
			mp[temp]++;
			//cout<</*temp<<' '<<sum<<' '<<*/f[5][i1][j]<<' '<<f[9][i2][j]<<' '<<f[7][i1][j]<<' '<<f[11][i2][j]<<' '<<f[6][i1][j]<<' '<<f[10][i2][j]<<'\n';
			//cout<<pref(i1+1,j,i2-1,j,13)<<' '<<pref(i1+1,j,i2-1,j,15)<<' '<<pref(i1+1,j,i2-1,j,14)<<'\n';
		}
	}
	return;
}
void solve(){
	inpt();
	
	ans=n*m;
	
	if(n>m)rotiraj();
	sazimanje();
	precompute();
	
	prav1();
	
	prav();
	
	cout<<ans<<'\n';
	return;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t=1;
	//cin>>t;
	while(t--)solve();
	return 0;
}

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