Submission #529947

#	Time	Username	Problem	Language	Result	Execution time	Memory
529947		fhvirus	Sandcastle 2 (JOI22_ho_t5)	C++17	100 / 100	407 ms	36036 KiB

Main

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

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#define debug(...) ((void)0)
#endif

// d, u, r, l
const int di[4] = {1, -1, 0, 0};
const int dj[4] = {0, 0, 1, -1};

const int kN = 51215;
int H, W, A[kN], AT[kN];
int B[9][9][kN], C[9][6][kN], D[6][6][kN], S[6][kN];
int PS5[kN], SA[kN], SB[kN], cnt[kN * 2];

int get_sum(int th, int i, int lb, int rb) {
	if (rb - lb + 1 == 1) return D[th][0][i * W + lb];
	if (rb - lb + 1 == 2) return D[th][1][i * W + lb];
	if (rb - lb + 1 == 3) return D[th][2][i * W + lb];
	if (rb - lb + 1 == 4) return D[th][3][i * W + lb] + D[th][4][i * W + lb + 2];
	return D[th][3][i * W + lb] + 
		(S[th][i * W + rb - 1] - S[th][i * W + lb + 2]) +
		D[th][4][i * W + rb - 1];
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> H >> W;
	for (int i = 0; i < H * W; ++i)
		cin >> A[i];

	if (H < W) {
		for (int i = 0; i < H * W; ++i)
			AT[(i % W) * H + (i / W)] = A[i];
		for (int i = 0; i < H * W; ++i)
			A[i] = AT[i];
		swap(H, W);
	}

	// B[th][tw][i]: in degree of cell i when U-D side type th, L-R type tw 
	// 0:  - -[x]- -  1:  - -[x -]-  2:  - -[x - -|
	// 3:  -[- x]- -  4:  -[- x -]-  5:  -[- x - -|
	// 6: |- - x]- -  7: |- - x -]-  8: |- - x - -|
	// [: Edge |: not necessary an edge
	for (int th = 0; th < 9; ++th)
		for (int tw = 0; tw < 9; ++tw)
			for (int i = 0; i < H; ++i)
				for (int j = 0; j < W; ++j) {
					int bu = i - th / 3, bd = i + th % 3;
					int bl = j - tw / 3, br = j + tw % 3;
					if (bu < 0 or bd >= H or bl < 0 or br >= W)
						continue;
					// iterate neighbor
					int indeg = 0;
					for (int d = 0; d < 4; ++d) {
						int ni = i + di[d], nj = j + dj[d];
						if (ni < bu or ni > bd or nj < bl or nj > br or A[i * W + j] > A[ni * W + nj])
							continue;
						// iterate neighbor's neighbor
						int to_num = A[i * W + j];
						for (int dn = 0; dn < 4; ++dn) {
							int mi = ni + di[dn], mj = nj + dj[dn];
							if (mi < bu or mi > bd or mj < bl or mj > br or A[mi * W + mj] > A[ni * W + nj])
								continue;
							to_num = max(to_num, A[mi * W + mj]);
						}
						if (to_num == A[i * W + j])
							++indeg;
					}
					B[th][tw][i * W + j] = (indeg == 0);
				}

	// Gather the values of cells at the edges.
	// C[th][tw][i]: in degree of cell i when U-D side type th, L-R type tw 
	// 0: [x]  1: [x -] + [- x]  2: [x - -] + [- x -] + [- - x]
	// 3: [x - - -| + [- x - -|  4: |- - x -] + |- - - x]
	// 5: |- - x - -|
	// The left bound of a type is the same.
	// D goes the same way.
	for (int th = 0; th < 9; ++th)
		for (int i = 0; i < H * W; ++i) {
			C[th][0][i] = B[th][0][i];
			C[th][1][i] = B[th][1][i] + B[th][3][i + 1];
			C[th][2][i] = B[th][2][i] + B[th][4][i + 1] + B[th][6][i + 2];
			C[th][3][i] = B[th][2][i] + B[th][5][i + 1];
			C[th][4][i] = B[th][7][i] + B[th][6][i + 1];
			C[th][5][i] = B[th][8][i];
		}
	for (int tw = 0; tw < 6; ++tw)
		for (int i = 0; i < H * W; ++i) {
			D[0][tw][i] = C[0][tw][i];
			D[1][tw][i] = C[1][tw][i] + C[3][tw][i + W];
			D[2][tw][i] = C[2][tw][i] + C[4][tw][i + W] + C[6][tw][i + 2 * W];
			D[3][tw][i] = C[2][tw][i] + C[5][tw][i + W];
			D[4][tw][i] = C[7][tw][i] + C[6][tw][i + W];
			D[5][tw][i] = C[8][tw][i];
		}

	// Calculate prefix sum
	// S[th][i]: prefix sum when U-D side type th, L-R must be type 5 (inner ones)
	for (int th = 0; th < 6; ++th)
		for (int i = 0; i < H * W; ++i)
			S[th][i + 1] = S[th][i] + D[th][5][i];

	int ans = 0;
	for (int lb = 0; lb < W; ++lb)
		for (int rb = lb; rb < W; ++rb) {
			for (int i = 0; i < H; ++i) {
				PS5[i] = get_sum(5, i, lb, rb) + (i > 0 ? PS5[i - 1] : 0);
				SA[i] = PS5[i] - (i >= 1 ? get_sum(3, i - 1, lb, rb) : 0);
				SB[i] = (i >= 2 ? PS5[i - 2] : 0) + (i >= 1 ? get_sum(4, i - 1, lb, rb) : 0);
			}
			for (int i = 0; i < H; ++i) {
				for (int d = 0; d < 3 and i - d >= 0; ++d)
					ans += (get_sum(d, i - d, lb, rb) == 1);
				if (i < 3) continue;
				cnt[SA[i - 2] + kN]++;
				ans += cnt[SB[i] - 1 + kN];
			}
			for (int i = 0; i + 2 < H; ++i)
				cnt[SA[i] + kN] = 0;
		}

	cout << ans << '\n';

	return 0;
}

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