oj.uz

Submission #624832

# Submission time Handle Problem Language Result Execution time Memory
624832 2022-08-08T20:27:15 Z QwertyPi Sandcastle 2 (JOI22_ho_t5) C++14
71 / 100
 5000 ms 925432 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 1620 KB Output is correct
2 Execution timed out 5108 ms 925432 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 1876 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 1 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 1876 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 1 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 30 ms 22832 KB Output is correct
9 Correct 20 ms 2820 KB Output is correct
10 Correct 29 ms 7500 KB Output is correct
11 Correct 18 ms 10068 KB Output is correct
12 Correct 19 ms 10068 KB Output is correct
13 Correct 28 ms 7236 KB Output is correct
14 Correct 14 ms 4664 KB Output is correct
15 Correct 25 ms 5272 KB Output is correct
16 Correct 29 ms 3504 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 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 1 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 30 ms 22832 KB Output is correct
9 Correct 20 ms 2820 KB Output is correct
10 Correct 29 ms 7500 KB Output is correct
11 Correct 18 ms 10068 KB Output is correct
12 Correct 19 ms 10068 KB Output is correct
13 Correct 28 ms 7236 KB Output is correct
14 Correct 14 ms 4664 KB Output is correct
15 Correct 25 ms 5272 KB Output is correct
16 Correct 29 ms 3504 KB Output is correct
17 Correct 375 ms 250684 KB Output is correct
18 Correct 342 ms 8716 KB Output is correct
19 Correct 345 ms 9040 KB Output is correct
20 Correct 775 ms 151900 KB Output is correct
21 Correct 536 ms 82640 KB Output is correct
22 Correct 655 ms 105104 KB Output is correct
23 Correct 591 ms 100436 KB Output is correct
24 Correct 387 ms 57884 KB Output is correct
25 Correct 518 ms 76024 KB Output is correct
26 Correct 548 ms 83832 KB Output is correct
27 Correct 402 ms 22840 KB Output is correct
28 Correct 437 ms 25620 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 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 1 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 30 ms 22832 KB Output is correct
9 Correct 20 ms 2820 KB Output is correct
10 Correct 29 ms 7500 KB Output is correct
11 Correct 18 ms 10068 KB Output is correct
12 Correct 19 ms 10068 KB Output is correct
13 Correct 28 ms 7236 KB Output is correct
14 Correct 14 ms 4664 KB Output is correct
15 Correct 25 ms 5272 KB Output is correct
16 Correct 29 ms 3504 KB Output is correct
17 Correct 375 ms 250684 KB Output is correct
18 Correct 342 ms 8716 KB Output is correct
19 Correct 345 ms 9040 KB Output is correct
20 Correct 775 ms 151900 KB Output is correct
21 Correct 536 ms 82640 KB Output is correct
22 Correct 655 ms 105104 KB Output is correct
23 Correct 591 ms 100436 KB Output is correct
24 Correct 387 ms 57884 KB Output is correct
25 Correct 518 ms 76024 KB Output is correct
26 Correct 548 ms 83832 KB Output is correct
27 Correct 402 ms 22840 KB Output is correct
28 Correct 437 ms 25620 KB Output is correct
29 Execution timed out 5121 ms 833052 KB Time limit exceeded
30 Halted 0 ms 0 KB -