Submission #1276593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276593		justinlgl20	Sandcastle 2 (JOI22_ho_t5)	C++20	100 / 100	2771 ms	362856 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define f first
#define s second
 
template<template<typename> class Container, typename G>
ostream& operator<<(ostream& os, Container<G> x) {int f=0;os<<'{';for(auto&i:x)os<<(f++ ? ", " : ""),os<<i;os<<"}";return os;}
void _print() {cerr << "]\n";}
template<typename T, typename... V>
void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr <<", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

int lg[500005];
void preprocess(){
	lg[1]=0;
	for(int i=2;i<=500000;i++)lg[i]=lg[i/2]+1;
}

template<typename T>
struct sparseTable{
	vector<vector<sparseTable>>t;
	T op(T a, T b){
		return min(a,b);
	}
	bool end=0;T val;int n;
	template<typename... A> sparseTable(int n,A... args){ this->n=n;t.assign(lg[n]+1,vector<sparseTable>(n,sparseTable(args...))); }
	sparseTable(){end=1;};
	template<typename... A> void upd(int pos,A... args){ t[0][pos].upd(args...); }
	void upd(T v){ val=v; }
	void build(){
		if(end)return; for(int i=0;i<n;i++){t[0][i].build();}
		for(int i=1;i<t.size();i++){ for(int l=0,r=l+(1<<i)-1;r<n;l++,r++){ t[i][l]=t[i-1][l]+t[i-1][l+(1<<(i-1))]; } }
	}
	template<typename... A> T query(int l,int r,A... args){
		int v=lg[r-l+1]; return op(t[v][l].query(args...),t[v][r-(1<<v)+1].query(args...));
	}
	T query(){ return val; }
	sparseTable operator+(sparseTable other){
		sparseTable res=other; if(end){ res.val=op(val,other.val); return res;}
		for(int i=0;i<t.size();i++){ for(int j=0;j<n;j++){ res.t[i][j]=res.t[i][j]+t[i][j]; } }
		return res;
	};
};

int32_t main() {
	int n,m;cin>>n>>m;
	vector<vector<int>>a;
	if(n<m){
		a=vector<vector<int>>(n,vector<int>(m,0));for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>a[i][j];
	}else{
		swap(n,m);
		a=vector<vector<int>>(n,vector<int>(m,0));for(int i=0;i<m;i++)for(int j=0;j<n;j++)cin>>a[j][i];
	}
	vector<vector<int>>norm(n,vector<int>(m,0));
	vector<vector<int>>psa(n,vector<int>(m,0));
	vector<vector<vector<int>>>dir(4,vector<vector<int>>(n,vector<int>(m,0)));
	vector<vector<vector<int>>>ppp(4,vector<vector<int>>(n,vector<int>(m,0)));
	vector<int>dx={-1,1,0,0};
	vector<int>dy={0,0,-1,1};
	function<int(int,int)>get=[&](int i,int j){
		if(0<=i and i<n and 0<=j and j<m)return a[i][j];
		return (int)1e9;
	};
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			norm[i][j]=a[i][j];
			for(int k=0;k<4;k++)dir[k][i][j]=a[i][j];
			for(int k=0;k<4;k++){
				if(get(i+dx[k],j+dy[k])<a[i][j]){
					norm[i][j]=min(norm[i][j],a[i][j]-get(i+dx[k],j+dy[k]));
					for(int v=0;v<4;v++){
						if(v==k)continue;
						dir[v][i][j]=min(dir[v][i][j],a[i][j]-get(i+dx[k],j+dy[k]));
					}
				}
			}
			dbg(a[i][j],norm[i][j]);
		}
	}
	dbg("HI");
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			psa[i][j]=norm[i][j];
			if(i)
				psa[i][j]+=psa[i-1][j];
			for(int k=0;k<4;k++){
				ppp[k][i][j]=dir[k][i][j];
				if(i)
					ppp[k][i][j]+=ppp[k][i-1][j];
			}
		}
	}
	function<int(int,int,int)>sum=[&](int v,int l,int r){
		if(r<l)return 0ll;
		return psa[r][v]-(l?psa[l-1][v]:0ll);
	};
	// this is 4 directions
	preprocess();
	sparseTable<int>mintree(n,m);
	sparseTable<int>maxtree(n,m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			mintree.upd(i,j,a[i][j]);
			maxtree.upd(i,j,-a[i][j]);
		}
	}
	mintree.build();
	maxtree.build();
	int ans=0ll;
	function<int(int,int,int,int)>ssum=[&](int x,int y,int l,int r){
		if(r<l)return 0ll;
		return ppp[x][r][y]-(l?ppp[x][l-1][y]:0ll);
	};
	function<int(int,int,vector<int>)>best=[&](int i,int j,vector<int>d){
		int ans=a[i][j];
		for(int k:d){
			if(get(i+dx[k],j+dy[k])<a[i][j]){
				ans=min(ans,a[i][j]-get(i+dx[k],j+dy[k]));
			}
		}
		return ans;
	};
	// do all of length 1 here
	{
		int hori=0;
		for(int i=0;i<n;i++){
			// all paths of length n
			int s=0; int up=1; int lst=0;
			for(int j=0;j<m;j++){
				int v=a[i][j];
				if(up and v>lst){ }
				else if(!up and v<lst){ }
				else if(up and v<lst){
					hori+=(j-s)*(j-s+1ll)/2;
					hori-=(j-s); s=j-1; up=0;
				}
				else if(!up and v>lst){
					hori+=(j-s)*(j-s+1ll)/2;
					hori-=(j-s); s=j-1; up=1;
				}
				lst=v;
			}
			hori+=(m-s)*(m-s+1ll)/2;
			hori-=(m-s);
		}
		ans+=n*m;
		ans+=hori;
		int vert=0;
		for(int i=0;i<m;i++){
			// all paths of length n
			int s=0; int up=1; int lst=0;
			for(int j=0;j<n;j++){
				int v=a[j][i];
				if(up and v>lst){ }
				if(!up and v<lst){ }
				if(up and v<lst){
					vert+=(j-s)*(j-s+1ll)/2;
					vert-=(j-s); s=j-1; up=0;
				}
				if(!up and v>lst){
					vert+=(j-s)*(j-s+1ll)/2;
					vert-=(j-s); s=j-1; up=1;
				}
				lst=v;
			}
			vert+=(n-s)*(n-s+1ll)/2;
			vert-=(n-s);
		}
		ans+=vert;
		dbg(hori,vert);
	}
	dbg(ans);
	dbg(best(1,1,{0,3}));

	// do all with sides >=2 here
	for(int l=0;l<n;l++){
		for(int r=l;r<n;r++){
			// [l,r] is one dimension
			// now calculate all values
			vector<int>s(m),ll(m),rr(m),ps(m);
			if(r-l+1>=2){
				dbg(l,r,a[0],a[1]);
				for(int i=0;i<m;i++){ s[i]=sum(i,l+1,r-1); }
				for(int i=0;i<m;i++){
					s[i]+=dir[1][r][i];
					s[i]+=dir[0][l][i];
					ll[i]=ssum(2,i,l+1,r-1)+best(l,i,{1,3})+best(r,i,{0,3});
					rr[i]=ssum(3,i,l+1,r-1)+best(l,i,{1,2})+best(r,i,{0,2});
				}
				for(int i=0;i<m;i++){
					ps[i]=s[i];
					if(i)ps[i]+=ps[i-1];
				}
				dbg(s,ll,rr);
				// s in middle special case corners
				// left is 2, right is 3
				for(int x=0;x<m;x++){
					for(int y=x+1;y<m;y++){
						// ll[x]+rr[y]+s for the things in between
						int val=ps[y-1]-ps[x]+ll[x]+rr[y];
						int v=-maxtree.query(l,r,x,y);
						dbg(x,y,val,v);
						if(v==val){
							ans++;
						}
					}
				}

			}else{

			}
		}
	}
	cout<<ans<<"\n";
}

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