oj.uz

Submission #529947

# Submission time Handle Problem Language Result Execution time Memory
529947 2022-02-24T06:21:06 Z fhvirus Sandcastle 2 (JOI22_ho_t5) C++17
100 / 100
 407 ms 36036 KB 
/*
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 35 ms 22232 KB Output is correct
3 Correct 35 ms 22360 KB Output is correct
4 Correct 35 ms 22624 KB Output is correct
5 Correct 34 ms 22624 KB Output is correct
6 Correct 42 ms 22832 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 2 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 2 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 2 ms 1472 KB Output is correct
8 Correct 2 ms 1484 KB Output is correct
9 Correct 6 ms 2124 KB Output is correct
10 Correct 4 ms 2124 KB Output is correct
11 Correct 2 ms 1612 KB Output is correct
12 Correct 3 ms 1612 KB Output is correct
13 Correct 4 ms 2124 KB Output is correct
14 Correct 4 ms 1740 KB Output is correct
15 Correct 7 ms 2124 KB Output is correct
16 Correct 7 ms 2124 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 2 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 2 ms 1472 KB Output is correct
8 Correct 2 ms 1484 KB Output is correct
9 Correct 6 ms 2124 KB Output is correct
10 Correct 4 ms 2124 KB Output is correct
11 Correct 2 ms 1612 KB Output is correct
12 Correct 3 ms 1612 KB Output is correct
13 Correct 4 ms 2124 KB Output is correct
14 Correct 4 ms 1740 KB Output is correct
15 Correct 7 ms 2124 KB Output is correct
16 Correct 7 ms 2124 KB Output is correct
17 Correct 6 ms 3788 KB Output is correct
18 Correct 30 ms 5972 KB Output is correct
19 Correct 25 ms 5912 KB Output is correct
20 Correct 22 ms 5964 KB Output is correct
21 Correct 21 ms 5836 KB Output is correct
22 Correct 23 ms 5776 KB Output is correct
23 Correct 21 ms 5708 KB Output is correct
24 Correct 21 ms 5196 KB Output is correct
25 Correct 27 ms 5940 KB Output is correct
26 Correct 29 ms 5864 KB Output is correct
27 Correct 43 ms 5900 KB Output is correct
28 Correct 38 ms 5900 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 2 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 2 ms 1472 KB Output is correct
8 Correct 2 ms 1484 KB Output is correct
9 Correct 6 ms 2124 KB Output is correct
10 Correct 4 ms 2124 KB Output is correct
11 Correct 2 ms 1612 KB Output is correct
12 Correct 3 ms 1612 KB Output is correct
13 Correct 4 ms 2124 KB Output is correct
14 Correct 4 ms 1740 KB Output is correct
15 Correct 7 ms 2124 KB Output is correct
16 Correct 7 ms 2124 KB Output is correct
17 Correct 6 ms 3788 KB Output is correct
18 Correct 30 ms 5972 KB Output is correct
19 Correct 25 ms 5912 KB Output is correct
20 Correct 22 ms 5964 KB Output is correct
21 Correct 21 ms 5836 KB Output is correct
22 Correct 23 ms 5776 KB Output is correct
23 Correct 21 ms 5708 KB Output is correct
24 Correct 21 ms 5196 KB Output is correct
25 Correct 27 ms 5940 KB Output is correct
26 Correct 29 ms 5864 KB Output is correct
27 Correct 43 ms 5900 KB Output is correct
28 Correct 38 ms 5900 KB Output is correct
29 Correct 36 ms 22156 KB Output is correct
30 Correct 206 ms 36036 KB Output is correct
31 Correct 407 ms 35980 KB Output is correct
32 Correct 38 ms 25800 KB Output is correct
33 Correct 289 ms 35820 KB Output is correct
34 Correct 309 ms 35608 KB Output is correct
35 Correct 157 ms 23860 KB Output is correct
36 Correct 266 ms 35384 KB Output is correct
37 Correct 399 ms 35604 KB Output is correct
38 Correct 328 ms 35556 KB Output is correct
39 Correct 351 ms 35556 KB Output is correct
40 Correct 322 ms 35708 KB Output is correct
41 Correct 377 ms 35716 KB Output is correct
42 Correct 349 ms 35360 KB Output is correct
43 Correct 370 ms 35488 KB Output is correct
44 Correct 331 ms 35276 KB Output is correct