Submission #1276474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276474		Ivo_12	Sandcastle 2 (JOI22_ho_t5)	C++20	100 / 100	431 ms	15800 KiB

Main

#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define pii pair < int, int >
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;

using namespace std;

const ll inf = (ll) 1e11;
const vector < ll > nul;

int h, w;
vector < vector < ll > > mat;
vector < vector < ll > > prefsum[16];// 1 = x + 1, 2 = y + 1, 4 = x - 1, 8 = y - 1
pii dir[4] = {mp(0, 1), mp(1, 0), mp(0, -1), mp(-1, 0)};
int l2[16] = {0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3};
unordered_map < ll, ll > rep;

bool inbounds( int y, int x ) {return (y >= 0 && y < h && x >= 0 && x < w);}

void flipmat( void ) {
	
	vector < vector < ll > > newmat;
	for(int i = 0; i < w; i++) {
		newmat.pb(nul);
		for(int j = 0; j < h; j++) {
			newmat[i].pb(mat[j][i]);
		}
	}
	
	mat = newmat;
	swap(h, w);
	
	return;
}

ll rec( int k, int y1, int x1, int y2, int x2 ) {
	return prefsum[k][y1][x1] - prefsum[k][y2][x1] - prefsum[k][y1][x2] + prefsum[k][y2][x2];
}

void task( void ) {
	
	cin >> h >> w;
	
	for(int i = 0; i < h; i++) {
		mat.pb(nul);
		
		for(int j = 0; j < w; j++) {
			mat[i].pb(0);
			cin >> mat[i][j];
		}
	}
	
	if(h > w) flipmat();
	
	int curbit;
	int prevval;
	//mark sus
	for(int i = 0; i < 16; i++) {
		prefsum[i].pb(nul);
		for(int j = 0; j < w + 1; j++) prefsum[i][0].pb(0);
		
		curbit = l2[i & -i];
		
		for(int j = 1; j < h + 1; j++) {
			
			prefsum[i].pb(nul);
			prefsum[i][j].pb(0);
			
			for(int z = 1; z < w + 1; z++) {
				prefsum[i][j].pb(mat[j - 1][z - 1]);
			}
			
		}
		
		if(i != 0) {
			prevval = i - (i&-i);
			for(int j = 1; j < h + 1; j++) {
				for(int z = 1; z < w + 1; z++) {
					prefsum[i][j][z] = prefsum[prevval][j][z];
					
					if(inbounds(j + dir[curbit].F - 1, z + dir[curbit].S - 1) && mat[j + dir[curbit].F - 1][z + dir[curbit].S - 1] < mat[j - 1][z - 1]) 
					prefsum[i][j][z] = min(prefsum[prevval][j][z], mat[j - 1][z - 1] - mat[j + dir[curbit].F - 1][z + dir[curbit].S - 1]);
				}
			}
		}
	}
	
	//mark the biggest
	bool biggest;
	for(int i = 0; i < 16; i++) {
		for(int j = 0; j < h; j++) {
			for(int z = 0; z < w; z++) {
				biggest = 1;
				
				for(int k = 0; k < 4; k++) {
					if(inbounds(j + dir[k].F, z + dir[k].S) && ((1<<k) & i) 
					&& mat[j + dir[k].F][z + dir[k].S] > mat[j][z]) biggest = 0;
				}
				
				if(biggest) prefsum[i][j + 1][z + 1] += inf - mat[j][z];
			}
		}
	}
	
	//make sums
	for(int i = 0; i < 16; i++) {
		for(int j = 1; j < h + 1; j++) {
			for(int z = 1; z < w + 1; z++) {
				prefsum[i][j][z] += prefsum[i][j - 1][z] + prefsum[i][j][z - 1] - prefsum[i][j - 1][z - 1];
			}
		}
	}
	
	ll cur = 0;
	ll sol = 0;
	for(int i = 0; i < h; i++) {
		for(int j = i; j < h; j++) {
			cur = 0;
			rep.clear();
			
			for(int z = 0; z < w; z++) {
				if(j - i > 0) {
					if(rec(2, i, z, i + 1, z + 1) + rec(8, j, z, j + 1, z + 1) + rec(10, i + 1, z, j, z + 1) == inf) sol++;
					
					sol += rep[inf - rec(6, i, z, i + 1, z + 1) - rec(12, j, z, j + 1, z + 1) - rec(14, i + 1, z, j, z + 1) - cur];
					
					cur += rec(7, i, z, i + 1, z + 1) + rec(13, j, z, j + 1, z + 1) + rec(15, i + 1, z, j, z + 1);
					rep[rec(3, i, z, i + 1, z + 1) + rec(9, j, z, j + 1, z + 1) + rec(11, i + 1, z, j, z + 1) - cur]++;
				}
				
				else {
					sol++;
					
					sol += rep[inf - rec(4, i, z, i + 1, z + 1) - cur];
					
					cur += rec(5, i, z, i + 1, z + 1);
					rep[rec(1, i, z, i + 1, z + 1) - cur]++;
				}
			}
		}
	}
	
	cout << sol << "\n";
	
	return;
}

int main( void ) {
	
	FIO;
	task();
	
	return 0;
}

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