oj.uz

Submission #624849

# Submission time Handle Problem Language Result Execution time Memory
624849 2022-08-08T21:05:38 Z QwertyPi Sandcastle 2 (JOI22_ho_t5) C++14
71 / 100
 1172 ms 1048576 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;

const int N = 15013;
const int SQ = 240;
int a[200013];
int b[200013];
bool f[200013];
int s[200013];
int h, w;
inline int id(int i, int j){
	return i * (w + 1) + j;
}
inline int id2(int i, int j){
	return j * (h + 1) + i;
}

inline int qry(int x1, int x2, int y1, int y2){
	return s[id(x2 + 1, y2 + 1)] + s[id(x1, y1)] - s[id(x2 + 1, y1)] - s[id(x1, y2 + 1)];
}


struct PartialSum2D{
	vector<vector<short>> a, ps;
	PartialSum2D() = default;
	PartialSum2D(int n, int m){
		a = ps = vector<vector<short>>(n + 1, vector<short>(m + 1));
	}
	void upd(int x1, int x2, int y1, int y2, int v){
		a[x2 + 1][y2 + 1] += v;
		a[x1][y2 + 1] -= v;
		a[x2 + 1][y1] -= v;
		a[x1][y1] += v;
	}
	void run(int n){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + a[i - 1][j - 1];
			}
		}
	}
	int qry(int x, int y){
		return ps[x + 1][y + 1];
	}
} ps[SQ][SQ];

int g(int l, int r){
	ps[l][r].run(w);
	int ans = 0;
	for(int i = 0; i < w; i++){
		for(int j = i; j < w; j++){
			ans += ps[l][r].qry(i, j) == (r - l + 1) * (j - i + 1) - 1;
		}
	}
	return ans;
}

int32_t main(){
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
	
	cin >> h >> w;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			cin >> a[id(i, j)];
		}
	}
	if(h > w){
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				b[id2(i, j)] = a[id(i, j)];
			}
		}
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				a[id2(i, j)] = b[id2(i, j)];
			}
		}
		swap(w, h);
	}
	{
		set<int> S; map<int, int> M;
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				S.insert(a[id(i, j)]);
			}
		}
		int idx = 0;
		for(auto j : S){
			M[j] = idx++;
		}
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				a[id(i, j)] = M[a[id(i, j)]];
			}
		}
	}
	
	for(int x1 = 0; x1 < h; x1++){
		for(int x2 = x1; x2 < h; x2++){
			ps[x1][x2] = PartialSum2D(w, w);
		}
	}
	int ans = 0;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w - 1; j++){
			int v1 = a[id(i, j)], v2 = a[id(i, j + 1)];
			if(v1 > v2) swap(v1, v2);
			for(int x = 0; x < h; x++){
				for(int y = 0; y < w; y++){
					f[id(x, y)] = a[id(x, y)] > v1 && a[id(x, y)] < v2;
				}
			}
			for(int x = 0; x < h; x++){
				for(int y = 0; y < w; y++){
					s[id(x + 1, y + 1)] = s[id(x + 1, y)] + s[id(x, y + 1)] - s[id(x, y)] + f[id(x, y)];
				}
			}
			int x1 = i, x2 = i, y1 = j, y2 = j + 1;
			for(int x3 = 0; x3 <= x1; x3++){
				int y3 = 0, y4 = w - 1;
				for(int x4 = x2; x4 < h; x4++){
					if(qry(x3, x4, y1, y2)) continue;
					while(qry(x3, x4, y3, y1)) y3++;
					while(qry(x3, x4, y2, y4)) y4--;
					ps[x3][x4].upd(y3, y1, y2, y4, 1);
				}
			}
		}
	}

	for(int i = 0; i < h - 1; i++){
		for(int j = 0; j < w; j++){
			int v1 = a[id(i, j)], v2 = a[id(i + 1, j)];
			if(v1 > v2) swap(v1, v2);
			for(int x = 0; x < h; x++){
				for(int y = 0; y < w; y++){
					f[id(x, y)] = a[id(x, y)] > v1 && a[id(x, y)] < v2;
				}
			}
			for(int x = 0; x < h; x++){
				for(int y = 0; y < w; y++){
					s[id(x + 1, y + 1)] = s[id(x + 1, y)] + s[id(x, y + 1)] - s[id(x, y)] + f[id(x, y)];
				}
			}
			int x1 = i, x2 = i + 1, y1 = j, y2 = j;
			for(int x3 = 0; x3 <= x1; x3++){
				int y3 = 0, y4 = w - 1;
				for(int x4 = x2; x4 < h; x4++){
					if(qry(x3, x4, y1, y2)) continue;
					while(qry(x3, x4, y3, y1)) y3++;
					while(qry(x3, x4, y2, y4)) y4--;
					ps[x3][x4].upd(y3, y1, y2, y4, 1);
				}
			}
		}
	}
	for(int x1 = 0; x1 < h; x1++){
		for(int x2 = x1; x2 < h; x2++){
			ans += g(x1, x2);
		}
	}
	cout << ans << endl;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Runtime error 403 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3032 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 12 ms 11988 KB Output is correct
8 Correct 13 ms 12040 KB Output is correct
9 Correct 17 ms 9428 KB Output is correct
10 Correct 23 ms 9392 KB Output is correct
11 Correct 12 ms 9812 KB Output is correct
12 Correct 14 ms 9840 KB Output is correct
13 Correct 28 ms 9812 KB Output is correct
14 Correct 11 ms 6604 KB Output is correct
15 Correct 19 ms 9300 KB Output is correct
16 Correct 19 ms 9388 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3032 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 12 ms 11988 KB Output is correct
8 Correct 13 ms 12040 KB Output is correct
9 Correct 17 ms 9428 KB Output is correct
10 Correct 23 ms 9392 KB Output is correct
11 Correct 12 ms 9812 KB Output is correct
12 Correct 14 ms 9840 KB Output is correct
13 Correct 28 ms 9812 KB Output is correct
14 Correct 11 ms 6604 KB Output is correct
15 Correct 19 ms 9300 KB Output is correct
16 Correct 19 ms 9388 KB Output is correct
17 Correct 191 ms 195532 KB Output is correct
18 Correct 268 ms 114888 KB Output is correct
19 Correct 220 ms 110796 KB Output is correct
20 Correct 1172 ms 122016 KB Output is correct
21 Correct 755 ms 117800 KB Output is correct
22 Correct 798 ms 117880 KB Output is correct
23 Correct 799 ms 113688 KB Output is correct
24 Correct 568 ms 94740 KB Output is correct
25 Correct 759 ms 120132 KB Output is correct
26 Correct 779 ms 126576 KB Output is correct
27 Correct 392 ms 120132 KB Output is correct
28 Correct 428 ms 126596 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3032 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 12 ms 11988 KB Output is correct
8 Correct 13 ms 12040 KB Output is correct
9 Correct 17 ms 9428 KB Output is correct
10 Correct 23 ms 9392 KB Output is correct
11 Correct 12 ms 9812 KB Output is correct
12 Correct 14 ms 9840 KB Output is correct
13 Correct 28 ms 9812 KB Output is correct
14 Correct 11 ms 6604 KB Output is correct
15 Correct 19 ms 9300 KB Output is correct
16 Correct 19 ms 9388 KB Output is correct
17 Correct 191 ms 195532 KB Output is correct
18 Correct 268 ms 114888 KB Output is correct
19 Correct 220 ms 110796 KB Output is correct
20 Correct 1172 ms 122016 KB Output is correct
21 Correct 755 ms 117800 KB Output is correct
22 Correct 798 ms 117880 KB Output is correct
23 Correct 799 ms 113688 KB Output is correct
24 Correct 568 ms 94740 KB Output is correct
25 Correct 759 ms 120132 KB Output is correct
26 Correct 779 ms 126576 KB Output is correct
27 Correct 392 ms 120132 KB Output is correct
28 Correct 428 ms 126596 KB Output is correct
29 Runtime error 411 ms 1048576 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -