oj.uz

Submission #827857

# Submission time Handle Problem Language Result Execution time Memory
827857 2023-08-16T20:28:53 Z OrazB Rectangles (IOI19_rect) C++14
38 / 100
 5000 ms 131416 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second

const int N = 205;
int mxc[N][N][N]; 
int mxr[N][N][N];
int row[N][N][N], col[N][N][N];

ll count_rectangles(vector<vector<int>> a){
	
	int ans = 0, sub6 = 0;
	int n = a.size(), m = a[0].size();
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++) sub6 |= (a[i][j]>1);
	}

	if (n < 3) return 0;

	if (n == 3){
		vector<vector<vector<int>>> mx(n, vector<vector<int>>(m, vector<int>(m,0)));
		vector<int> P(m, 0);
		
		for (int i = 0; i < n; i++){
			for (int x = 0; x < m; x++){
				for (int j = 0; j < m-x; j++){
					if (!x) 
						mx[i][j][j] = a[i][j];
					else
						mx[i][j][j+x] = max(mx[i][j][j+x-1], a[i][j+x]);
				}
			}
		}

		for (int i = 0; i < m; i++){
			if (a[0][i] <= a[1][i] or a[2][i] <= a[1][i]) P[i] = 1;
			if (i) P[i] += P[i-1];
		}

		int ans = 0;
		for (int i = 0; i < m; i++){
			for (int j = i+2; j < m; j++){
				if (a[1][i] > mx[1][i+1][j-1] and a[1][j] > mx[1][i+1][j-1] and !(P[j-1]-P[i])) ans++;
			}
		} 
		
		return ans;
	}

	if (!sub6){
		vector<vector<int>> rw(m, vector<int>(n,0));
		vector<vector<int>> c(n, vector<int>(m,0));
		vector<vector<int>> mat(n, vector<int>(m,0));
		for (int i = 0; i < n; i++){
			for (int j = 0; j < m; j++){
				mat[i][j] = a[i][j];
				if (j) mat[i][j] += mat[i][j-1];
			}
		}
		for (int i = 1; i < n; i++){
			for (int j = 0; j < m; j++){
				mat[i][j] += mat[i-1][j];
			}
		}
		for (int i = 0; i < n; i++){
			for (int j = 0; j < m; j++){
				c[i][j] = a[i][j];
				if (j) c[i][j] += c[i][j-1];
			}
		}
		for (int i = 0; i < m; i++){
			for (int j = 0; j < n; j++){
				rw[i][j] = a[j][i];
				if (j) rw[i][j] += rw[i][j-1];
			}
		}
		for (int i = 1; i < n; i++){
			for (int j = 0; j < m; j++){
				if (a[i][j+1] == 1 or a[i][j] == 0) continue;
				int l = j+2, r = m-1, pos = -1;
				while(l <= r){
					int md = (l+r)>>1;
					if (c[i][md]-c[i][j] > 1) r = md - 1;
					else if (c[i][md]-c[i][j] == 1){pos=md;r=md-1;}
					else l = md + 1;
				}
				if (pos == -1) continue;
				if (c[i-1][pos-1]-c[i-1][j] != pos-j-1) continue;
				l = i+1, r = n-1;
				int pos1 = -1;
				while(l <= r){
					int md = (l+r)>>1;
					if (rw[j+1][md]-rw[j+1][i] > 1) r = md - 1;
					else if (rw[j+1][md]-rw[j+1][i] == 1){pos1=md;r=md-1;}
					else l = md + 1;
				}
				if (pos1 == -1) continue;
				if (c[pos1][pos-1]-c[pos1][j] != pos-j-1) continue;
				pos1--;
				if (rw[j][pos1]-rw[j][i] != pos1-i or rw[pos][pos1]-rw[pos][i] != pos1-i) continue;
				if (mat[pos1][pos-1]-mat[pos1][j]-mat[i-1][pos-1]+mat[i-1][j]) continue;
				ans++;
			}
		}
		return ans;
	}

	for (int i = 0; i < n; i++){
		for (int x = 0; x < m; x++){
			for (int j = 0; j < m-x; j++){
				
				if (!x) 
					mxc[i][j][j] = a[i][j];
				else
					mxc[i][j][j+x] = max(mxc[i][j][j+x-1], a[i][j+x]);
			}
		}
	}

	for (int i = 0; i < m; i++){
		for (int x = 0; x < n; x++){
			for (int j = 0; j < n-x; j++){
 
				if (!x) 
					mxr[i][j][j] = a[j][i];
				else
					mxr[i][j][j+x] = max(mxr[i][j][j+x-1], a[j+x][i]);
			}
		}
	}

	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			for (int k = j+2; k < m; k++){
				row[i][j][k] = (a[i][j] > mxc[i][j+1][k-1] and a[i][k] > mxc[i][j+1][k-1]);
				if (i) row[i][j][k] += row[i-1][j][k];
			}
		}
	}
	for (int i = 0; i < m; i++){
		for (int j = 0; j < n; j++){
			for (int k = j+2; k < n; k++){
				col[i][j][k] = (a[j][i] > mxr[i][j+1][k-1] and a[k][i] > mxr[i][j+1][k-1]);
				if (i) col[i][j][k] += col[i-1][j][k];
			}
		}
	}
	for (int x = 2; x < n; x++){
		for (int y = 2; y < m; y++){
			for (int i = 0; i < n; i++){
				for (int j = 0; j < m; j++){
					if (row[i+x-1][j][j+y]-row[i][j][j+y] != x-1) continue;
					if (col[j+y-1][i][i+x]-col[j][i][i+x] != y-1) continue;
					ans++;
				}
			}
		}
	}
	return ans;
}

// int main ()
// {
// 	ios::sync_with_stdio(false);
// 	cin.tie(0);
// 	int n, m;
// 	cin >> n >> m;
// 	vector<vector<int>> a(n, vector<int>(m));
// 	for (int i = 0; i < n; i++){
// 		for (int j = 0; j < m; j++) cin >> a[i][j];
// 	}
// 	cout << count_rectangles(a);
// }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 3 ms 3540 KB Output is correct
3 Correct 3 ms 3540 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 3 ms 3540 KB Output is correct
7 Correct 1 ms 1732 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 3 ms 3540 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 3 ms 3540 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 3 ms 3540 KB Output is correct
3 Correct 3 ms 3540 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 3 ms 3540 KB Output is correct
7 Correct 1 ms 1732 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 3 ms 3540 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 3 ms 3540 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 130 ms 21824 KB Output is correct
23 Correct 103 ms 21836 KB Output is correct
24 Correct 103 ms 21748 KB Output is correct
25 Correct 107 ms 21836 KB Output is correct
26 Correct 139 ms 21564 KB Output is correct
27 Correct 108 ms 21588 KB Output is correct
28 Correct 105 ms 21828 KB Output is correct
29 Correct 31 ms 11220 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 3 ms 3540 KB Output is correct
3 Correct 3 ms 3540 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 3 ms 3540 KB Output is correct
7 Correct 1 ms 1732 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 3 ms 3540 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 3 ms 3540 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 130 ms 21824 KB Output is correct
18 Correct 103 ms 21836 KB Output is correct
19 Correct 103 ms 21748 KB Output is correct
20 Correct 107 ms 21836 KB Output is correct
21 Correct 139 ms 21564 KB Output is correct
22 Correct 108 ms 21588 KB Output is correct
23 Correct 105 ms 21828 KB Output is correct
24 Correct 31 ms 11220 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Execution timed out 5077 ms 131416 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 3 ms 3540 KB Output is correct
3 Correct 3 ms 3540 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 3 ms 3540 KB Output is correct
7 Correct 1 ms 1732 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 3 ms 3540 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 3 ms 3540 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 130 ms 21824 KB Output is correct
18 Correct 103 ms 21836 KB Output is correct
19 Correct 103 ms 21748 KB Output is correct
20 Correct 107 ms 21836 KB Output is correct
21 Correct 139 ms 21564 KB Output is correct
22 Correct 108 ms 21588 KB Output is correct
23 Correct 105 ms 21828 KB Output is correct
24 Correct 31 ms 11220 KB Output is correct
25 Execution timed out 5077 ms 131416 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 98516 KB Output is correct
2 Correct 49 ms 71276 KB Output is correct
3 Correct 68 ms 98512 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 70 ms 98508 KB Output is correct
6 Correct 70 ms 98596 KB Output is correct
7 Correct 72 ms 98596 KB Output is correct
8 Correct 72 ms 98516 KB Output is correct
9 Correct 73 ms 98508 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 117 ms 56568 KB Output is correct
8 Correct 266 ms 122472 KB Output is correct
9 Correct 272 ms 123084 KB Output is correct
10 Correct 271 ms 123088 KB Output is correct
11 Correct 74 ms 60812 KB Output is correct
12 Correct 159 ms 115464 KB Output is correct
13 Correct 165 ms 123088 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 3 ms 3540 KB Output is correct
3 Correct 3 ms 3540 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 3 ms 3540 KB Output is correct
7 Correct 1 ms 1732 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 3 ms 3540 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 3 ms 3540 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 130 ms 21824 KB Output is correct
18 Correct 103 ms 21836 KB Output is correct
19 Correct 103 ms 21748 KB Output is correct
20 Correct 107 ms 21836 KB Output is correct
21 Correct 139 ms 21564 KB Output is correct
22 Correct 108 ms 21588 KB Output is correct
23 Correct 105 ms 21828 KB Output is correct
24 Correct 31 ms 11220 KB Output is correct
25 Execution timed out 5077 ms 131416 KB Time limit exceeded
26 Halted 0 ms 0 KB -