oj.uz

Submission #260747

# Submission time Handle Problem Language Result Execution time Memory
260747 2020-08-10T20:15:10 Z idk321 Rectangles (IOI19_rect) Java 11
15 / 100
 5000 ms 1048584 KB 
import java.util.Arrays;

class rect {
	boolean[][] visited;

	public long count_rectangles(int[][] a) {
		int n = a.length;
		int m = a[0].length;

		if (n <= 2 || m <= 2) return 0;

		boolean allZeroAndOne = true;
		for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (a[i][j] != 0 && a[i][j] != 1) allZeroAndOne = false;

		if (n <= 3) {
			int currLength = 0;
			int goodStarts = 0;
			long res = 0;
			for (int i = 1; i < m - 1; i++) {
				int h = a[1][i];
				if (a[0][i] <= h || a[2][i] <= h) {
					goodStarts = 0;
				} else {
					if (a[1][i - 1] > h) goodStarts++;
					if (a[1][i + 1] > h) res += goodStarts;
				}
			}

			return res;
		/*} else if (allZeroAndOne) {
			visited = new boolean[n][m];
			Arrays.fill(visited[0], true);
			Arrays.fill(visited[n - 1], true);
			for (int i = 0; i < n; i++) {
				visited[i][0] = true;
				visited[i][m - 1] = true;
			}
			for (int i = 1; i < n - 1; i++) {
				for (int j = 1; j < m - 1; j++) {

				}
			} */
		} else {
			int[][][] maxRight = new int[n][m][m];
			for (int i = 1; i < n - 1; i++) {
				for (int j = 1; j < m - 1; j++) {
					for (int k = j; k < m - 1; k++) {
						if (j == k) {
							maxRight[i][j][k] = a[i][j];
						} else {
							maxRight[i][j][k] = Math.max(a[i][k], maxRight[i][j][k - 1]);
						}
					}
				}
			}
			int[][][] maxDown = new int[m][n][n];
			for (int j = 1; j < m - 1; j++) {
				for (int i = 1; i < n - 1; i++) {
					for (int k = i; k < n - 1; k++) {
						if (i == k) {
							maxDown[j][i][k] = a[i][j];
						} else {
							maxDown[j][i][k] = Math.max(a[k][j], maxDown[j][i][k - 1]);
						}
					}
				}
			}

			boolean[][][][] okJ = new boolean[n][n][m][m];
			for (int i = 1; i < n - 1; i++) {
				for (int k = i; k < n - 1; k++) {
					for (int j = 1;  j < m - 1; j++) {
						for (int l = j; l < m - 1; l++) {
							okJ[i][k][j][l] = maxRight[k][j][l] < a[k][l + 1] && maxRight[k][j][l] < a[k][j - 1];
							if (k != i) {
								okJ[i][k][j][l] = okJ[i][k][j][l] && okJ[i][k - 1][j][l];
							}
						}
					}
				}
			}
			boolean[][][][] okI = new boolean[n][n][m][m];
			for (int i = 1; i < n - 1; i++) {
				for (int k = i; k < n - 1; k++) {
					for (int j = 1;  j < m - 1; j++) {
						for (int l = j; l < m - 1; l++) {
							okI[i][k][j][l] = maxDown[l][i][k] < a[i - 1][l] && maxDown[l][i][k] < a[k + 1][l];
							if (j != l) {
								okI[i][k][j][l] = okI[i][k][j][l] && okI[i][k][j][l - 1];
							}
						}
					}
				}
			}


			long rect = 0;
			for (int i = 1; i < n - 1; i++) {
				for (int j = 1; j < m - 1; j++) {
					for (int k = i; k < n - 1; k++) {
						if (a[k][j - 1] <= a[k][j]) break;
						for (int l = j; l < m - 1; l++) {
							if (maxDown[l][i][k] >= a[k + 1][l]) break;
							if (maxDown[l][i][k] >= a[i - 1][l]) break;


 							if (okI[i][k][j][l] && okJ[i][k][j][l]) {
								rect++;
								//System.out.println(i + " " + j + " " + k + " " + l);
							}
						}
					}
				}
			}
			//System.out.println(Arrays.deepToString(maxDown));
			//System.out.println(Arrays.deepToString(rightOk));
			//System.out.println(maxDown[1][1][1]);

			return rect;
		}
	}

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 10104 KB Output is correct
2 Correct 116 ms 14588 KB Output is correct
3 Correct 115 ms 14456 KB Output is correct
4 Correct 116 ms 14508 KB Output is correct
5 Correct 112 ms 14456 KB Output is correct
6 Correct 122 ms 14580 KB Output is correct
7 Correct 97 ms 11880 KB Output is correct
8 Correct 92 ms 10884 KB Output is correct
9 Correct 117 ms 14640 KB Output is correct
10 Correct 113 ms 14328 KB Output is correct
11 Correct 128 ms 14700 KB Output is correct
12 Correct 118 ms 14576 KB Output is correct
13 Correct 79 ms 10216 KB Output is correct
14 Correct 87 ms 10208 KB Output is correct
15 Correct 77 ms 10356 KB Output is correct
16 Correct 79 ms 10124 KB Output is correct
17 Correct 78 ms 10232 KB Output is correct
18 Correct 77 ms 10088 KB Output is correct
19 Correct 125 ms 14608 KB Output is correct
20 Correct 98 ms 12280 KB Output is correct
21 Correct 76 ms 10232 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 10104 KB Output is correct
2 Correct 116 ms 14588 KB Output is correct
3 Correct 115 ms 14456 KB Output is correct
4 Correct 116 ms 14508 KB Output is correct
5 Correct 112 ms 14456 KB Output is correct
6 Correct 122 ms 14580 KB Output is correct
7 Correct 97 ms 11880 KB Output is correct
8 Correct 92 ms 10884 KB Output is correct
9 Correct 117 ms 14640 KB Output is correct
10 Correct 113 ms 14328 KB Output is correct
11 Correct 128 ms 14700 KB Output is correct
12 Correct 118 ms 14576 KB Output is correct
13 Correct 79 ms 10216 KB Output is correct
14 Correct 87 ms 10208 KB Output is correct
15 Correct 77 ms 10356 KB Output is correct
16 Correct 79 ms 10124 KB Output is correct
17 Correct 1296 ms 128380 KB Output is correct
18 Correct 1453 ms 128588 KB Output is correct
19 Correct 1386 ms 127564 KB Output is correct
20 Correct 1370 ms 128128 KB Output is correct
21 Correct 1387 ms 128324 KB Output is correct
22 Correct 1263 ms 127884 KB Output is correct
23 Correct 1433 ms 128820 KB Output is correct
24 Correct 353 ms 47896 KB Output is correct
25 Correct 78 ms 10232 KB Output is correct
26 Correct 77 ms 10088 KB Output is correct
27 Correct 125 ms 14608 KB Output is correct
28 Correct 98 ms 12280 KB Output is correct
29 Correct 76 ms 10232 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 10104 KB Output is correct
2 Correct 116 ms 14588 KB Output is correct
3 Correct 115 ms 14456 KB Output is correct
4 Correct 116 ms 14508 KB Output is correct
5 Correct 112 ms 14456 KB Output is correct
6 Correct 122 ms 14580 KB Output is correct
7 Correct 97 ms 11880 KB Output is correct
8 Correct 92 ms 10884 KB Output is correct
9 Correct 117 ms 14640 KB Output is correct
10 Correct 113 ms 14328 KB Output is correct
11 Correct 128 ms 14700 KB Output is correct
12 Correct 118 ms 14576 KB Output is correct
13 Correct 79 ms 10216 KB Output is correct
14 Correct 87 ms 10208 KB Output is correct
15 Correct 77 ms 10356 KB Output is correct
16 Correct 79 ms 10124 KB Output is correct
17 Correct 1296 ms 128380 KB Output is correct
18 Correct 1453 ms 128588 KB Output is correct
19 Correct 1386 ms 127564 KB Output is correct
20 Correct 1370 ms 128128 KB Output is correct
21 Correct 1387 ms 128324 KB Output is correct
22 Correct 1263 ms 127884 KB Output is correct
23 Correct 1433 ms 128820 KB Output is correct
24 Correct 353 ms 47896 KB Output is correct
25 Execution timed out 5219 ms 1029220 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 10104 KB Output is correct
2 Correct 116 ms 14588 KB Output is correct
3 Correct 115 ms 14456 KB Output is correct
4 Correct 116 ms 14508 KB Output is correct
5 Correct 112 ms 14456 KB Output is correct
6 Correct 122 ms 14580 KB Output is correct
7 Correct 97 ms 11880 KB Output is correct
8 Correct 92 ms 10884 KB Output is correct
9 Correct 117 ms 14640 KB Output is correct
10 Correct 113 ms 14328 KB Output is correct
11 Correct 128 ms 14700 KB Output is correct
12 Correct 118 ms 14576 KB Output is correct
13 Correct 79 ms 10216 KB Output is correct
14 Correct 87 ms 10208 KB Output is correct
15 Correct 77 ms 10356 KB Output is correct
16 Correct 79 ms 10124 KB Output is correct
17 Correct 1296 ms 128380 KB Output is correct
18 Correct 1453 ms 128588 KB Output is correct
19 Correct 1386 ms 127564 KB Output is correct
20 Correct 1370 ms 128128 KB Output is correct
21 Correct 1387 ms 128324 KB Output is correct
22 Correct 1263 ms 127884 KB Output is correct
23 Correct 1433 ms 128820 KB Output is correct
24 Correct 353 ms 47896 KB Output is correct
25 Execution timed out 5219 ms 1029220 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 10680 KB Output is correct
2 Correct 91 ms 10484 KB Output is correct
3 Correct 94 ms 10748 KB Output is correct
4 Correct 79 ms 10088 KB Output is correct
5 Incorrect 101 ms 10680 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 10236 KB Output is correct
2 Runtime error 2410 ms 1048584 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 10104 KB Output is correct
2 Correct 116 ms 14588 KB Output is correct
3 Correct 115 ms 14456 KB Output is correct
4 Correct 116 ms 14508 KB Output is correct
5 Correct 112 ms 14456 KB Output is correct
6 Correct 122 ms 14580 KB Output is correct
7 Correct 97 ms 11880 KB Output is correct
8 Correct 92 ms 10884 KB Output is correct
9 Correct 117 ms 14640 KB Output is correct
10 Correct 113 ms 14328 KB Output is correct
11 Correct 128 ms 14700 KB Output is correct
12 Correct 118 ms 14576 KB Output is correct
13 Correct 79 ms 10216 KB Output is correct
14 Correct 87 ms 10208 KB Output is correct
15 Correct 77 ms 10356 KB Output is correct
16 Correct 79 ms 10124 KB Output is correct
17 Correct 1296 ms 128380 KB Output is correct
18 Correct 1453 ms 128588 KB Output is correct
19 Correct 1386 ms 127564 KB Output is correct
20 Correct 1370 ms 128128 KB Output is correct
21 Correct 1387 ms 128324 KB Output is correct
22 Correct 1263 ms 127884 KB Output is correct
23 Correct 1433 ms 128820 KB Output is correct
24 Correct 353 ms 47896 KB Output is correct
25 Execution timed out 5219 ms 1029220 KB Time limit exceeded
26 Halted 0 ms 0 KB -