# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
298860 |
2020-09-14T08:25:47 Z |
Aldas25 |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
233084 KB |
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
const int MAXN = 3510, MAXK = 13;
int n, m;
int colMax[MAXN][MAXN][MAXK];
int rowMax[MAXN][MAXN][MAXK];
int lg[MAXN];
void buildST() {
FOR(i, 2, MAXN-1) lg[i] = lg[i/2]+1;
FOR(j, 1, MAXK-1) FOR(k, 0, m-1) for (int i = 0; i + (1<<j) <= n; i++) {
colMax[k][i][j] = max(colMax[k][i][j-1], colMax[k][i + (1<<(j-1))][j-1]);
}
FOR(j, 1, MAXK-1) FOR(k, 0, n-1) for (int i = 0; i + (1<<j) <= m; i++) {
rowMax[k][i][j] = max(rowMax[k][i][j-1], rowMax[k][i + (1<<(j-1))][j-1]);
}
}
int getColMax (int k, int fr, int to) {
int j = lg[to-fr+1];
return max(colMax[k][fr][j], colMax[k][to - (1<<j)+ 1][j]);
}
int getRowMax (int k, int fr, int to) {
int j = lg[to-fr+1];
return max(rowMax[k][fr][j], rowMax[k][to - (1<<j)+ 1][j]);
}
int par[MAXN*MAXN], sz[MAXN*MAXN], mnR[MAXN*MAXN], mxR[MAXN*MAXN], mnC[MAXN*MAXN], mxC[MAXN*MAXN];
int find (int a) {return par[a] = par[a]==a ? a : find(par[a]);}
void unite (int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
par[b] = a;
sz[a] += sz[b];
mnR[a] = min(mnR[a], mnR[b]);
mnC[a] = min(mnC[a], mnC[b]);
mxR[a] = max(mxR[a], mxR[b]);
mxC[a] = max(mxC[a], mxC[b]);
}
int getId (int i, int j) {
return i*m + j;
}
long long sub6(std::vector<std::vector<int> > a) {
FOR(i, 0, n-1) FOR(j, 0, m-1) {
int id = getId(i,j);
par[id] = id;
sz[id] = 1;
mnR[id] = mxR[id] = i;
mnC[id] = mxC[id] = j;
}
FOR(i, 0, n-1) FOR(j, 0, m-1) {
if(a[i][j] == 1) continue;
if (i < n-1 && a[i+1][j] == 0)
unite(getId(i,j), getId(i+1,j));
if (j < m-1 && a[i][j+1] == 0)
unite(getId(i,j), getId(i, j+1));
}
ll ans = 0ll;
FOR(i, 0, n-1) FOR(j, 0, m-1) {
if (a[i][j] == 1) continue;
int id = getId(i,j);
if (find(id) != id) continue;
if (mxR[id] == n-1 || mxC[id] == m-1 || mnR[id] == 0 || mnC[id] == 0) continue;
if (sz[id] == (mxR[id] - mnR[id] + 1) * (mxC[id] - mnC[id] + 1))
ans++;
}
return ans;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n = (int)a.size();
m = (int)a[0].size();
bool s6 = true;
FOR(i, 0 ,n-1) FOR(j, 0, m-1) if (a[i][j] > 1) s6 = false;
if (s6) {
return sub6(a);
}
FOR(i, 0, n-1) FOR(j, 0, m-1) colMax[j][i][0] = rowMax[i][j][0] = a[i][j];
buildST();
/*FOR(r1, 0, n-1) FOR(c1, 0, m-1) FOR(r2, r1, n-1) {
cout << " colMax, col: " << c1 << " ["<<r1<<", "<<r2<<"] mx= " << getColMax(c1, r1, r2) << endl;
}
FOR(r1, 0, n-1) FOR(c1, 0, m-1) FOR(c2, c1, m-1) {
cout << " rowMax, row: " << r1 << " ["<<c1<<", "<<c2<<"] mx= " << getRowMax(r1, c1, c2) << endl;
}*/
ll ans = 0ll;
FOR(r1, 1, n-2) FOR(c1, 1, m-2) FOR(r2, r1, n-2) FOR(c2, c1, m-2) {
bool ok = true;
/*FOR(i, r1, r2) FOR(j, c1, c2) {
int mnH = a[i][c1-1];
mnH = min(mnH, a[i][c2+1]);
mnH = min(mnH, a[r1-1][j]);
mnH = min(mnH, a[r2+1][j]);
if(a[i][j] >= mnH) {
ok = false;
break;
}
}*/
FOR(i, r1, r2) {
int mnH = min(a[i][c1-1], a[i][c2+1]);
int mxH = getRowMax(i, c1, c2);
if (mxH >= mnH) {
ok = false;
break;
}
}
if (ok) {
FOR(j, c1, c2) {
int mnH = min(a[r1-1][j], a[r2+1][j]);
int mxH = getColMax(j, r1, r2);
if(mxH >= mnH) {
ok = false;
break;
}
}
}
if (ok) ans++;
}
return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
ans:
6
4 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
640 KB |
Output is correct |
3 |
Correct |
2 ms |
640 KB |
Output is correct |
4 |
Correct |
2 ms |
640 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
640 KB |
Output is correct |
7 |
Correct |
1 ms |
640 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
640 KB |
Output is correct |
10 |
Correct |
2 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
640 KB |
Output is correct |
12 |
Correct |
2 ms |
640 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
640 KB |
Output is correct |
3 |
Correct |
2 ms |
640 KB |
Output is correct |
4 |
Correct |
2 ms |
640 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
640 KB |
Output is correct |
7 |
Correct |
1 ms |
640 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
640 KB |
Output is correct |
10 |
Correct |
2 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
640 KB |
Output is correct |
12 |
Correct |
2 ms |
640 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
61 ms |
1808 KB |
Output is correct |
18 |
Correct |
61 ms |
1792 KB |
Output is correct |
19 |
Correct |
76 ms |
1792 KB |
Output is correct |
20 |
Correct |
45 ms |
1792 KB |
Output is correct |
21 |
Correct |
44 ms |
1792 KB |
Output is correct |
22 |
Correct |
43 ms |
1792 KB |
Output is correct |
23 |
Correct |
60 ms |
1800 KB |
Output is correct |
24 |
Correct |
12 ms |
1280 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
1 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
640 KB |
Output is correct |
3 |
Correct |
2 ms |
640 KB |
Output is correct |
4 |
Correct |
2 ms |
640 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
640 KB |
Output is correct |
7 |
Correct |
1 ms |
640 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
640 KB |
Output is correct |
10 |
Correct |
2 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
640 KB |
Output is correct |
12 |
Correct |
2 ms |
640 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
61 ms |
1808 KB |
Output is correct |
18 |
Correct |
61 ms |
1792 KB |
Output is correct |
19 |
Correct |
76 ms |
1792 KB |
Output is correct |
20 |
Correct |
45 ms |
1792 KB |
Output is correct |
21 |
Correct |
44 ms |
1792 KB |
Output is correct |
22 |
Correct |
43 ms |
1792 KB |
Output is correct |
23 |
Correct |
60 ms |
1800 KB |
Output is correct |
24 |
Correct |
12 ms |
1280 KB |
Output is correct |
25 |
Correct |
2566 ms |
6712 KB |
Output is correct |
26 |
Correct |
2534 ms |
6776 KB |
Output is correct |
27 |
Correct |
2563 ms |
6936 KB |
Output is correct |
28 |
Correct |
1668 ms |
6536 KB |
Output is correct |
29 |
Correct |
1694 ms |
6644 KB |
Output is correct |
30 |
Correct |
1708 ms |
6796 KB |
Output is correct |
31 |
Correct |
1717 ms |
6760 KB |
Output is correct |
32 |
Correct |
1670 ms |
6720 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
1 ms |
384 KB |
Output is correct |
37 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
640 KB |
Output is correct |
3 |
Correct |
2 ms |
640 KB |
Output is correct |
4 |
Correct |
2 ms |
640 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
640 KB |
Output is correct |
7 |
Correct |
1 ms |
640 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
640 KB |
Output is correct |
10 |
Correct |
2 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
640 KB |
Output is correct |
12 |
Correct |
2 ms |
640 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
61 ms |
1808 KB |
Output is correct |
18 |
Correct |
61 ms |
1792 KB |
Output is correct |
19 |
Correct |
76 ms |
1792 KB |
Output is correct |
20 |
Correct |
45 ms |
1792 KB |
Output is correct |
21 |
Correct |
44 ms |
1792 KB |
Output is correct |
22 |
Correct |
43 ms |
1792 KB |
Output is correct |
23 |
Correct |
60 ms |
1800 KB |
Output is correct |
24 |
Correct |
12 ms |
1280 KB |
Output is correct |
25 |
Correct |
2566 ms |
6712 KB |
Output is correct |
26 |
Correct |
2534 ms |
6776 KB |
Output is correct |
27 |
Correct |
2563 ms |
6936 KB |
Output is correct |
28 |
Correct |
1668 ms |
6536 KB |
Output is correct |
29 |
Correct |
1694 ms |
6644 KB |
Output is correct |
30 |
Correct |
1708 ms |
6796 KB |
Output is correct |
31 |
Correct |
1717 ms |
6760 KB |
Output is correct |
32 |
Correct |
1670 ms |
6720 KB |
Output is correct |
33 |
Execution timed out |
5008 ms |
60792 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
11904 KB |
Output is correct |
2 |
Correct |
35 ms |
10264 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
20 ms |
12032 KB |
Output is correct |
6 |
Correct |
20 ms |
12032 KB |
Output is correct |
7 |
Correct |
20 ms |
12032 KB |
Output is correct |
8 |
Correct |
20 ms |
11904 KB |
Output is correct |
9 |
Correct |
21 ms |
12032 KB |
Output is correct |
10 |
Correct |
6 ms |
11392 KB |
Output is correct |
11 |
Correct |
7 ms |
11648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
182 ms |
102136 KB |
Output is correct |
3 |
Correct |
390 ms |
231800 KB |
Output is correct |
4 |
Correct |
392 ms |
233080 KB |
Output is correct |
5 |
Correct |
398 ms |
233080 KB |
Output is correct |
6 |
Correct |
188 ms |
115192 KB |
Output is correct |
7 |
Correct |
366 ms |
218744 KB |
Output is correct |
8 |
Correct |
390 ms |
233084 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
640 KB |
Output is correct |
3 |
Correct |
2 ms |
640 KB |
Output is correct |
4 |
Correct |
2 ms |
640 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
640 KB |
Output is correct |
7 |
Correct |
1 ms |
640 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
640 KB |
Output is correct |
10 |
Correct |
2 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
640 KB |
Output is correct |
12 |
Correct |
2 ms |
640 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
61 ms |
1808 KB |
Output is correct |
18 |
Correct |
61 ms |
1792 KB |
Output is correct |
19 |
Correct |
76 ms |
1792 KB |
Output is correct |
20 |
Correct |
45 ms |
1792 KB |
Output is correct |
21 |
Correct |
44 ms |
1792 KB |
Output is correct |
22 |
Correct |
43 ms |
1792 KB |
Output is correct |
23 |
Correct |
60 ms |
1800 KB |
Output is correct |
24 |
Correct |
12 ms |
1280 KB |
Output is correct |
25 |
Correct |
2566 ms |
6712 KB |
Output is correct |
26 |
Correct |
2534 ms |
6776 KB |
Output is correct |
27 |
Correct |
2563 ms |
6936 KB |
Output is correct |
28 |
Correct |
1668 ms |
6536 KB |
Output is correct |
29 |
Correct |
1694 ms |
6644 KB |
Output is correct |
30 |
Correct |
1708 ms |
6796 KB |
Output is correct |
31 |
Correct |
1717 ms |
6760 KB |
Output is correct |
32 |
Correct |
1670 ms |
6720 KB |
Output is correct |
33 |
Execution timed out |
5008 ms |
60792 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |