oj.uz

Submission #624819

# Submission time Handle Problem Language Result Execution time Memory
624819 2022-08-08T19:22:41 Z QwertyPi Sandcastle 2 (JOI22_ho_t5) C++14
15 / 100
 5000 ms 50340 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[1501][1501];
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 5028 ms 8336 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 2 ms 1800 KB Output is correct
3 Correct 2 ms 1788 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 2 ms 1796 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 527 ms 19520 KB Output is correct
8 Correct 18 ms 19540 KB Output is correct
9 Correct 27 ms 4748 KB Output is correct
10 Correct 164 ms 21708 KB Output is correct
11 Correct 318 ms 9320 KB Output is correct
12 Correct 231 ms 9428 KB Output is correct
13 Correct 163 ms 20860 KB Output is correct
14 Correct 66 ms 11756 KB Output is correct
15 Correct 135 ms 13444 KB Output is correct
16 Correct 31 ms 7036 KB Output is correct

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 2 ms 1800 KB Output is correct
3 Correct 2 ms 1788 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 2 ms 1796 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 527 ms 19520 KB Output is correct
8 Correct 18 ms 19540 KB Output is correct
9 Correct 27 ms 4748 KB Output is correct
10 Correct 164 ms 21708 KB Output is correct
11 Correct 318 ms 9320 KB Output is correct
12 Correct 231 ms 9428 KB Output is correct
13 Correct 163 ms 20860 KB Output is correct
14 Correct 66 ms 11756 KB Output is correct
15 Correct 135 ms 13444 KB Output is correct
16 Correct 31 ms 7036 KB Output is correct
17 Runtime error 155 ms 50340 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 2 ms 1800 KB Output is correct
3 Correct 2 ms 1788 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 2 ms 1796 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 527 ms 19520 KB Output is correct
8 Correct 18 ms 19540 KB Output is correct
9 Correct 27 ms 4748 KB Output is correct
10 Correct 164 ms 21708 KB Output is correct
11 Correct 318 ms 9320 KB Output is correct
12 Correct 231 ms 9428 KB Output is correct
13 Correct 163 ms 20860 KB Output is correct
14 Correct 66 ms 11756 KB Output is correct
15 Correct 135 ms 13444 KB Output is correct
16 Correct 31 ms 7036 KB Output is correct
17 Runtime error 155 ms 50340 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -