oj.uz

답안 #291864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
291864 2020-09-05T22:16:38 Z keko37 Rectangles (IOI19_rect) C++14
100 / 100
 4927 ms 673100 KB 
#include<bits/stdc++.h>
#include "rect.h"

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 2505;
const int INF = 1000000007;

int n, m;
int a[MAXN][MAXN];
int lef[MAXN][MAXN], rig[MAXN][MAXN], upp[MAXN][MAXN], dwn[MAXN][MAXN];
vector <int> valr[MAXN][MAXN], valc[MAXN][MAXN];
vector < pair <pi, pi> > sol;

void precompute_row (int r) {
	vector <int> st;
	vector <pi> seg;
	for (int c = 0; c < m; c++) {
		while (!st.empty() && a[r][st.back()] <= a[r][c]) st.pop_back();
		lef[r][c] = (st.empty() ? -1 : st.back());
		st.push_back(c);
	}
	st.clear();
	for (int c = m - 1; c >= 0; c--) {
		while (!st.empty() && a[r][st.back()] <= a[r][c]) st.pop_back();
		rig[r][c] = (st.empty() ? -1 : st.back());
		st.push_back(c);
	}
	for (int c = 0; c < m; c++) {
		if (lef[r][c] != -1 && rig[r][c] != -1) seg.push_back({lef[r][c] + 1, rig[r][c] - 1});
	}
	sort(seg.begin(), seg.end());
	seg.erase(unique(seg.begin(), seg.end()), seg.end());
	for (auto par : seg) {
		valr[par.first][par.second].push_back(r);
	}
}

void precompute_col (int c) {
	vector <int> st;
	vector <pi> seg;
	for (int r = 0; r < n; r++) {
		while (!st.empty() && a[st.back()][c] <= a[r][c]) st.pop_back();
		upp[r][c] = (st.empty() ? -1 : st.back());
		st.push_back(r);
	}
	st.clear();
	for (int r = n - 1; r >= 0; r--) {
		while (!st.empty() && a[st.back()][c] <= a[r][c]) st.pop_back();
		dwn[r][c] = (st.empty() ? -1 : st.back());
		st.push_back(r);
	}
	for (int r = 0; r < n; r++) {
		if (upp[r][c] != -1 && dwn[r][c] != -1) seg.push_back({upp[r][c] + 1, dwn[r][c] - 1});
	}
	sort(seg.begin(), seg.end());
	seg.erase(unique(seg.begin(), seg.end()), seg.end());
	for (auto par : seg) {
		valc[par.first][par.second].push_back(c);
	}
}

inline int upit_row (int r, int c1, int c2) {
	return upper_bound(valr[c1][c2].begin(), valr[c1][c2].end(), r) - valr[c1][c2].begin();
}

inline int sum_row (int r1, int r2, int c1, int c2) {
	return upit_row(r2, c1, c2) - upit_row(r1 - 1, c1, c2);
}

inline int upit_col (int c, int r1, int r2) {
	return upper_bound(valc[r1][r2].begin(), valc[r1][r2].end(), c) - valc[r1][r2].begin();
}

inline int sum_col (int r1, int r2, int c1, int c2) {
	return upit_col(c2, r1, r2) - upit_col(c1 - 1, r1, r2);
}

bool check (int r1, int r2, int c1, int c2) {
	return sum_row(r1, r2, c1, c2) == r2 - r1 + 1 && sum_col(r1, r2, c1, c2) == c2 - c1 + 1;
}

llint count_rectangles (vector<vector<int>> A) {
	n = A.size(), m = A[0].size();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			a[i][j] = A[i][j];
		}
	}
	for (int r = 0; r < n; r++) precompute_row(r);
	for (int c = 0; c < m; c++) precompute_col(c);
	for (int r = 1; r < n - 1; r++) {
		for (int c = 1; c < m - 1; c++) {
			if (lef[r][c] != -1 && rig[r][c] != -1 && upp[r][c] != -1 && dwn[r][c] != -1) {
				if (check(upp[r][c] + 1, dwn[r][c] - 1, lef[r][c] + 1, rig[r][c] - 1)) {
					sol.push_back({{upp[r][c] + 1, dwn[r][c] - 1}, {lef[r][c] + 1, rig[r][c] - 1}});
				}
			}
		}
	}
	sort(sol.begin(), sol.end());
	sol.erase(unique(sol.begin(), sol.end()), sol.end());
	return sol.size();
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 295160 KB Output is correct
2 Correct 197 ms 295672 KB Output is correct
3 Correct 199 ms 295676 KB Output is correct
4 Correct 195 ms 295672 KB Output is correct
5 Correct 197 ms 295672 KB Output is correct
6 Correct 200 ms 295676 KB Output is correct
7 Correct 208 ms 295672 KB Output is correct
8 Correct 194 ms 295288 KB Output is correct
9 Correct 201 ms 295676 KB Output is correct
10 Correct 205 ms 295624 KB Output is correct
11 Correct 198 ms 295672 KB Output is correct
12 Correct 200 ms 295616 KB Output is correct
13 Correct 197 ms 295104 KB Output is correct
14 Correct 196 ms 295288 KB Output is correct
15 Correct 195 ms 295176 KB Output is correct
16 Correct 202 ms 295288 KB Output is correct
17 Correct 204 ms 295040 KB Output is correct
18 Correct 199 ms 295032 KB Output is correct
19 Correct 198 ms 295672 KB Output is correct
20 Correct 195 ms 295672 KB Output is correct
21 Correct 197 ms 295284 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 295160 KB Output is correct
2 Correct 197 ms 295672 KB Output is correct
3 Correct 199 ms 295676 KB Output is correct
4 Correct 195 ms 295672 KB Output is correct
5 Correct 197 ms 295672 KB Output is correct
6 Correct 200 ms 295676 KB Output is correct
7 Correct 208 ms 295672 KB Output is correct
8 Correct 194 ms 295288 KB Output is correct
9 Correct 201 ms 295676 KB Output is correct
10 Correct 205 ms 295624 KB Output is correct
11 Correct 198 ms 295672 KB Output is correct
12 Correct 200 ms 295616 KB Output is correct
13 Correct 197 ms 295104 KB Output is correct
14 Correct 196 ms 295288 KB Output is correct
15 Correct 195 ms 295176 KB Output is correct
16 Correct 202 ms 295288 KB Output is correct
17 Correct 202 ms 297080 KB Output is correct
18 Correct 200 ms 297252 KB Output is correct
19 Correct 198 ms 297208 KB Output is correct
20 Correct 201 ms 297080 KB Output is correct
21 Correct 202 ms 297000 KB Output is correct
22 Correct 199 ms 296952 KB Output is correct
23 Correct 202 ms 297060 KB Output is correct
24 Correct 198 ms 296824 KB Output is correct
25 Correct 204 ms 295040 KB Output is correct
26 Correct 199 ms 295032 KB Output is correct
27 Correct 198 ms 295672 KB Output is correct
28 Correct 195 ms 295672 KB Output is correct
29 Correct 197 ms 295284 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 295160 KB Output is correct
2 Correct 197 ms 295672 KB Output is correct
3 Correct 199 ms 295676 KB Output is correct
4 Correct 195 ms 295672 KB Output is correct
5 Correct 197 ms 295672 KB Output is correct
6 Correct 200 ms 295676 KB Output is correct
7 Correct 208 ms 295672 KB Output is correct
8 Correct 194 ms 295288 KB Output is correct
9 Correct 201 ms 295676 KB Output is correct
10 Correct 205 ms 295624 KB Output is correct
11 Correct 198 ms 295672 KB Output is correct
12 Correct 200 ms 295616 KB Output is correct
13 Correct 197 ms 295104 KB Output is correct
14 Correct 196 ms 295288 KB Output is correct
15 Correct 195 ms 295176 KB Output is correct
16 Correct 202 ms 295288 KB Output is correct
17 Correct 202 ms 297080 KB Output is correct
18 Correct 200 ms 297252 KB Output is correct
19 Correct 198 ms 297208 KB Output is correct
20 Correct 201 ms 297080 KB Output is correct
21 Correct 202 ms 297000 KB Output is correct
22 Correct 199 ms 296952 KB Output is correct
23 Correct 202 ms 297060 KB Output is correct
24 Correct 198 ms 296824 KB Output is correct
25 Correct 220 ms 301816 KB Output is correct
26 Correct 217 ms 301688 KB Output is correct
27 Correct 212 ms 301816 KB Output is correct
28 Correct 211 ms 300664 KB Output is correct
29 Correct 220 ms 301308 KB Output is correct
30 Correct 218 ms 301256 KB Output is correct
31 Correct 220 ms 301308 KB Output is correct
32 Correct 219 ms 301052 KB Output is correct
33 Correct 204 ms 295040 KB Output is correct
34 Correct 199 ms 295032 KB Output is correct
35 Correct 198 ms 295672 KB Output is correct
36 Correct 195 ms 295672 KB Output is correct
37 Correct 197 ms 295284 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 295160 KB Output is correct
2 Correct 197 ms 295672 KB Output is correct
3 Correct 199 ms 295676 KB Output is correct
4 Correct 195 ms 295672 KB Output is correct
5 Correct 197 ms 295672 KB Output is correct
6 Correct 200 ms 295676 KB Output is correct
7 Correct 208 ms 295672 KB Output is correct
8 Correct 194 ms 295288 KB Output is correct
9 Correct 201 ms 295676 KB Output is correct
10 Correct 205 ms 295624 KB Output is correct
11 Correct 198 ms 295672 KB Output is correct
12 Correct 200 ms 295616 KB Output is correct
13 Correct 197 ms 295104 KB Output is correct
14 Correct 196 ms 295288 KB Output is correct
15 Correct 195 ms 295176 KB Output is correct
16 Correct 202 ms 295288 KB Output is correct
17 Correct 202 ms 297080 KB Output is correct
18 Correct 200 ms 297252 KB Output is correct
19 Correct 198 ms 297208 KB Output is correct
20 Correct 201 ms 297080 KB Output is correct
21 Correct 202 ms 297000 KB Output is correct
22 Correct 199 ms 296952 KB Output is correct
23 Correct 202 ms 297060 KB Output is correct
24 Correct 198 ms 296824 KB Output is correct
25 Correct 220 ms 301816 KB Output is correct
26 Correct 217 ms 301688 KB Output is correct
27 Correct 212 ms 301816 KB Output is correct
28 Correct 211 ms 300664 KB Output is correct
29 Correct 220 ms 301308 KB Output is correct
30 Correct 218 ms 301256 KB Output is correct
31 Correct 220 ms 301308 KB Output is correct
32 Correct 219 ms 301052 KB Output is correct
33 Correct 314 ms 338200 KB Output is correct
34 Correct 311 ms 337880 KB Output is correct
35 Correct 307 ms 337912 KB Output is correct
36 Correct 303 ms 337784 KB Output is correct
37 Correct 427 ms 336476 KB Output is correct
38 Correct 432 ms 336480 KB Output is correct
39 Correct 427 ms 336864 KB Output is correct
40 Correct 408 ms 334708 KB Output is correct
41 Correct 319 ms 324852 KB Output is correct
42 Correct 353 ms 326204 KB Output is correct
43 Correct 483 ms 333292 KB Output is correct
44 Correct 490 ms 333420 KB Output is correct
45 Correct 338 ms 321416 KB Output is correct
46 Correct 347 ms 314476 KB Output is correct
47 Correct 492 ms 332132 KB Output is correct
48 Correct 498 ms 332268 KB Output is correct
49 Correct 204 ms 295040 KB Output is correct
50 Correct 199 ms 295032 KB Output is correct
51 Correct 198 ms 295672 KB Output is correct
52 Correct 195 ms 295672 KB Output is correct
53 Correct 197 ms 295284 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 295416 KB Output is correct
2 Correct 200 ms 295544 KB Output is correct
3 Correct 201 ms 295288 KB Output is correct
4 Correct 197 ms 295032 KB Output is correct
5 Correct 202 ms 295544 KB Output is correct
6 Correct 203 ms 295424 KB Output is correct
7 Correct 199 ms 295544 KB Output is correct
8 Correct 198 ms 295544 KB Output is correct
9 Correct 198 ms 295544 KB Output is correct
10 Correct 198 ms 295164 KB Output is correct
11 Correct 199 ms 295436 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 199 ms 295288 KB Output is correct
2 Correct 987 ms 392684 KB Output is correct
3 Correct 1985 ms 495240 KB Output is correct
4 Correct 2029 ms 495940 KB Output is correct
5 Correct 1982 ms 496244 KB Output is correct
6 Correct 478 ms 379768 KB Output is correct
7 Correct 753 ms 463644 KB Output is correct
8 Correct 796 ms 466808 KB Output is correct
9 Correct 204 ms 295040 KB Output is correct
10 Correct 199 ms 295032 KB Output is correct
11 Correct 198 ms 295672 KB Output is correct
12 Correct 195 ms 295672 KB Output is correct
13 Correct 197 ms 295284 KB Output is correct

Subtask #7
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 295160 KB Output is correct
2 Correct 197 ms 295672 KB Output is correct
3 Correct 199 ms 295676 KB Output is correct
4 Correct 195 ms 295672 KB Output is correct
5 Correct 197 ms 295672 KB Output is correct
6 Correct 200 ms 295676 KB Output is correct
7 Correct 208 ms 295672 KB Output is correct
8 Correct 194 ms 295288 KB Output is correct
9 Correct 201 ms 295676 KB Output is correct
10 Correct 205 ms 295624 KB Output is correct
11 Correct 198 ms 295672 KB Output is correct
12 Correct 200 ms 295616 KB Output is correct
13 Correct 197 ms 295104 KB Output is correct
14 Correct 196 ms 295288 KB Output is correct
15 Correct 195 ms 295176 KB Output is correct
16 Correct 202 ms 295288 KB Output is correct
17 Correct 202 ms 297080 KB Output is correct
18 Correct 200 ms 297252 KB Output is correct
19 Correct 198 ms 297208 KB Output is correct
20 Correct 201 ms 297080 KB Output is correct
21 Correct 202 ms 297000 KB Output is correct
22 Correct 199 ms 296952 KB Output is correct
23 Correct 202 ms 297060 KB Output is correct
24 Correct 198 ms 296824 KB Output is correct
25 Correct 220 ms 301816 KB Output is correct
26 Correct 217 ms 301688 KB Output is correct
27 Correct 212 ms 301816 KB Output is correct
28 Correct 211 ms 300664 KB Output is correct
29 Correct 220 ms 301308 KB Output is correct
30 Correct 218 ms 301256 KB Output is correct
31 Correct 220 ms 301308 KB Output is correct
32 Correct 219 ms 301052 KB Output is correct
33 Correct 314 ms 338200 KB Output is correct
34 Correct 311 ms 337880 KB Output is correct
35 Correct 307 ms 337912 KB Output is correct
36 Correct 303 ms 337784 KB Output is correct
37 Correct 427 ms 336476 KB Output is correct
38 Correct 432 ms 336480 KB Output is correct
39 Correct 427 ms 336864 KB Output is correct
40 Correct 408 ms 334708 KB Output is correct
41 Correct 319 ms 324852 KB Output is correct
42 Correct 353 ms 326204 KB Output is correct
43 Correct 483 ms 333292 KB Output is correct
44 Correct 490 ms 333420 KB Output is correct
45 Correct 338 ms 321416 KB Output is correct
46 Correct 347 ms 314476 KB Output is correct
47 Correct 492 ms 332132 KB Output is correct
48 Correct 498 ms 332268 KB Output is correct
49 Correct 201 ms 295416 KB Output is correct
50 Correct 200 ms 295544 KB Output is correct
51 Correct 201 ms 295288 KB Output is correct
52 Correct 197 ms 295032 KB Output is correct
53 Correct 202 ms 295544 KB Output is correct
54 Correct 203 ms 295424 KB Output is correct
55 Correct 199 ms 295544 KB Output is correct
56 Correct 198 ms 295544 KB Output is correct
57 Correct 198 ms 295544 KB Output is correct
58 Correct 198 ms 295164 KB Output is correct
59 Correct 199 ms 295436 KB Output is correct
60 Correct 199 ms 295288 KB Output is correct
61 Correct 987 ms 392684 KB Output is correct
62 Correct 1985 ms 495240 KB Output is correct
63 Correct 2029 ms 495940 KB Output is correct
64 Correct 1982 ms 496244 KB Output is correct
65 Correct 478 ms 379768 KB Output is correct
66 Correct 753 ms 463644 KB Output is correct
67 Correct 796 ms 466808 KB Output is correct
68 Correct 2089 ms 662424 KB Output is correct
69 Correct 1825 ms 662744 KB Output is correct
70 Correct 1845 ms 662764 KB Output is correct
71 Correct 1510 ms 662392 KB Output is correct
72 Correct 4096 ms 672968 KB Output is correct
73 Correct 2874 ms 477528 KB Output is correct
74 Correct 3047 ms 535632 KB Output is correct
75 Correct 4791 ms 607092 KB Output is correct
76 Correct 2912 ms 478940 KB Output is correct
77 Correct 3870 ms 554788 KB Output is correct
78 Correct 4927 ms 609432 KB Output is correct
79 Correct 2890 ms 470844 KB Output is correct
80 Correct 4908 ms 599944 KB Output is correct
81 Correct 4807 ms 593332 KB Output is correct
82 Correct 2303 ms 555572 KB Output is correct
83 Correct 4131 ms 673036 KB Output is correct
84 Correct 4189 ms 673100 KB Output is correct
85 Correct 4086 ms 672812 KB Output is correct
86 Correct 204 ms 295040 KB Output is correct
87 Correct 199 ms 295032 KB Output is correct
88 Correct 198 ms 295672 KB Output is correct
89 Correct 195 ms 295672 KB Output is correct
90 Correct 197 ms 295284 KB Output is correct