# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
603367 |
2022-07-24T05:32:39 Z |
SeDunion |
Rectangles (IOI19_rect) |
C++17 |
|
671 ms |
111048 KB |
#include "rect.h"
#include<iostream>
#include<vector>
using namespace std;
using ll = long long;
const int N = 202;
int gr[N][N][N];
int gc[N][N][N];
ll count_rectangles(vector<vector<int>>a) {
int n = a.size(), m = a[0].size();
ll ans = 0;
for (int r = 1 ; r < n - 1 ; ++ r) {
for (int c1 = 1 ; c1 < m - 1 ; ++ c1) {
int mx = 0;
for (int c2 = c1 ; c2 < m - 1 ; ++ c2) {
mx = max(mx, a[r][c2]);
if (mx < a[r][c1 - 1] && mx < a[r][c2 + 1]) {
gr[r][c1][c2] = 1;
}
}
}
}
for (int c = 1 ; c < m - 1 ; ++ c) {
for (int r1 = 1 ; r1 < n - 1 ; ++ r1) {
int mx = 0;
for (int r2 = r1 ; r2 < n - 1 ; ++ r2) {
mx = max(mx, a[r2][c]);
if (mx < a[r1 - 1][c] && mx < a[r2 + 1][c]) {
gc[c][r1][r2] = 1;
}
}
}
}
for (int r = 1 ; r < n - 1 ; ++ r) {
for (int c1 = 1 ; c1 < m - 1 ; ++ c1) {
for (int c2 = c1 ; c2 < m - 1 ; ++ c2) {
gr[r][c1][c2] += gr[r-1][c1][c2];
}
}
}
for (int c = 1 ; c < m - 1 ; ++ c) {
for (int r1 = 1 ; r1 < n - 1 ; ++ r1) {
for (int r2 = r1 ; r2 < n - 1 ; ++ r2) {
gc[c][r1][r2] += gc[c-1][r1][r2];
}
}
}
for (int r1 = 1 ; r1 < n - 1 ; ++ r1) {
for (int r2 = r1 ; r2 < n - 1 ; ++ r2) {
for (int c1 = 1 ; c1 < m - 1 ; ++ c1) {
for (int c2 = c1 ; c2 < m - 1; ++ c2) {
int sr = gr[r2][c1][c2] - gr[r1-1][c1][c2];
int sc = gc[c2][r1][r2] - gc[c1-1][r1][r2];
if (sr == r2 - r1 + 1 && sc == c2 - c1 + 1) {
ans++;
}
}
}
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1748 KB |
Output is correct |
3 |
Correct |
2 ms |
1748 KB |
Output is correct |
4 |
Correct |
2 ms |
1748 KB |
Output is correct |
5 |
Correct |
1 ms |
1748 KB |
Output is correct |
6 |
Correct |
1 ms |
1748 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1748 KB |
Output is correct |
10 |
Correct |
1 ms |
1748 KB |
Output is correct |
11 |
Correct |
1 ms |
1748 KB |
Output is correct |
12 |
Correct |
1 ms |
1748 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
1748 KB |
Output is correct |
20 |
Correct |
1 ms |
980 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1748 KB |
Output is correct |
3 |
Correct |
2 ms |
1748 KB |
Output is correct |
4 |
Correct |
2 ms |
1748 KB |
Output is correct |
5 |
Correct |
1 ms |
1748 KB |
Output is correct |
6 |
Correct |
1 ms |
1748 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1748 KB |
Output is correct |
10 |
Correct |
1 ms |
1748 KB |
Output is correct |
11 |
Correct |
1 ms |
1748 KB |
Output is correct |
12 |
Correct |
1 ms |
1748 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
1748 KB |
Output is correct |
20 |
Correct |
1 ms |
980 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
22 ms |
10452 KB |
Output is correct |
23 |
Correct |
18 ms |
10612 KB |
Output is correct |
24 |
Correct |
18 ms |
10608 KB |
Output is correct |
25 |
Correct |
23 ms |
10452 KB |
Output is correct |
26 |
Correct |
18 ms |
10436 KB |
Output is correct |
27 |
Correct |
17 ms |
10452 KB |
Output is correct |
28 |
Correct |
17 ms |
10580 KB |
Output is correct |
29 |
Correct |
6 ms |
5480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1748 KB |
Output is correct |
3 |
Correct |
2 ms |
1748 KB |
Output is correct |
4 |
Correct |
2 ms |
1748 KB |
Output is correct |
5 |
Correct |
1 ms |
1748 KB |
Output is correct |
6 |
Correct |
1 ms |
1748 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1748 KB |
Output is correct |
10 |
Correct |
1 ms |
1748 KB |
Output is correct |
11 |
Correct |
1 ms |
1748 KB |
Output is correct |
12 |
Correct |
1 ms |
1748 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
22 ms |
10452 KB |
Output is correct |
18 |
Correct |
18 ms |
10612 KB |
Output is correct |
19 |
Correct |
18 ms |
10608 KB |
Output is correct |
20 |
Correct |
23 ms |
10452 KB |
Output is correct |
21 |
Correct |
18 ms |
10436 KB |
Output is correct |
22 |
Correct |
17 ms |
10452 KB |
Output is correct |
23 |
Correct |
17 ms |
10580 KB |
Output is correct |
24 |
Correct |
6 ms |
5480 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
1748 KB |
Output is correct |
28 |
Correct |
1 ms |
980 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
605 ms |
64088 KB |
Output is correct |
31 |
Correct |
545 ms |
64080 KB |
Output is correct |
32 |
Correct |
556 ms |
64156 KB |
Output is correct |
33 |
Correct |
552 ms |
63940 KB |
Output is correct |
34 |
Correct |
518 ms |
64004 KB |
Output is correct |
35 |
Correct |
515 ms |
64164 KB |
Output is correct |
36 |
Correct |
561 ms |
64120 KB |
Output is correct |
37 |
Correct |
524 ms |
63528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1748 KB |
Output is correct |
3 |
Correct |
2 ms |
1748 KB |
Output is correct |
4 |
Correct |
2 ms |
1748 KB |
Output is correct |
5 |
Correct |
1 ms |
1748 KB |
Output is correct |
6 |
Correct |
1 ms |
1748 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1748 KB |
Output is correct |
10 |
Correct |
1 ms |
1748 KB |
Output is correct |
11 |
Correct |
1 ms |
1748 KB |
Output is correct |
12 |
Correct |
1 ms |
1748 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
22 ms |
10452 KB |
Output is correct |
18 |
Correct |
18 ms |
10612 KB |
Output is correct |
19 |
Correct |
18 ms |
10608 KB |
Output is correct |
20 |
Correct |
23 ms |
10452 KB |
Output is correct |
21 |
Correct |
18 ms |
10436 KB |
Output is correct |
22 |
Correct |
17 ms |
10452 KB |
Output is correct |
23 |
Correct |
17 ms |
10580 KB |
Output is correct |
24 |
Correct |
6 ms |
5480 KB |
Output is correct |
25 |
Correct |
605 ms |
64088 KB |
Output is correct |
26 |
Correct |
545 ms |
64080 KB |
Output is correct |
27 |
Correct |
556 ms |
64156 KB |
Output is correct |
28 |
Correct |
552 ms |
63940 KB |
Output is correct |
29 |
Correct |
518 ms |
64004 KB |
Output is correct |
30 |
Correct |
515 ms |
64164 KB |
Output is correct |
31 |
Correct |
561 ms |
64120 KB |
Output is correct |
32 |
Correct |
524 ms |
63528 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
1748 KB |
Output is correct |
36 |
Correct |
1 ms |
980 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Runtime error |
110 ms |
45256 KB |
Execution killed with signal 11 |
39 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
12 ms |
7876 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
1748 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
468 KB |
Output is correct |
7 |
Runtime error |
671 ms |
111048 KB |
Execution killed with signal 11 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1748 KB |
Output is correct |
3 |
Correct |
2 ms |
1748 KB |
Output is correct |
4 |
Correct |
2 ms |
1748 KB |
Output is correct |
5 |
Correct |
1 ms |
1748 KB |
Output is correct |
6 |
Correct |
1 ms |
1748 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1748 KB |
Output is correct |
10 |
Correct |
1 ms |
1748 KB |
Output is correct |
11 |
Correct |
1 ms |
1748 KB |
Output is correct |
12 |
Correct |
1 ms |
1748 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
22 ms |
10452 KB |
Output is correct |
18 |
Correct |
18 ms |
10612 KB |
Output is correct |
19 |
Correct |
18 ms |
10608 KB |
Output is correct |
20 |
Correct |
23 ms |
10452 KB |
Output is correct |
21 |
Correct |
18 ms |
10436 KB |
Output is correct |
22 |
Correct |
17 ms |
10452 KB |
Output is correct |
23 |
Correct |
17 ms |
10580 KB |
Output is correct |
24 |
Correct |
6 ms |
5480 KB |
Output is correct |
25 |
Correct |
605 ms |
64088 KB |
Output is correct |
26 |
Correct |
545 ms |
64080 KB |
Output is correct |
27 |
Correct |
556 ms |
64156 KB |
Output is correct |
28 |
Correct |
552 ms |
63940 KB |
Output is correct |
29 |
Correct |
518 ms |
64004 KB |
Output is correct |
30 |
Correct |
515 ms |
64164 KB |
Output is correct |
31 |
Correct |
561 ms |
64120 KB |
Output is correct |
32 |
Correct |
524 ms |
63528 KB |
Output is correct |
33 |
Runtime error |
110 ms |
45256 KB |
Execution killed with signal 11 |
34 |
Halted |
0 ms |
0 KB |
- |