oj.uz

답안 #829055

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
829055 2023-08-18T03:02:49 Z PurpleCrayon Rectangles (IOI19_rect) C++17
100 / 100
 2559 ms 781156 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2.5e3+10;

int n, m, prv_u[N][N], prv_d[N][N], prv_l[N][N], prv_r[N][N];
vector<int> sorted[N];
vector<short> ups[N][N], rights[N][N];

short can_ups[N * N], can_rights[N * N];
int l_ups[N][N], l_rights[N][N];
int cnt_ups = 0, cnt_rights = 0;

int far[N];

long long count_rectangles(vector<vector<int>> a) {
	n = sz(a), m = sz(a[0]);

	memset(prv_u, -1, sizeof(prv_u));
	memset(prv_d, -1, sizeof(prv_d));
	memset(prv_l, -1, sizeof(prv_l));
	memset(prv_r, -1, sizeof(prv_r));
	for (int i = 0; i < n; i++) {
		vector<int> stk;
		for (int j = 0; j < m; j++) {
			while (sz(stk) && a[stk.back() / m][stk.back() % m] <= a[i][j]) stk.pop_back();
			if (sz(stk)) prv_l[i][j] = stk.back();
			stk.push_back(i * m + j);
		}
	}

	for (int i = 0; i < n; i++) {
		vector<int> stk;
		for (int j = m-1; j >= 0; j--) {
			while (sz(stk) && a[stk.back() / m][stk.back() % m] < a[i][j]) stk.pop_back();
			if (sz(stk)) prv_r[i][j] = stk.back();
			stk.push_back(i * m + j);
		}
	}

	for (int j = 0; j < m; j++) {
		vector<int> stk;
		for (int i = 0; i < n; i++) {
			while (sz(stk) && a[stk.back() / m][stk.back() % m] <= a[i][j]) stk.pop_back();
			if (sz(stk)) prv_u[i][j] = stk.back();
			stk.push_back(i * m + j);
		}
	}

	for (int j = 0; j < m; j++) {
		vector<int> stk;
		for (int i = n-1; i >= 0; i--) {
			while (sz(stk) && a[stk.back() / m][stk.back() % m] < a[i][j]) stk.pop_back();
			if (sz(stk)) prv_d[i][j] = stk.back();
			stk.push_back(i * m + j);
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (prv_d[i][j] == -1 || a[prv_d[i][j] / m][prv_d[i][j] % m] <= a[i][j]) continue;
			if (prv_u[i][j] == -1 || a[prv_u[i][j] / m][prv_u[i][j] % m] <= a[i][j]) continue;
			sorted[prv_u[i][j] / m].push_back(prv_d[i][j]);
			// ups[prv_d[i][j] / m][prv_d[i][j] % m].push_back(prv_u[i][j] / m);
		}
	}

	for (int i = 0; i < n; i++) {
		for (int c : sorted[i]) {
			ups[c / m][c % m].push_back(i);
		}
		vector<int>().swap(sorted[i]);
	}


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (prv_l[i][j] == -1 || a[prv_l[i][j] / m][prv_l[i][j] % m] <= a[i][j]) continue;
			if (prv_r[i][j] == -1 || a[prv_r[i][j] / m][prv_r[i][j] % m] <= a[i][j]) continue;
			sorted[prv_r[i][j] % m].push_back(prv_l[i][j]);
			// rights[prv_l[i][j] / m][prv_l[i][j] % m].push_back(prv_r[i][j] % m);
		}
	}

	for (int i = 0; i < m; i++) {
		for (int c : sorted[i]) {
			rights[c / m][c % m].push_back(i);
		}

		vector<int>().swap(sorted[i]);
	}

	for (int i = 0; i < n; i++) {
		memset(far, -1, sizeof(far));
		for (int j = m-1; j >= 0; j--) {
			int k = sz(ups[i][j]);
			l_ups[i][j] = cnt_ups;
			// can_ups[i][j].resize(k);

			for (int c = 0; c < k; c++) {
				can_ups[cnt_ups++] = far[ups[i][j][c]] != -1 ? far[ups[i][j][c]] : j;
			}

			if (j < m-1) {
				for (int c = 0; c < sz(ups[i][j+1]); c++)
					far[ups[i][j+1][c]] = -1;
			}

			for (int c = 0; c < k; c++)
				far[ups[i][j][c]] = can_ups[l_ups[i][j] + c];
		}
	}

	for (int j = 0; j < m; j++) {
		memset(far, -1, sizeof(far));
		for (int i = 0; i < n; i++) {
			int k = sz(rights[i][j]);
			// can_rights[i][j].resize(k);
			l_rights[i][j] = cnt_rights;

			for (int c = 0; c < k; c++) {
				can_rights[cnt_rights++] = far[rights[i][j][c]] != -1 ? far[rights[i][j][c]] : i;
			}

			if (i > 0) {
				for (int c = 0; c < sz(rights[i-1][j]); c++)
					far[rights[i-1][j][c]] = -1;
			}

			for (int c = 0; c < k; c++)
				far[rights[i][j][c]] = can_rights[l_rights[i][j] + c];
		}
	}

	// for (int i = 0; i < n; i++) {
	// 	for (int j = 0; j < m; j++) {
	// 		if (sz(ups[i][j])) {
	// 			cerr << "ups: " << 	i << ' ' << j << endl;
	// 			for (int c : ups[i][j]) cerr << c << ' ';
	// 			cerr << endl;
	// 		}
	// 	}
	// }

	// for (int i = 0; i < n; i++) {
	// 	for (int j = 0; j < m; j++) {
	// 		if (sz(rights[i][j])) {
	// 			cerr << "rights: " << i << ' ' << j << endl;
	// 			for (int c : rights[i][j]) cerr << c << ' ';
	// 			cerr << endl;
	// 		}
	// 	}
	// }

	ll ans = 0;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < m-1; j++) {
			int k1 = sz(ups[i][j+1]);
			int k2 = sz(rights[i-1][j]);
			for (int a = 0; a < k1; a++) {
				for (int b = 0; b < k2; b++) {
					// if (i == 2 && j == 2 && ups[i][j+1][a] == 0 && rights[i-1][j][b] == 4) {
					// 	cerr << "HERE: " << can_rights[i-1][j][b] << ' ' << can_ups[i][j+1][a] << endl;
					// }

					// if (rights[i-1][j][b] > can_ups[i][j+1][a] + 1) break;
					if (rights[i-1][j][b] > can_ups[l_ups[i][j+1] + a] + 1) break;

					if (ups[i][j+1][a] >= can_rights[l_rights[i-1][j] + b] - 1) {
					// if (ups[i][j+1][a] >= can_rights[i-1][j][b] - 1) {
						// cout << ups[i][j+1][a] << ' ' << i << ' ' << j << ' ' << rights[i-1][j][b] << endl;
						ans++;
					}
				}
			}
		}
	}

	return ans;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 394912 KB Output is correct
2 Correct 150 ms 395128 KB Output is correct
3 Correct 152 ms 395128 KB Output is correct
4 Correct 153 ms 395140 KB Output is correct
5 Correct 169 ms 395132 KB Output is correct
6 Correct 155 ms 395104 KB Output is correct
7 Correct 149 ms 395060 KB Output is correct
8 Correct 152 ms 394944 KB Output is correct
9 Correct 152 ms 395172 KB Output is correct
10 Correct 162 ms 395144 KB Output is correct
11 Correct 155 ms 395160 KB Output is correct
12 Correct 152 ms 395184 KB Output is correct
13 Correct 150 ms 394868 KB Output is correct
14 Correct 153 ms 394928 KB Output is correct
15 Correct 152 ms 394952 KB Output is correct
16 Correct 158 ms 394812 KB Output is correct
17 Correct 159 ms 394884 KB Output is correct
18 Correct 155 ms 394832 KB Output is correct
19 Correct 158 ms 395160 KB Output is correct
20 Correct 148 ms 395128 KB Output is correct
21 Correct 149 ms 394932 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 394912 KB Output is correct
2 Correct 150 ms 395128 KB Output is correct
3 Correct 152 ms 395128 KB Output is correct
4 Correct 153 ms 395140 KB Output is correct
5 Correct 169 ms 395132 KB Output is correct
6 Correct 155 ms 395104 KB Output is correct
7 Correct 149 ms 395060 KB Output is correct
8 Correct 152 ms 394944 KB Output is correct
9 Correct 152 ms 395172 KB Output is correct
10 Correct 162 ms 395144 KB Output is correct
11 Correct 155 ms 395160 KB Output is correct
12 Correct 152 ms 395184 KB Output is correct
13 Correct 150 ms 394868 KB Output is correct
14 Correct 153 ms 394928 KB Output is correct
15 Correct 152 ms 394952 KB Output is correct
16 Correct 158 ms 394812 KB Output is correct
17 Correct 159 ms 394884 KB Output is correct
18 Correct 155 ms 394832 KB Output is correct
19 Correct 158 ms 395160 KB Output is correct
20 Correct 148 ms 395128 KB Output is correct
21 Correct 149 ms 394932 KB Output is correct
22 Correct 160 ms 395900 KB Output is correct
23 Correct 152 ms 395888 KB Output is correct
24 Correct 196 ms 395864 KB Output is correct
25 Correct 152 ms 395684 KB Output is correct
26 Correct 152 ms 395820 KB Output is correct
27 Correct 158 ms 395984 KB Output is correct
28 Correct 154 ms 395876 KB Output is correct
29 Correct 150 ms 395612 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 394912 KB Output is correct
2 Correct 150 ms 395128 KB Output is correct
3 Correct 152 ms 395128 KB Output is correct
4 Correct 153 ms 395140 KB Output is correct
5 Correct 169 ms 395132 KB Output is correct
6 Correct 155 ms 395104 KB Output is correct
7 Correct 149 ms 395060 KB Output is correct
8 Correct 152 ms 394944 KB Output is correct
9 Correct 152 ms 395172 KB Output is correct
10 Correct 162 ms 395144 KB Output is correct
11 Correct 155 ms 395160 KB Output is correct
12 Correct 152 ms 395184 KB Output is correct
13 Correct 150 ms 394868 KB Output is correct
14 Correct 153 ms 394928 KB Output is correct
15 Correct 152 ms 394952 KB Output is correct
16 Correct 158 ms 394812 KB Output is correct
17 Correct 160 ms 395900 KB Output is correct
18 Correct 152 ms 395888 KB Output is correct
19 Correct 196 ms 395864 KB Output is correct
20 Correct 152 ms 395684 KB Output is correct
21 Correct 152 ms 395820 KB Output is correct
22 Correct 158 ms 395984 KB Output is correct
23 Correct 154 ms 395876 KB Output is correct
24 Correct 150 ms 395612 KB Output is correct
25 Correct 159 ms 394884 KB Output is correct
26 Correct 155 ms 394832 KB Output is correct
27 Correct 158 ms 395160 KB Output is correct
28 Correct 148 ms 395128 KB Output is correct
29 Correct 149 ms 394932 KB Output is correct
30 Correct 183 ms 398596 KB Output is correct
31 Correct 162 ms 398672 KB Output is correct
32 Correct 156 ms 398656 KB Output is correct
33 Correct 158 ms 398040 KB Output is correct
34 Correct 162 ms 398476 KB Output is correct
35 Correct 163 ms 398468 KB Output is correct
36 Correct 160 ms 398412 KB Output is correct
37 Correct 160 ms 398288 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 394912 KB Output is correct
2 Correct 150 ms 395128 KB Output is correct
3 Correct 152 ms 395128 KB Output is correct
4 Correct 153 ms 395140 KB Output is correct
5 Correct 169 ms 395132 KB Output is correct
6 Correct 155 ms 395104 KB Output is correct
7 Correct 149 ms 395060 KB Output is correct
8 Correct 152 ms 394944 KB Output is correct
9 Correct 152 ms 395172 KB Output is correct
10 Correct 162 ms 395144 KB Output is correct
11 Correct 155 ms 395160 KB Output is correct
12 Correct 152 ms 395184 KB Output is correct
13 Correct 150 ms 394868 KB Output is correct
14 Correct 153 ms 394928 KB Output is correct
15 Correct 152 ms 394952 KB Output is correct
16 Correct 158 ms 394812 KB Output is correct
17 Correct 160 ms 395900 KB Output is correct
18 Correct 152 ms 395888 KB Output is correct
19 Correct 196 ms 395864 KB Output is correct
20 Correct 152 ms 395684 KB Output is correct
21 Correct 152 ms 395820 KB Output is correct
22 Correct 158 ms 395984 KB Output is correct
23 Correct 154 ms 395876 KB Output is correct
24 Correct 150 ms 395612 KB Output is correct
25 Correct 183 ms 398596 KB Output is correct
26 Correct 162 ms 398672 KB Output is correct
27 Correct 156 ms 398656 KB Output is correct
28 Correct 158 ms 398040 KB Output is correct
29 Correct 162 ms 398476 KB Output is correct
30 Correct 163 ms 398468 KB Output is correct
31 Correct 160 ms 398412 KB Output is correct
32 Correct 160 ms 398288 KB Output is correct
33 Correct 159 ms 394884 KB Output is correct
34 Correct 155 ms 394832 KB Output is correct
35 Correct 158 ms 395160 KB Output is correct
36 Correct 148 ms 395128 KB Output is correct
37 Correct 149 ms 394932 KB Output is correct
38 Correct 217 ms 417632 KB Output is correct
39 Correct 206 ms 411348 KB Output is correct
40 Correct 246 ms 424396 KB Output is correct
41 Correct 219 ms 418228 KB Output is correct
42 Correct 280 ms 426760 KB Output is correct
43 Correct 248 ms 426780 KB Output is correct
44 Correct 254 ms 426896 KB Output is correct
45 Correct 240 ms 424800 KB Output is correct
46 Correct 253 ms 416356 KB Output is correct
47 Correct 249 ms 419256 KB Output is correct
48 Correct 296 ms 425292 KB Output is correct
49 Correct 322 ms 425476 KB Output is correct
50 Correct 229 ms 412908 KB Output is correct
51 Correct 223 ms 410144 KB Output is correct
52 Correct 289 ms 423980 KB Output is correct
53 Correct 298 ms 424032 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 395340 KB Output is correct
2 Correct 150 ms 395304 KB Output is correct
3 Correct 159 ms 394956 KB Output is correct
4 Correct 149 ms 394912 KB Output is correct
5 Correct 152 ms 395168 KB Output is correct
6 Correct 151 ms 395124 KB Output is correct
7 Correct 173 ms 395108 KB Output is correct
8 Correct 151 ms 395092 KB Output is correct
9 Correct 151 ms 395164 KB Output is correct
10 Correct 151 ms 394884 KB Output is correct
11 Correct 151 ms 394968 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 394884 KB Output is correct
2 Correct 155 ms 394832 KB Output is correct
3 Correct 158 ms 395160 KB Output is correct
4 Correct 148 ms 395128 KB Output is correct
5 Correct 149 ms 394932 KB Output is correct
6 Correct 175 ms 394900 KB Output is correct
7 Correct 674 ms 489200 KB Output is correct
8 Correct 1349 ms 595984 KB Output is correct
9 Correct 1465 ms 596948 KB Output is correct
10 Correct 1524 ms 596952 KB Output is correct
11 Correct 407 ms 443292 KB Output is correct
12 Correct 687 ms 490096 KB Output is correct
13 Correct 707 ms 493040 KB Output is correct

Subtask #7
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 394912 KB Output is correct
2 Correct 150 ms 395128 KB Output is correct
3 Correct 152 ms 395128 KB Output is correct
4 Correct 153 ms 395140 KB Output is correct
5 Correct 169 ms 395132 KB Output is correct
6 Correct 155 ms 395104 KB Output is correct
7 Correct 149 ms 395060 KB Output is correct
8 Correct 152 ms 394944 KB Output is correct
9 Correct 152 ms 395172 KB Output is correct
10 Correct 162 ms 395144 KB Output is correct
11 Correct 155 ms 395160 KB Output is correct
12 Correct 152 ms 395184 KB Output is correct
13 Correct 150 ms 394868 KB Output is correct
14 Correct 153 ms 394928 KB Output is correct
15 Correct 152 ms 394952 KB Output is correct
16 Correct 158 ms 394812 KB Output is correct
17 Correct 160 ms 395900 KB Output is correct
18 Correct 152 ms 395888 KB Output is correct
19 Correct 196 ms 395864 KB Output is correct
20 Correct 152 ms 395684 KB Output is correct
21 Correct 152 ms 395820 KB Output is correct
22 Correct 158 ms 395984 KB Output is correct
23 Correct 154 ms 395876 KB Output is correct
24 Correct 150 ms 395612 KB Output is correct
25 Correct 183 ms 398596 KB Output is correct
26 Correct 162 ms 398672 KB Output is correct
27 Correct 156 ms 398656 KB Output is correct
28 Correct 158 ms 398040 KB Output is correct
29 Correct 162 ms 398476 KB Output is correct
30 Correct 163 ms 398468 KB Output is correct
31 Correct 160 ms 398412 KB Output is correct
32 Correct 160 ms 398288 KB Output is correct
33 Correct 217 ms 417632 KB Output is correct
34 Correct 206 ms 411348 KB Output is correct
35 Correct 246 ms 424396 KB Output is correct
36 Correct 219 ms 418228 KB Output is correct
37 Correct 280 ms 426760 KB Output is correct
38 Correct 248 ms 426780 KB Output is correct
39 Correct 254 ms 426896 KB Output is correct
40 Correct 240 ms 424800 KB Output is correct
41 Correct 253 ms 416356 KB Output is correct
42 Correct 249 ms 419256 KB Output is correct
43 Correct 296 ms 425292 KB Output is correct
44 Correct 322 ms 425476 KB Output is correct
45 Correct 229 ms 412908 KB Output is correct
46 Correct 223 ms 410144 KB Output is correct
47 Correct 289 ms 423980 KB Output is correct
48 Correct 298 ms 424032 KB Output is correct
49 Correct 148 ms 395340 KB Output is correct
50 Correct 150 ms 395304 KB Output is correct
51 Correct 159 ms 394956 KB Output is correct
52 Correct 149 ms 394912 KB Output is correct
53 Correct 152 ms 395168 KB Output is correct
54 Correct 151 ms 395124 KB Output is correct
55 Correct 173 ms 395108 KB Output is correct
56 Correct 151 ms 395092 KB Output is correct
57 Correct 151 ms 395164 KB Output is correct
58 Correct 151 ms 394884 KB Output is correct
59 Correct 151 ms 394968 KB Output is correct
60 Correct 175 ms 394900 KB Output is correct
61 Correct 674 ms 489200 KB Output is correct
62 Correct 1349 ms 595984 KB Output is correct
63 Correct 1465 ms 596948 KB Output is correct
64 Correct 1524 ms 596952 KB Output is correct
65 Correct 407 ms 443292 KB Output is correct
66 Correct 687 ms 490096 KB Output is correct
67 Correct 707 ms 493040 KB Output is correct
68 Correct 159 ms 394884 KB Output is correct
69 Correct 155 ms 394832 KB Output is correct
70 Correct 158 ms 395160 KB Output is correct
71 Correct 148 ms 395128 KB Output is correct
72 Correct 149 ms 394932 KB Output is correct
73 Correct 1225 ms 612188 KB Output is correct
74 Correct 1081 ms 525496 KB Output is correct
75 Correct 1507 ms 747644 KB Output is correct
76 Correct 1203 ms 667740 KB Output is correct
77 Correct 1548 ms 781156 KB Output is correct
78 Correct 1446 ms 599092 KB Output is correct
79 Correct 1531 ms 636228 KB Output is correct
80 Correct 2321 ms 735076 KB Output is correct
81 Correct 1499 ms 614676 KB Output is correct
82 Correct 2104 ms 697792 KB Output is correct
83 Correct 2559 ms 760836 KB Output is correct
84 Correct 1501 ms 597168 KB Output is correct
85 Correct 2411 ms 745788 KB Output is correct
86 Correct 2255 ms 735656 KB Output is correct
87 Correct 1004 ms 646296 KB Output is correct
88 Correct 1584 ms 779216 KB Output is correct
89 Correct 1617 ms 778632 KB Output is correct
90 Correct 1609 ms 778672 KB Output is correct