oj.uz

Submission #624821

# Submission time Handle Problem Language Result Execution time Memory
624821 2022-08-08T19:23:22 Z QwertyPi Sandcastle 2 (JOI22_ho_t5) C++14
15 / 100
 5000 ms 434044 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

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

struct Range{
	int x1, x2, y1, y2; // 1D; [x1, x2] x [y1, y2]
};

vector<Range> vrs[SQ][SQ];
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)];
}

int k[7001][7001];
int g(vector<Range> vr, int h){
	for(int i = 0; i < w; i++){
		for(int j = 0; j < w; j++){
			k[i][j] = 0;
		}
	}
	for(auto r : vr){
		for(int a = r.x1; a <= r.x2; a++){
			for(int b = r.y1; b <= r.y2; b++){
				k[a][b]++;
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < w; i++){
		for(int j = i; j < w; j++){
			ans += k[i][j] == h * (j - i + 1) - 1;
		}
	}
	return ans;
}

int32_t main(){
	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)]];
			}
		}
	}
	
	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++){
				for(int x4 = x2; x4 < h; x4++){
					if(qry(x3, x4, y1, y2)) continue;
					int y3 = INT32_MAX, y4 = INT32_MIN;
					{
						int l = 0, r = y1;
						while(l != r){
							int mid = (l + r) / 2;
							if(qry(x3, x4, mid, y1)){
								l = mid + 1;
							}else{
								r = mid;
							}
						}
						y3 = l;
					}
					{
						int l = y2, r = w - 1;
						while(l != r){
							int mid = (l + r + 1) / 2;
							if(qry(x3, x4, y2, mid)){
								r = mid - 1;
							}else{
								l = mid;
							}
						}
						y4 = l;
					}
					vrs[x3][x4].push_back({y3, y1, y2, y4});
				}
			}
		}
	}

	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++){
				for(int x4 = x2; x4 < h; x4++){
					if(qry(x3, x4, y1, y2)) continue;
					int y3 = INT32_MAX, y4 = INT32_MIN;
					{
						int l = 0, r = y1;
						while(l != r){
							int mid = (l + r) / 2;
							if(qry(x3, x4, mid, y1)){
								l = mid + 1;
							}else{
								r = mid;
							}
						}
						y3 = l;
					}
					{
						int l = y2, r = w - 1;
						while(l != r){
							int mid = (l + r + 1) / 2;
							if(qry(x3, x4, y2, mid)){
								r = mid - 1;
							}else{
								l = mid;
							}
						}
						y4 = l;
					}
					vrs[x3][x4].push_back({y3, y1, y2, y4});
				}
			}
		}
	}
	for(int x1 = 0; x1 < h; x1++){
		for(int x2 = x1; x2 < h; x2++){
			ans += g(vrs[x1][x2], x2 - x1 + 1);
		}
	}
	cout << ans << endl;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Execution timed out 5069 ms 434044 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1800 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1804 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 2 ms 1800 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1800 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1804 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 2 ms 1800 KB Output is correct
7 Correct 519 ms 25608 KB Output is correct
8 Correct 20 ms 25636 KB Output is correct
9 Correct 21 ms 4728 KB Output is correct
10 Correct 162 ms 21624 KB Output is correct
11 Correct 248 ms 9420 KB Output is correct
12 Correct 244 ms 9480 KB Output is correct
13 Correct 129 ms 20852 KB Output is correct
14 Correct 53 ms 11724 KB Output is correct
15 Correct 118 ms 13444 KB Output is correct
16 Correct 28 ms 6948 KB Output is correct

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1800 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1804 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 2 ms 1800 KB Output is correct
7 Correct 519 ms 25608 KB Output is correct
8 Correct 20 ms 25636 KB Output is correct
9 Correct 21 ms 4728 KB Output is correct
10 Correct 162 ms 21624 KB Output is correct
11 Correct 248 ms 9420 KB Output is correct
12 Correct 244 ms 9480 KB Output is correct
13 Correct 129 ms 20852 KB Output is correct
14 Correct 53 ms 11724 KB Output is correct
15 Correct 118 ms 13444 KB Output is correct
16 Correct 28 ms 6948 KB Output is correct
17 Execution timed out 5087 ms 386276 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1800 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1804 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 2 ms 1800 KB Output is correct
7 Correct 519 ms 25608 KB Output is correct
8 Correct 20 ms 25636 KB Output is correct
9 Correct 21 ms 4728 KB Output is correct
10 Correct 162 ms 21624 KB Output is correct
11 Correct 248 ms 9420 KB Output is correct
12 Correct 244 ms 9480 KB Output is correct
13 Correct 129 ms 20852 KB Output is correct
14 Correct 53 ms 11724 KB Output is correct
15 Correct 118 ms 13444 KB Output is correct
16 Correct 28 ms 6948 KB Output is correct
17 Execution timed out 5087 ms 386276 KB Time limit exceeded
18 Halted 0 ms 0 KB -