Submission #624831

#	Time	Username	Problem	Language	Result	Execution time	Memory
624831		QwertyPi	Sandcastle 2 (JOI22_ho_t5)	C++14	71 / 100	5135 ms	856724 KiB

Main

#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 (stderr)

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
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 56 / 56
• Subtask 5: 0 / 20