답안 #1067951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1067951	2024-08-21T05:59:29 Z	Gromp15	Rectangles (IOI19_rect)	C++17	37 / 100	438 ms	1048576 KB

rect

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include "rect.h"
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)

long long count_rectangles(std::vector<std::vector<int>> a) {
	int n = sz(a), m = sz(a[0]);
	vector ok(n, vector(n, vector<int>(m)));
	for (int i = 0; i < m; i++) {
		for (int j = 1; j < n-1; j++) {
			int mx = 0;
			for (int k = j; k < n-1; k++) {
				ckmax(mx, a[k][i]);
				ok[j][k][i] = (mx >= min(a[j-1][i], a[k+1][i])) + (i ? ok[j][k][i-1] : 0);
			}
		}
	}
	vector ok2(m, vector(m, vector<int>(n)));
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < m-1; j++) {
			int mx = 0;
			for (int k = j; k < m-1; k++) {
				ckmax(mx, a[i][k]);
				ok2[j][k][i] = (mx >= min(a[i][j-1], a[i][k+1])) + (i ? ok2[j][k][i-1] : 0);
			}
		}
	}
	long long ans = 0;
	for (int i = 1; i < n-1; i++) for (int j = i; j < n-1; j++) {
		for (int k = 1; k < m-1; k++) {
			int l = min(m-2, int(upper_bound(all(ok[i][j]), ok[i][j][k-1]) - ok[i][j].begin() - 1));
			if (l < k) continue;
			for (int t = k; t <= l; t++) {
				ans += !(ok[i][j][t] - ok[i][j][k-1]) && !(ok2[k][t][j] - ok2[k][t][i-1]);
			}
		}
	}
	return ans;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	580 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	604 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	580 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	604 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	8 ms	4956 KB	Output is correct
23	Correct	6 ms	4952 KB	Output is correct
24	Correct	6 ms	4984 KB	Output is correct
25	Correct	6 ms	4868 KB	Output is correct
26	Correct	9 ms	4956 KB	Output is correct
27	Correct	8 ms	4956 KB	Output is correct
28	Correct	10 ms	4956 KB	Output is correct
29	Correct	2 ms	2140 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	580 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	8 ms	4956 KB	Output is correct
18	Correct	6 ms	4952 KB	Output is correct
19	Correct	6 ms	4984 KB	Output is correct
20	Correct	6 ms	4868 KB	Output is correct
21	Correct	9 ms	4956 KB	Output is correct
22	Correct	8 ms	4956 KB	Output is correct
23	Correct	10 ms	4956 KB	Output is correct
24	Correct	2 ms	2140 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	604 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	121 ms	66456 KB	Output is correct
31	Correct	127 ms	66644 KB	Output is correct
32	Correct	123 ms	66644 KB	Output is correct
33	Correct	100 ms	66640 KB	Output is correct
34	Correct	102 ms	66644 KB	Output is correct
35	Correct	117 ms	66644 KB	Output is correct
36	Correct	109 ms	66556 KB	Output is correct
37	Correct	98 ms	64852 KB	Output is correct

Subtask #4
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	580 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	8 ms	4956 KB	Output is correct
18	Correct	6 ms	4952 KB	Output is correct
19	Correct	6 ms	4984 KB	Output is correct
20	Correct	6 ms	4868 KB	Output is correct
21	Correct	9 ms	4956 KB	Output is correct
22	Correct	8 ms	4956 KB	Output is correct
23	Correct	10 ms	4956 KB	Output is correct
24	Correct	2 ms	2140 KB	Output is correct
25	Correct	121 ms	66456 KB	Output is correct
26	Correct	127 ms	66644 KB	Output is correct
27	Correct	123 ms	66644 KB	Output is correct
28	Correct	100 ms	66640 KB	Output is correct
29	Correct	102 ms	66644 KB	Output is correct
30	Correct	117 ms	66644 KB	Output is correct
31	Correct	109 ms	66556 KB	Output is correct
32	Correct	98 ms	64852 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	0 ms	604 KB	Output is correct
36	Correct	0 ms	348 KB	Output is correct
37	Correct	0 ms	348 KB	Output is correct
38	Runtime error	412 ms	1048576 KB	Execution killed with signal 9
39	Halted	0 ms	0 KB	-

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	333 ms	343124 KB	Output is correct
2	Correct	230 ms	247632 KB	Output is correct
3	Correct	312 ms	343136 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	321 ms	343136 KB	Output is correct
6	Correct	317 ms	343092 KB	Output is correct
7	Correct	328 ms	343260 KB	Output is correct
8	Correct	398 ms	343124 KB	Output is correct
9	Correct	318 ms	343060 KB	Output is correct
10	Correct	299 ms	342948 KB	Output is correct
11	Correct	292 ms	343164 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Runtime error	438 ms	1048576 KB	Execution killed with signal 9
8	Halted	0 ms	0 KB	-

Subtask #7
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	580 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	8 ms	4956 KB	Output is correct
18	Correct	6 ms	4952 KB	Output is correct
19	Correct	6 ms	4984 KB	Output is correct
20	Correct	6 ms	4868 KB	Output is correct
21	Correct	9 ms	4956 KB	Output is correct
22	Correct	8 ms	4956 KB	Output is correct
23	Correct	10 ms	4956 KB	Output is correct
24	Correct	2 ms	2140 KB	Output is correct
25	Correct	121 ms	66456 KB	Output is correct
26	Correct	127 ms	66644 KB	Output is correct
27	Correct	123 ms	66644 KB	Output is correct
28	Correct	100 ms	66640 KB	Output is correct
29	Correct	102 ms	66644 KB	Output is correct
30	Correct	117 ms	66644 KB	Output is correct
31	Correct	109 ms	66556 KB	Output is correct
32	Correct	98 ms	64852 KB	Output is correct
33	Runtime error	412 ms	1048576 KB	Execution killed with signal 9
34	Halted	0 ms	0 KB	-

답안 #1067951

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 7.0 / 7.0

Subtask #3 12.0 / 12.0

Subtask #4 0 / 22.0

Subtask #5 10.0 / 10.0

Subtask #6 0 / 13.0

Subtask #7 0 / 28.0

Subtask #1
8.0 / 8.0

Subtask #2
7.0 / 7.0

Subtask #3
12.0 / 12.0

Subtask #4
0 / 22.0

Subtask #5
10.0 / 10.0

Subtask #6
0 / 13.0

Subtask #7
0 / 28.0