# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
409163 |
2021-05-20T09:38:56 Z |
idk321 |
Rectangles (IOI19_rect) |
C++17 |
|
5000 ms |
268428 KB |
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int>> a;
int n, m;
long long count_rectangles(std::vector<std::vector<int> > A) {
a = A;
n = a.size();
m = a[0].size();
bool allSmall = true;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (a[i][j] > 1) allSmall = false;
}
}
if (allSmall)
{
vector<vector<int>> left(n, vector<int>(m));
vector<vector<int>> down(n, vector<int>(m));
vector<vector<int>> pref(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++)
{
int sum = 0;
for (int j = 1; j <= m; j++)
{
sum += a[i - 1][j - 1];
pref[i][j] = pref[i - 1][j] + sum;
}
}
for (int i = 1; i < n - 1; i++)
{
for (int j = m - 2; j >= 1; j--)
{
if (j == m - 2)
{
left[i][j] = j;
} else
{
if (a[i][j + 1] == 1)
{
left[i][j] = j;
} else
{
left[i][j] = left[i][j + 1];
}
}
}
}
for (int j = 1; j < m - 1; j++)
{
for (int i = n - 2; i >= 1; i--)
{
if (i == n - 2)
{
down[i][j] = i;
} else
{
if (a[i + 1][j] == 1)
{
down[i][j] = i;
} else
{
down[i][j] = down[i + 1][j];
}
}
}
}
int res = 0;
for (int i = 1; i < n - 1; i++)
{
for (int j = 1; j < m - 1; j++)
{
int i2 = down[i][j];
int j2 = left[i][j];
int sum1 = pref[i2 + 1][j2 + 1] - pref[i2 + 1][j] - pref[i][j2 + 1] + pref[i][j];
int sum2 = pref[i2 + 2][j2 + 2] - pref[i2 + 2][j - 1] - pref[i - 1][j2 + 2] + pref[i - 1][j - 1];
sum2 -= a[i2 + 1][j2 + 1];
sum2 -= a[i2 + 1][j - 1];
sum2 -= a[i - 1][j2 + 1];
sum2 -= a[i - 1][j - 1];
if (sum1 == 0 && sum2 == (i2 - i + 1) * 2 + (j2 - j + 1) * 2) res++;
}
}
return res;
} else
{
ll res = 0;
vector<vector<vector<int>>> goodVer(n, vector<vector<int>>(m));
for (int j = 0; j < m; j++)
{
for (int i = 0; i < n - 2; i++)
{
int cmax = 0;
for (int k = i + 2; k < n; k++)
{
cmax = max(cmax, a[k - 1][j]);
if (cmax < a[i][j] && cmax < a[k][j])
{
goodVer[i][j].push_back(k);
}
}
}
}
vector<vector<int>> goDown(m, vector<int>(m));
for (int i = n - 2; i >= 0; i--)
{
vector<vector<int>> newGoDown(m, vector<int>(m));
for (int j = 0; j < m - 2; j++)
{
int cmax = 0;
for (int k = j + 2; k < m; k++)
{
cmax = max(cmax, a[i + 1][k - 1]);
if (cmax < a[i + 1][j] && cmax < a[i + 1][k])
{
if (i + 1 != n - 1) newGoDown[j][k] = goDown[j][k] + 1;
else newGoDown[j][k] = 1;
}
}
}
goDown = newGoDown;
for (int j = 0; j < m; j++)
{
deque<int> atHeight;
for (int k = j + 1; k < m - 1; k++)
{
if (k == j + 1)
{
for (int x : goodVer[i][k])
{
atHeight.push_back(x);
}
} else
{
auto it = atHeight.begin();
auto it2 = goodVer[i][k].begin();
while (true)
{
if (it == atHeight.end()) break;
if (it2 == goodVer[i][k].end())
{
it = atHeight.erase(it);
} else
{
if (*it == *it2)
{
it++;
it2++;
} else
{
if (*it > *it2)
{
it2++;
} else it = atHeight.erase(it);
}
}
}
}
for (int num : atHeight)
{
if (num <= i + goDown[j][k + 1] + 1) res++;
}
}
}
}
return res;
}
return 1;
}
/*
5 5
0 1 1 1 0
1 0 1 0 1
1 0 1 0 1
1 0 1 0 1
0 1 1 1 0
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
284 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
284 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
284 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
284 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
6 ms |
716 KB |
Output is correct |
23 |
Correct |
6 ms |
716 KB |
Output is correct |
24 |
Correct |
6 ms |
812 KB |
Output is correct |
25 |
Correct |
4 ms |
588 KB |
Output is correct |
26 |
Correct |
5 ms |
684 KB |
Output is correct |
27 |
Correct |
5 ms |
588 KB |
Output is correct |
28 |
Correct |
5 ms |
588 KB |
Output is correct |
29 |
Correct |
3 ms |
424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
284 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
6 ms |
716 KB |
Output is correct |
18 |
Correct |
6 ms |
716 KB |
Output is correct |
19 |
Correct |
6 ms |
812 KB |
Output is correct |
20 |
Correct |
4 ms |
588 KB |
Output is correct |
21 |
Correct |
5 ms |
684 KB |
Output is correct |
22 |
Correct |
5 ms |
588 KB |
Output is correct |
23 |
Correct |
5 ms |
588 KB |
Output is correct |
24 |
Correct |
3 ms |
424 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
204 KB |
Output is correct |
28 |
Correct |
1 ms |
284 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
60 ms |
3380 KB |
Output is correct |
31 |
Correct |
59 ms |
3392 KB |
Output is correct |
32 |
Correct |
62 ms |
3404 KB |
Output is correct |
33 |
Correct |
44 ms |
2508 KB |
Output is correct |
34 |
Correct |
47 ms |
2788 KB |
Output is correct |
35 |
Correct |
47 ms |
2788 KB |
Output is correct |
36 |
Correct |
47 ms |
2756 KB |
Output is correct |
37 |
Correct |
46 ms |
2716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
284 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
6 ms |
716 KB |
Output is correct |
18 |
Correct |
6 ms |
716 KB |
Output is correct |
19 |
Correct |
6 ms |
812 KB |
Output is correct |
20 |
Correct |
4 ms |
588 KB |
Output is correct |
21 |
Correct |
5 ms |
684 KB |
Output is correct |
22 |
Correct |
5 ms |
588 KB |
Output is correct |
23 |
Correct |
5 ms |
588 KB |
Output is correct |
24 |
Correct |
3 ms |
424 KB |
Output is correct |
25 |
Correct |
60 ms |
3380 KB |
Output is correct |
26 |
Correct |
59 ms |
3392 KB |
Output is correct |
27 |
Correct |
62 ms |
3404 KB |
Output is correct |
28 |
Correct |
44 ms |
2508 KB |
Output is correct |
29 |
Correct |
47 ms |
2788 KB |
Output is correct |
30 |
Correct |
47 ms |
2788 KB |
Output is correct |
31 |
Correct |
47 ms |
2756 KB |
Output is correct |
32 |
Correct |
46 ms |
2716 KB |
Output is correct |
33 |
Correct |
1 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
204 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
1 ms |
284 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
1964 ms |
32468 KB |
Output is correct |
39 |
Correct |
1994 ms |
32548 KB |
Output is correct |
40 |
Correct |
1972 ms |
26320 KB |
Output is correct |
41 |
Correct |
1941 ms |
26428 KB |
Output is correct |
42 |
Correct |
2982 ms |
40312 KB |
Output is correct |
43 |
Correct |
3013 ms |
40292 KB |
Output is correct |
44 |
Correct |
2983 ms |
40588 KB |
Output is correct |
45 |
Correct |
2828 ms |
38632 KB |
Output is correct |
46 |
Correct |
25 ms |
12876 KB |
Output is correct |
47 |
Correct |
1967 ms |
27968 KB |
Output is correct |
48 |
Correct |
2025 ms |
31420 KB |
Output is correct |
49 |
Correct |
2025 ms |
33468 KB |
Output is correct |
50 |
Correct |
661 ms |
15864 KB |
Output is correct |
51 |
Correct |
870 ms |
18692 KB |
Output is correct |
52 |
Correct |
2063 ms |
31660 KB |
Output is correct |
53 |
Correct |
2122 ms |
32592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
49760 KB |
Output is correct |
2 |
Correct |
67 ms |
35952 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
73 ms |
49640 KB |
Output is correct |
6 |
Correct |
76 ms |
49688 KB |
Output is correct |
7 |
Correct |
75 ms |
49696 KB |
Output is correct |
8 |
Correct |
72 ms |
49644 KB |
Output is correct |
9 |
Correct |
80 ms |
49700 KB |
Output is correct |
10 |
Correct |
13 ms |
24852 KB |
Output is correct |
11 |
Correct |
41 ms |
49600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
284 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
171 ms |
67728 KB |
Output is correct |
8 |
Correct |
394 ms |
146872 KB |
Output is correct |
9 |
Correct |
376 ms |
147580 KB |
Output is correct |
10 |
Correct |
374 ms |
147644 KB |
Output is correct |
11 |
Correct |
155 ms |
72900 KB |
Output is correct |
12 |
Correct |
301 ms |
138380 KB |
Output is correct |
13 |
Correct |
316 ms |
147624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
284 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
6 ms |
716 KB |
Output is correct |
18 |
Correct |
6 ms |
716 KB |
Output is correct |
19 |
Correct |
6 ms |
812 KB |
Output is correct |
20 |
Correct |
4 ms |
588 KB |
Output is correct |
21 |
Correct |
5 ms |
684 KB |
Output is correct |
22 |
Correct |
5 ms |
588 KB |
Output is correct |
23 |
Correct |
5 ms |
588 KB |
Output is correct |
24 |
Correct |
3 ms |
424 KB |
Output is correct |
25 |
Correct |
60 ms |
3380 KB |
Output is correct |
26 |
Correct |
59 ms |
3392 KB |
Output is correct |
27 |
Correct |
62 ms |
3404 KB |
Output is correct |
28 |
Correct |
44 ms |
2508 KB |
Output is correct |
29 |
Correct |
47 ms |
2788 KB |
Output is correct |
30 |
Correct |
47 ms |
2788 KB |
Output is correct |
31 |
Correct |
47 ms |
2756 KB |
Output is correct |
32 |
Correct |
46 ms |
2716 KB |
Output is correct |
33 |
Correct |
1964 ms |
32468 KB |
Output is correct |
34 |
Correct |
1994 ms |
32548 KB |
Output is correct |
35 |
Correct |
1972 ms |
26320 KB |
Output is correct |
36 |
Correct |
1941 ms |
26428 KB |
Output is correct |
37 |
Correct |
2982 ms |
40312 KB |
Output is correct |
38 |
Correct |
3013 ms |
40292 KB |
Output is correct |
39 |
Correct |
2983 ms |
40588 KB |
Output is correct |
40 |
Correct |
2828 ms |
38632 KB |
Output is correct |
41 |
Correct |
25 ms |
12876 KB |
Output is correct |
42 |
Correct |
1967 ms |
27968 KB |
Output is correct |
43 |
Correct |
2025 ms |
31420 KB |
Output is correct |
44 |
Correct |
2025 ms |
33468 KB |
Output is correct |
45 |
Correct |
661 ms |
15864 KB |
Output is correct |
46 |
Correct |
870 ms |
18692 KB |
Output is correct |
47 |
Correct |
2063 ms |
31660 KB |
Output is correct |
48 |
Correct |
2122 ms |
32592 KB |
Output is correct |
49 |
Correct |
83 ms |
49760 KB |
Output is correct |
50 |
Correct |
67 ms |
35952 KB |
Output is correct |
51 |
Correct |
1 ms |
460 KB |
Output is correct |
52 |
Correct |
1 ms |
204 KB |
Output is correct |
53 |
Correct |
73 ms |
49640 KB |
Output is correct |
54 |
Correct |
76 ms |
49688 KB |
Output is correct |
55 |
Correct |
75 ms |
49696 KB |
Output is correct |
56 |
Correct |
72 ms |
49644 KB |
Output is correct |
57 |
Correct |
80 ms |
49700 KB |
Output is correct |
58 |
Correct |
13 ms |
24852 KB |
Output is correct |
59 |
Correct |
41 ms |
49600 KB |
Output is correct |
60 |
Correct |
1 ms |
204 KB |
Output is correct |
61 |
Correct |
171 ms |
67728 KB |
Output is correct |
62 |
Correct |
394 ms |
146872 KB |
Output is correct |
63 |
Correct |
376 ms |
147580 KB |
Output is correct |
64 |
Correct |
374 ms |
147644 KB |
Output is correct |
65 |
Correct |
155 ms |
72900 KB |
Output is correct |
66 |
Correct |
301 ms |
138380 KB |
Output is correct |
67 |
Correct |
316 ms |
147624 KB |
Output is correct |
68 |
Correct |
1 ms |
204 KB |
Output is correct |
69 |
Correct |
1 ms |
204 KB |
Output is correct |
70 |
Correct |
1 ms |
204 KB |
Output is correct |
71 |
Correct |
1 ms |
284 KB |
Output is correct |
72 |
Correct |
1 ms |
204 KB |
Output is correct |
73 |
Execution timed out |
5073 ms |
268428 KB |
Time limit exceeded |
74 |
Halted |
0 ms |
0 KB |
- |