oj.uz

Submission #624836

# Submission time Handle Problem Language Result Execution time Memory
624836 2022-08-08T20:52:22 Z QwertyPi Sandcastle 2 (JOI22_ho_t5) C++14
71 / 100
 5000 ms 931980 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 PartialSum2D{
	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++){
				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--;
					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++){
				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--;
					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:130:29: warning: narrowing conversion of 'y3' from 'int' to 'short int' [-Wnarrowing]
  130 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                             ^~
Main.cpp:130:33: warning: narrowing conversion of 'y1' from 'int' to 'short int' [-Wnarrowing]
  130 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                 ^~
Main.cpp:130:37: warning: narrowing conversion of 'y2' from 'int' to 'short int' [-Wnarrowing]
  130 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                     ^~
Main.cpp:130:41: warning: narrowing conversion of 'y4' from 'int' to 'short int' [-Wnarrowing]
  130 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                         ^~
Main.cpp:157:29: warning: narrowing conversion of 'y3' from 'int' to 'short int' [-Wnarrowing]
  157 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                             ^~
Main.cpp:157:33: warning: narrowing conversion of 'y1' from 'int' to 'short int' [-Wnarrowing]
  157 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                 ^~
Main.cpp:157:37: warning: narrowing conversion of 'y2' from 'int' to 'short int' [-Wnarrowing]
  157 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                     ^~
Main.cpp:157:41: warning: narrowing conversion of 'y4' from 'int' to 'short int' [-Wnarrowing]
  157 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                         ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1664 KB Output is correct
2 Execution timed out 5139 ms 931980 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 1748 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 2 ms 1748 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 1 ms 1748 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 2 ms 1748 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 23 ms 22740 KB Output is correct
8 Correct 29 ms 22720 KB Output is correct
9 Correct 20 ms 2772 KB Output is correct
10 Correct 28 ms 7500 KB Output is correct
11 Correct 18 ms 10140 KB Output is correct
12 Correct 20 ms 10052 KB Output is correct
13 Correct 30 ms 7192 KB Output is correct
14 Correct 15 ms 4564 KB Output is correct
15 Correct 23 ms 5332 KB Output is correct
16 Correct 21 ms 3492 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 1 ms 1748 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 2 ms 1748 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 23 ms 22740 KB Output is correct
8 Correct 29 ms 22720 KB Output is correct
9 Correct 20 ms 2772 KB Output is correct
10 Correct 28 ms 7500 KB Output is correct
11 Correct 18 ms 10140 KB Output is correct
12 Correct 20 ms 10052 KB Output is correct
13 Correct 30 ms 7192 KB Output is correct
14 Correct 15 ms 4564 KB Output is correct
15 Correct 23 ms 5332 KB Output is correct
16 Correct 21 ms 3492 KB Output is correct
17 Correct 383 ms 250684 KB Output is correct
18 Correct 340 ms 8656 KB Output is correct
19 Correct 346 ms 9032 KB Output is correct
20 Correct 747 ms 151916 KB Output is correct
21 Correct 541 ms 82500 KB Output is correct
22 Correct 603 ms 104972 KB Output is correct
23 Correct 574 ms 100440 KB Output is correct
24 Correct 400 ms 57848 KB Output is correct
25 Correct 527 ms 75852 KB Output is correct
26 Correct 538 ms 83872 KB Output is correct
27 Correct 403 ms 22732 KB Output is correct
28 Correct 426 ms 25564 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 1 ms 1748 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 2 ms 1748 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 23 ms 22740 KB Output is correct
8 Correct 29 ms 22720 KB Output is correct
9 Correct 20 ms 2772 KB Output is correct
10 Correct 28 ms 7500 KB Output is correct
11 Correct 18 ms 10140 KB Output is correct
12 Correct 20 ms 10052 KB Output is correct
13 Correct 30 ms 7192 KB Output is correct
14 Correct 15 ms 4564 KB Output is correct
15 Correct 23 ms 5332 KB Output is correct
16 Correct 21 ms 3492 KB Output is correct
17 Correct 383 ms 250684 KB Output is correct
18 Correct 340 ms 8656 KB Output is correct
19 Correct 346 ms 9032 KB Output is correct
20 Correct 747 ms 151916 KB Output is correct
21 Correct 541 ms 82500 KB Output is correct
22 Correct 603 ms 104972 KB Output is correct
23 Correct 574 ms 100440 KB Output is correct
24 Correct 400 ms 57848 KB Output is correct
25 Correct 527 ms 75852 KB Output is correct
26 Correct 538 ms 83872 KB Output is correct
27 Correct 403 ms 22732 KB Output is correct
28 Correct 426 ms 25564 KB Output is correct
29 Execution timed out 5149 ms 923852 KB Time limit exceeded
30 Halted 0 ms 0 KB -