oj.uz

Submission #143401

# Submission time Handle Problem Language Result Execution time Memory
143401 2019-08-13T23:25:51 Z model_code Rectangles (IOI19_rect) Java 11
100 / 100
 4527 ms 520712 KB 
// correct/rect-mruxim-n2lg.java 🤣🤣🤣
 
import java.util.Arrays;
 
class rect {
	final int maxn = 3000 + 10;
 
	int n, m;
 
	int[][] H;
 
	short[][] L, R, U, D;
	short[][] UL, DL, LU, RU;
 
	long[] v;
	int vs;
 
	private void precalc() {
		L = new short[maxn][maxn];
		R = new short[maxn][maxn];
		U = new short[maxn][maxn];
		D = new short[maxn][maxn];
 
		UL = new short[maxn][maxn];
		DL = new short[maxn][maxn];
		LU = new short[maxn][maxn];
		RU = new short[maxn][maxn];
 
		short[] st = new short[maxn];
 
		for(int i = 0; i < n; i++) {
			int t = 0;
			for(int j = 0; j < m; j++) {
				while(t > 0 && H[i][j] > H[i][st[t-1]]) t--;
				L[i][j] = (t > 0 ? st[t-1] : -1);
				st[t++] = (short)j;
			}
		}
 
		for(int i = 0; i < n; i++) {
			int t = 0;
			for(int j = m; j-- > 0; ) {
				while(t > 0 && H[i][j] > H[i][st[t-1]]) t--;
				R[i][j] = (t > 0 ? st[t-1] : -1);
				st[t++] = (short)j;
			}
		}
 
		for(int j = 0; j < m; j++) {
			int t = 0;
			for(int i = 0; i < n; i++) {
				while(t > 0 && H[i][j] > H[st[t-1]][j]) t--;
				U[i][j] = (t > 0 ? st[t-1] : -1);
				st[t++] = (short)i;
			}
		}
 
		for(int j = 0; j < m; j++) {
			int t = 0;
			for(int i = n; i-- > 0; ) {
				while(t > 0 && H[i][j] > H[st[t-1]][j]) t--;
				D[i][j] = (t > 0 ? st[t-1] : -1);
				st[t++] = (short)i;
			}
		}
 
		for(int j = 0; j < m; j++) for(int i = 0; i < n; i++) {
			if(U[i][j] != -1) {
				if(j > 0 && U[i][j] == U[i][j-1]) UL[i][j] = UL[i][j-1];
				else if(j > 0 && i == D[U[i][j]][j-1]) UL[i][j] = DL[U[i][j]][j-1];
				else UL[i][j] = (short)j;
			}
			if(D[i][j] != -1) {
				if(j > 0 && D[i][j] == D[i][j-1]) DL[i][j] = DL[i][j-1];
				else if(j > 0 && i == U[D[i][j]][j-1]) DL[i][j] = UL[D[i][j]][j-1];
				else DL[i][j] = (short)j;
			}
		}
 
		for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
			if(L[i][j] != -1) {
				if(i > 0 && L[i][j] == L[i-1][j]) LU[i][j] = LU[i-1][j];
				else if(i > 0 && j == R[i-1][L[i][j]]) LU[i][j] = RU[i-1][L[i][j]];
				else LU[i][j] = (short)i;
			}
			if(R[i][j] != -1) {
				if(i > 0 && R[i][j] == R[i-1][j]) RU[i][j] = RU[i-1][j];
				else if(i > 0 && j == L[i-1][R[i][j]]) RU[i][j] = LU[i-1][R[i][j]];
				else RU[i][j] = (short)i;
			}
		}
	}
 
	private void check(int i1, int i2, int j1, int j2) {
		if(i2 < i1 || j2 < j1) return;
		if(!((R[i2][j1-1]-1 == j2 && RU[i2][j1-1] <= i1) || (L[i2][j2+1]+1 == j1 && LU[i2][j2+1] <= i1))) return;
		if(!((D[i1-1][j2]-1 == i2 && DL[i1-1][j2] <= j1) || (U[i2+1][j2]+1 == i1 && UL[i2+1][j2] <= j1))) return;
		v[vs++] = (((long)i1 * maxn + i2) * maxn + j1) * maxn + j2;
	}
 
	public long count_rectangles(int[][] _H) {
		H = _H;
		n = H.length;
		m = H[0].length;
 
		precalc();
 
		v = new long[maxn * maxn * 4];
		vs = 0;
 
		for(int i = 1; i < n-1; i++) for(int j = 1; j < m-1; j++) {
			if(U[i+1][j] != -1 && L[i][j+1] != -1) check(U[i+1][j]+1, i, L[i][j+1]+1, j);
			if(U[i+1][j] != -1 && R[i][j-1] != -1) check(U[i+1][j]+1, i, j, R[i][j-1]-1);
			if(D[i-1][j] != -1 && L[i][j+1] != -1) check(i, D[i-1][j]-1, L[i][j+1]+1, j);
			if(D[i-1][j] != -1 && R[i][j-1] != -1) check(i, D[i-1][j]-1, j, R[i][j-1]-1);
			if(D[i-1][j] != -1 && R[D[i-1][j]-1][j-1] != -1) check(i, D[i-1][j]-1, j, R[D[i-1][j]-1][j-1]-1);
			if(D[i-1][j] != -1 && L[D[i-1][j]-1][j+1] != -1) check(i, D[i-1][j]-1, L[D[i-1][j]-1][j+1]+1, j);
		}
 
		Arrays.sort(v, 0, vs);
		int ans = 0;
		for(int i = 0; i < vs; i++)
			if(i == 0 || v[i] != v[i-1])
				ans++;
		return ans;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 509136 KB Output is correct
2 Correct 645 ms 510092 KB Output is correct
3 Correct 694 ms 510156 KB Output is correct
4 Correct 654 ms 510000 KB Output is correct
5 Correct 635 ms 509260 KB Output is correct
6 Correct 673 ms 509324 KB Output is correct
7 Correct 677 ms 509108 KB Output is correct
8 Correct 669 ms 509140 KB Output is correct
9 Correct 637 ms 509132 KB Output is correct
10 Correct 656 ms 509112 KB Output is correct
11 Correct 651 ms 509020 KB Output is correct
12 Correct 663 ms 509408 KB Output is correct
13 Correct 650 ms 509140 KB Output is correct
14 Correct 655 ms 509048 KB Output is correct
15 Correct 668 ms 509164 KB Output is correct
16 Correct 641 ms 509060 KB Output is correct
17 Correct 627 ms 509096 KB Output is correct
18 Correct 635 ms 509184 KB Output is correct
19 Correct 657 ms 509216 KB Output is correct
20 Correct 679 ms 509144 KB Output is correct
21 Correct 755 ms 508936 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 509136 KB Output is correct
2 Correct 645 ms 510092 KB Output is correct
3 Correct 694 ms 510156 KB Output is correct
4 Correct 654 ms 510000 KB Output is correct
5 Correct 635 ms 509260 KB Output is correct
6 Correct 673 ms 509324 KB Output is correct
7 Correct 677 ms 509108 KB Output is correct
8 Correct 669 ms 509140 KB Output is correct
9 Correct 637 ms 509132 KB Output is correct
10 Correct 656 ms 509112 KB Output is correct
11 Correct 651 ms 509020 KB Output is correct
12 Correct 663 ms 509408 KB Output is correct
13 Correct 650 ms 509140 KB Output is correct
14 Correct 655 ms 509048 KB Output is correct
15 Correct 668 ms 509164 KB Output is correct
16 Correct 641 ms 509060 KB Output is correct
17 Correct 732 ms 510304 KB Output is correct
18 Correct 711 ms 510348 KB Output is correct
19 Correct 699 ms 510412 KB Output is correct
20 Correct 694 ms 510556 KB Output is correct
21 Correct 669 ms 510408 KB Output is correct
22 Correct 708 ms 510468 KB Output is correct
23 Correct 687 ms 510216 KB Output is correct
24 Correct 713 ms 509948 KB Output is correct
25 Correct 627 ms 509096 KB Output is correct
26 Correct 635 ms 509184 KB Output is correct
27 Correct 657 ms 509216 KB Output is correct
28 Correct 679 ms 509144 KB Output is correct
29 Correct 755 ms 508936 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 509136 KB Output is correct
2 Correct 645 ms 510092 KB Output is correct
3 Correct 694 ms 510156 KB Output is correct
4 Correct 654 ms 510000 KB Output is correct
5 Correct 635 ms 509260 KB Output is correct
6 Correct 673 ms 509324 KB Output is correct
7 Correct 677 ms 509108 KB Output is correct
8 Correct 669 ms 509140 KB Output is correct
9 Correct 637 ms 509132 KB Output is correct
10 Correct 656 ms 509112 KB Output is correct
11 Correct 651 ms 509020 KB Output is correct
12 Correct 663 ms 509408 KB Output is correct
13 Correct 650 ms 509140 KB Output is correct
14 Correct 655 ms 509048 KB Output is correct
15 Correct 668 ms 509164 KB Output is correct
16 Correct 641 ms 509060 KB Output is correct
17 Correct 732 ms 510304 KB Output is correct
18 Correct 711 ms 510348 KB Output is correct
19 Correct 699 ms 510412 KB Output is correct
20 Correct 694 ms 510556 KB Output is correct
21 Correct 669 ms 510408 KB Output is correct
22 Correct 708 ms 510468 KB Output is correct
23 Correct 687 ms 510216 KB Output is correct
24 Correct 713 ms 509948 KB Output is correct
25 Correct 791 ms 511692 KB Output is correct
26 Correct 807 ms 512272 KB Output is correct
27 Correct 780 ms 511964 KB Output is correct
28 Correct 738 ms 511032 KB Output is correct
29 Correct 791 ms 513472 KB Output is correct
30 Correct 764 ms 510460 KB Output is correct
31 Correct 814 ms 510308 KB Output is correct
32 Correct 813 ms 513476 KB Output is correct
33 Correct 627 ms 509096 KB Output is correct
34 Correct 635 ms 509184 KB Output is correct
35 Correct 657 ms 509216 KB Output is correct
36 Correct 679 ms 509144 KB Output is correct
37 Correct 755 ms 508936 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 509136 KB Output is correct
2 Correct 645 ms 510092 KB Output is correct
3 Correct 694 ms 510156 KB Output is correct
4 Correct 654 ms 510000 KB Output is correct
5 Correct 635 ms 509260 KB Output is correct
6 Correct 673 ms 509324 KB Output is correct
7 Correct 677 ms 509108 KB Output is correct
8 Correct 669 ms 509140 KB Output is correct
9 Correct 637 ms 509132 KB Output is correct
10 Correct 656 ms 509112 KB Output is correct
11 Correct 651 ms 509020 KB Output is correct
12 Correct 663 ms 509408 KB Output is correct
13 Correct 650 ms 509140 KB Output is correct
14 Correct 655 ms 509048 KB Output is correct
15 Correct 668 ms 509164 KB Output is correct
16 Correct 641 ms 509060 KB Output is correct
17 Correct 732 ms 510304 KB Output is correct
18 Correct 711 ms 510348 KB Output is correct
19 Correct 699 ms 510412 KB Output is correct
20 Correct 694 ms 510556 KB Output is correct
21 Correct 669 ms 510408 KB Output is correct
22 Correct 708 ms 510468 KB Output is correct
23 Correct 687 ms 510216 KB Output is correct
24 Correct 713 ms 509948 KB Output is correct
25 Correct 791 ms 511692 KB Output is correct
26 Correct 807 ms 512272 KB Output is correct
27 Correct 780 ms 511964 KB Output is correct
28 Correct 738 ms 511032 KB Output is correct
29 Correct 791 ms 513472 KB Output is correct
30 Correct 764 ms 510460 KB Output is correct
31 Correct 814 ms 510308 KB Output is correct
32 Correct 813 ms 513476 KB Output is correct
33 Correct 1238 ms 514792 KB Output is correct
34 Correct 1032 ms 515604 KB Output is correct
35 Correct 1140 ms 515376 KB Output is correct
36 Correct 1040 ms 511764 KB Output is correct
37 Correct 1515 ms 519000 KB Output is correct
38 Correct 1621 ms 517800 KB Output is correct
39 Correct 1432 ms 517944 KB Output is correct
40 Correct 1535 ms 518284 KB Output is correct
41 Correct 1139 ms 516960 KB Output is correct
42 Correct 1227 ms 518964 KB Output is correct
43 Correct 1442 ms 519956 KB Output is correct
44 Correct 1404 ms 520104 KB Output is correct
45 Correct 1094 ms 515652 KB Output is correct
46 Correct 1175 ms 520712 KB Output is correct
47 Correct 1365 ms 519680 KB Output is correct
48 Correct 1231 ms 518252 KB Output is correct
49 Correct 627 ms 509096 KB Output is correct
50 Correct 635 ms 509184 KB Output is correct
51 Correct 657 ms 509216 KB Output is correct
52 Correct 679 ms 509144 KB Output is correct
53 Correct 755 ms 508936 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 686 ms 510224 KB Output is correct
2 Correct 660 ms 510256 KB Output is correct
3 Correct 688 ms 509664 KB Output is correct
4 Correct 646 ms 509136 KB Output is correct
5 Correct 666 ms 509924 KB Output is correct
6 Correct 648 ms 510264 KB Output is correct
7 Correct 689 ms 510228 KB Output is correct
8 Correct 683 ms 510352 KB Output is correct
9 Correct 706 ms 510132 KB Output is correct
10 Correct 735 ms 509192 KB Output is correct
11 Correct 655 ms 509608 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 509108 KB Output is correct
2 Correct 2123 ms 518128 KB Output is correct
3 Correct 3794 ms 518212 KB Output is correct
4 Correct 3147 ms 518920 KB Output is correct
5 Correct 3088 ms 518780 KB Output is correct
6 Correct 1724 ms 515244 KB Output is correct
7 Correct 2541 ms 515492 KB Output is correct
8 Correct 2569 ms 515636 KB Output is correct
9 Correct 627 ms 509096 KB Output is correct
10 Correct 635 ms 509184 KB Output is correct
11 Correct 657 ms 509216 KB Output is correct
12 Correct 679 ms 509144 KB Output is correct
13 Correct 755 ms 508936 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 509136 KB Output is correct
2 Correct 645 ms 510092 KB Output is correct
3 Correct 694 ms 510156 KB Output is correct
4 Correct 654 ms 510000 KB Output is correct
5 Correct 635 ms 509260 KB Output is correct
6 Correct 673 ms 509324 KB Output is correct
7 Correct 677 ms 509108 KB Output is correct
8 Correct 669 ms 509140 KB Output is correct
9 Correct 637 ms 509132 KB Output is correct
10 Correct 656 ms 509112 KB Output is correct
11 Correct 651 ms 509020 KB Output is correct
12 Correct 663 ms 509408 KB Output is correct
13 Correct 650 ms 509140 KB Output is correct
14 Correct 655 ms 509048 KB Output is correct
15 Correct 668 ms 509164 KB Output is correct
16 Correct 641 ms 509060 KB Output is correct
17 Correct 732 ms 510304 KB Output is correct
18 Correct 711 ms 510348 KB Output is correct
19 Correct 699 ms 510412 KB Output is correct
20 Correct 694 ms 510556 KB Output is correct
21 Correct 669 ms 510408 KB Output is correct
22 Correct 708 ms 510468 KB Output is correct
23 Correct 687 ms 510216 KB Output is correct
24 Correct 713 ms 509948 KB Output is correct
25 Correct 791 ms 511692 KB Output is correct
26 Correct 807 ms 512272 KB Output is correct
27 Correct 780 ms 511964 KB Output is correct
28 Correct 738 ms 511032 KB Output is correct
29 Correct 791 ms 513472 KB Output is correct
30 Correct 764 ms 510460 KB Output is correct
31 Correct 814 ms 510308 KB Output is correct
32 Correct 813 ms 513476 KB Output is correct
33 Correct 1238 ms 514792 KB Output is correct
34 Correct 1032 ms 515604 KB Output is correct
35 Correct 1140 ms 515376 KB Output is correct
36 Correct 1040 ms 511764 KB Output is correct
37 Correct 1515 ms 519000 KB Output is correct
38 Correct 1621 ms 517800 KB Output is correct
39 Correct 1432 ms 517944 KB Output is correct
40 Correct 1535 ms 518284 KB Output is correct
41 Correct 1139 ms 516960 KB Output is correct
42 Correct 1227 ms 518964 KB Output is correct
43 Correct 1442 ms 519956 KB Output is correct
44 Correct 1404 ms 520104 KB Output is correct
45 Correct 1094 ms 515652 KB Output is correct
46 Correct 1175 ms 520712 KB Output is correct
47 Correct 1365 ms 519680 KB Output is correct
48 Correct 1231 ms 518252 KB Output is correct
49 Correct 686 ms 510224 KB Output is correct
50 Correct 660 ms 510256 KB Output is correct
51 Correct 688 ms 509664 KB Output is correct
52 Correct 646 ms 509136 KB Output is correct
53 Correct 666 ms 509924 KB Output is correct
54 Correct 648 ms 510264 KB Output is correct
55 Correct 689 ms 510228 KB Output is correct
56 Correct 683 ms 510352 KB Output is correct
57 Correct 706 ms 510132 KB Output is correct
58 Correct 735 ms 509192 KB Output is correct
59 Correct 655 ms 509608 KB Output is correct
60 Correct 626 ms 509108 KB Output is correct
61 Correct 2123 ms 518128 KB Output is correct
62 Correct 3794 ms 518212 KB Output is correct
63 Correct 3147 ms 518920 KB Output is correct
64 Correct 3088 ms 518780 KB Output is correct
65 Correct 1724 ms 515244 KB Output is correct
66 Correct 2541 ms 515492 KB Output is correct
67 Correct 2569 ms 515636 KB Output is correct
68 Correct 2634 ms 516148 KB Output is correct
69 Correct 2704 ms 515964 KB Output is correct
70 Correct 2518 ms 515748 KB Output is correct
71 Correct 2583 ms 516196 KB Output is correct
72 Correct 4383 ms 517228 KB Output is correct
73 Correct 2731 ms 518372 KB Output is correct
74 Correct 3292 ms 518540 KB Output is correct
75 Correct 3949 ms 519260 KB Output is correct
76 Correct 3197 ms 518860 KB Output is correct
77 Correct 3766 ms 519268 KB Output is correct
78 Correct 4238 ms 518900 KB Output is correct
79 Correct 3170 ms 518376 KB Output is correct
80 Correct 4191 ms 519144 KB Output is correct
81 Correct 4035 ms 519032 KB Output is correct
82 Correct 2968 ms 516452 KB Output is correct
83 Correct 4320 ms 517864 KB Output is correct
84 Correct 4527 ms 517132 KB Output is correct
85 Correct 4147 ms 517520 KB Output is correct
86 Correct 627 ms 509096 KB Output is correct
87 Correct 635 ms 509184 KB Output is correct
88 Correct 657 ms 509216 KB Output is correct
89 Correct 679 ms 509144 KB Output is correct
90 Correct 755 ms 508936 KB Output is correct