oj.uz

Submission #624831

# Submission time Handle Problem Language Result Execution time Memory
624831 2022-08-08T20:20:45 Z QwertyPi Sandcastle 2 (JOI22_ho_t5) C++14
71 / 100
 5000 ms 856724 KB 
#include <bits/stdc++.h>
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;
int id(int i, int j){
	return i * (w + 1) + j;
}
int id2(int i, int j){
	return j * (h + 1) + i;
}

struct Range{
	short 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)];
}


struct PartialSum{
	short a[N][N] = {0}, ps[N][N] = {0};
	void clear(int n){
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= n; j++){
				a[i][j] = ps[i][j] = 0;
			}
		}
	}
	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;

int g(vector<Range> vr, int h){
	ps.clear(w);
	for(auto r : vr){
		ps.upd(r.x1, r.x2, r.y1, r.y2, 1);
	}
	ps.run(w);
	int ans = 0;
	for(int i = 0; i < w; i++){
		for(int j = i; j < w; j++){
			ans += ps.qry(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 = INT16_MAX, y4 = INT16_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 = INT16_MAX, y4 = INT16_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;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:152:29: warning: narrowing conversion of 'y3' from 'int' to 'short int' [-Wnarrowing]
  152 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                             ^~
Main.cpp:152:33: warning: narrowing conversion of 'y1' from 'int' to 'short int' [-Wnarrowing]
  152 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                 ^~
Main.cpp:152:37: warning: narrowing conversion of 'y2' from 'int' to 'short int' [-Wnarrowing]
  152 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                     ^~
Main.cpp:152:41: warning: narrowing conversion of 'y4' from 'int' to 'short int' [-Wnarrowing]
  152 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                         ^~
Main.cpp:201:29: warning: narrowing conversion of 'y3' from 'int' to 'short int' [-Wnarrowing]
  201 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                             ^~
Main.cpp:201:33: warning: narrowing conversion of 'y1' from 'int' to 'short int' [-Wnarrowing]
  201 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                 ^~
Main.cpp:201:37: warning: narrowing conversion of 'y2' from 'int' to 'short int' [-Wnarrowing]
  201 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                     ^~
Main.cpp:201:41: warning: narrowing conversion of 'y4' from 'int' to 'short int' [-Wnarrowing]
  201 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                         ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Execution timed out 5094 ms 507280 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 2 ms 1748 KB Output is correct
3 Correct 1 ms 1756 KB Output is correct
4 Correct 1 ms 1756 KB Output is correct
5 Correct 1 ms 1756 KB Output is correct
6 Correct 1 ms 1748 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 2 ms 1748 KB Output is correct
3 Correct 1 ms 1756 KB Output is correct
4 Correct 1 ms 1756 KB Output is correct
5 Correct 1 ms 1756 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 27 ms 22788 KB Output is correct
8 Correct 25 ms 22752 KB Output is correct
9 Correct 20 ms 2816 KB Output is correct
10 Correct 38 ms 7448 KB Output is correct
11 Correct 19 ms 10136 KB Output is correct
12 Correct 19 ms 10160 KB Output is correct
13 Correct 36 ms 7256 KB Output is correct
14 Correct 19 ms 4648 KB Output is correct
15 Correct 29 ms 5264 KB Output is correct
16 Correct 28 ms 3464 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 1 ms 1756 KB Output is correct
4 Correct 1 ms 1756 KB Output is correct
5 Correct 1 ms 1756 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 27 ms 22788 KB Output is correct
8 Correct 25 ms 22752 KB Output is correct
9 Correct 20 ms 2816 KB Output is correct
10 Correct 38 ms 7448 KB Output is correct
11 Correct 19 ms 10136 KB Output is correct
12 Correct 19 ms 10160 KB Output is correct
13 Correct 36 ms 7256 KB Output is correct
14 Correct 19 ms 4648 KB Output is correct
15 Correct 29 ms 5264 KB Output is correct
16 Correct 28 ms 3464 KB Output is correct
17 Correct 393 ms 250680 KB Output is correct
18 Correct 338 ms 8828 KB Output is correct
19 Correct 297 ms 8924 KB Output is correct
20 Correct 1152 ms 151920 KB Output is correct
21 Correct 781 ms 82660 KB Output is correct
22 Correct 904 ms 105132 KB Output is correct
23 Correct 844 ms 100556 KB Output is correct
24 Correct 568 ms 57836 KB Output is correct
25 Correct 739 ms 76016 KB Output is correct
26 Correct 782 ms 83904 KB Output is correct
27 Correct 429 ms 22860 KB Output is correct
28 Correct 468 ms 25624 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 1 ms 1756 KB Output is correct
4 Correct 1 ms 1756 KB Output is correct
5 Correct 1 ms 1756 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 27 ms 22788 KB Output is correct
8 Correct 25 ms 22752 KB Output is correct
9 Correct 20 ms 2816 KB Output is correct
10 Correct 38 ms 7448 KB Output is correct
11 Correct 19 ms 10136 KB Output is correct
12 Correct 19 ms 10160 KB Output is correct
13 Correct 36 ms 7256 KB Output is correct
14 Correct 19 ms 4648 KB Output is correct
15 Correct 29 ms 5264 KB Output is correct
16 Correct 28 ms 3464 KB Output is correct
17 Correct 393 ms 250680 KB Output is correct
18 Correct 338 ms 8828 KB Output is correct
19 Correct 297 ms 8924 KB Output is correct
20 Correct 1152 ms 151920 KB Output is correct
21 Correct 781 ms 82660 KB Output is correct
22 Correct 904 ms 105132 KB Output is correct
23 Correct 844 ms 100556 KB Output is correct
24 Correct 568 ms 57836 KB Output is correct
25 Correct 739 ms 76016 KB Output is correct
26 Correct 782 ms 83904 KB Output is correct
27 Correct 429 ms 22860 KB Output is correct
28 Correct 468 ms 25624 KB Output is correct
29 Execution timed out 5135 ms 856724 KB Time limit exceeded
30 Halted 0 ms 0 KB -