# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
479592 |
2021-10-12T09:30:45 Z |
peti1234 |
Rectangles (IOI19_rect) |
C++17 |
|
4957 ms |
639764 KB |
#include <bits/stdc++.h>
using namespace std;
const int c=2550;
bool v[c][c], t[c][c];
int n, m, ans, ks, ko, ns, no, mini, db, fel[c][c], le[c][c], bal[c][c], jobb[c][c], cfel[c][c], cle[c][c], cbal[c][c], cjobb[c][c];
set<pair<pair<int, int>, pair<int, int> > > sol;
void add(int ks, int ko, int ns, int no) {
int mini=min({ks, ko, ns, no});
if (mini!=-1 && ks && ko && ns<n-1 && no<m-1 && ks<=ns && ko<=no) {
int sdb=ns-ks+1, odb=no-ko+1;
bool josor=(jobb[ns][ko]==no && cjobb[ns][ko]>=sdb || bal[ns][no]==ko && cbal[ns][no]>=sdb);
bool jooszlop=(le[ks][no]==ns && cle[ks][no]>=odb || fel[ns][no]==ks && cfel[ns][no]>=odb);
if (josor && jooszlop) {
pair<pair<int, int>, pair<int, int> > p={{ks, ko}, {ns, no}};
if (sol.find(p)==sol.end()) {
ans++;
sol.insert(p);
}
}
}
}
long long count_rectangles(vector<vector<int>> sz) {
n=sz.size(), m=sz[0].size();
vector<int> s;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
while(s.size()>0 && sz[i][j]>=sz[i][s.back()]) jobb[i][1+s.back()]=j-1, s.pop_back();
s.push_back(j);
}
while(s.size()>0) jobb[i][1+s.back()]=-1, s.pop_back();
for (int j=m-1; j>=0; j--) {
while(s.size()>0 && sz[i][j]>=sz[i][s.back()]) bal[i][-1+s.back()]=j+1, s.pop_back();
if (j) s.push_back(j);
}
while(s.size()>0) bal[i][-1+s.back()]=-1, s.pop_back();
}
for (int j=0; j<m; j++) {
for (int i=0; i<n; i++) {
while(s.size()>0 && sz[i][j]>=sz[s.back()][j]) le[1+s.back()][j]=i-1, s.pop_back();
s.push_back(i);
}
while(s.size()>0) le[1+s.back()][j]=-1, s.pop_back();
for (int i=n-1; i>=0; i--) {
while(s.size()>0 && sz[i][j]>=sz[s.back()][j]) fel[-1+s.back()][j]=i+1, s.pop_back();
if (i) s.push_back(i);
}
while(s.size()>0) fel[-1+s.back()][j]=-1, s.pop_back();
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (i==0 || j==0 || i==n-1 || j==m-1) {
bal[i][j]=jobb[i][j]=le[i][j]=fel[i][j]=-c;
}
}
}
for (int i=1; i<n-1; i++) {
for (int j=1; j<m-1; j++) {
int pos;
pos=jobb[i][j];
if (pos!=-1) {
if (jobb[i-1][j]==pos) cjobb[i][j]=cjobb[i-1][j];
if (bal[i-1][pos]==j) cjobb[i][j]=cbal[i-1][pos];
cjobb[i][j]++;
}
pos=bal[i][j];
if (pos!=-1) {
if (bal[i-1][j]==pos) cbal[i][j]=cbal[i-1][j];
if (jobb[i-1][pos]==j) cbal[i][j]=cjobb[i-1][pos];
cbal[i][j]++;
}
}
}
for (int j=1; j<m-1; j++) {
for (int i=1; i<n-1; i++) {
int pos;
pos=le[i][j];
if (pos!=-1) {
if (le[i][j-1]==pos) cle[i][j]=cle[i][j-1];
if (fel[pos][j-1]==i) cle[i][j]=cfel[pos][j-1];
cle[i][j]++;
}
pos=fel[i][j];
if (pos!=-1) {
if (fel[i][j-1]==pos) cfel[i][j]=cfel[i][j-1];
if (le[pos][j-1]==i) cfel[i][j]=cle[pos][j-1];
cfel[i][j]++;
}
}
}
for (int i=1; i<n-1; i++) {
for (int j=1; j<m-1; j++) {
int ba=bal[i][j], jo=jobb[i][j], fe=fel[i][j], l=le[i][j];
add(i, j, l, jo), add(i, ba, l, j), add(fe, j, i, jo), add(fe, ba, i, j);
if (jo!=-1) add(i, j, le[i][jo], jo);
if (l!=-1) add(i, j, l, jobb[l][j]);
}
}
return ans;
}
/*
int b1, b2;
vector<vector<int>> b3;
int main()
{
cin >> b1 >> b2;
b3.resize(b1);
for (int i=0; i<b1; i++) for (int j=0; j<b2; j++) {
int x; cin >> x;
b3[i].push_back(x);
}
cout << count_rectangles(b3);
return 0;
}
*/
Compilation message
rect.cpp: In function 'void add(int, int, int, int)':
rect.cpp:13:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
13 | bool josor=(jobb[ns][ko]==no && cjobb[ns][ko]>=sdb || bal[ns][no]==ko && cbal[ns][no]>=sdb);
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:14:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
14 | bool jooszlop=(le[ks][no]==ns && cle[ks][no]>=odb || fel[ns][no]==ks && cfel[ns][no]>=odb);
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
1228 KB |
Output is correct |
3 |
Correct |
1 ms |
1356 KB |
Output is correct |
4 |
Correct |
1 ms |
1356 KB |
Output is correct |
5 |
Correct |
1 ms |
1228 KB |
Output is correct |
6 |
Correct |
1 ms |
1228 KB |
Output is correct |
7 |
Correct |
1 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
1228 KB |
Output is correct |
10 |
Correct |
1 ms |
1228 KB |
Output is correct |
11 |
Correct |
1 ms |
1228 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
588 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
1228 KB |
Output is correct |
20 |
Correct |
1 ms |
1228 KB |
Output is correct |
21 |
Correct |
0 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
1228 KB |
Output is correct |
3 |
Correct |
1 ms |
1356 KB |
Output is correct |
4 |
Correct |
1 ms |
1356 KB |
Output is correct |
5 |
Correct |
1 ms |
1228 KB |
Output is correct |
6 |
Correct |
1 ms |
1228 KB |
Output is correct |
7 |
Correct |
1 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
1228 KB |
Output is correct |
10 |
Correct |
1 ms |
1228 KB |
Output is correct |
11 |
Correct |
1 ms |
1228 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
588 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
1228 KB |
Output is correct |
20 |
Correct |
1 ms |
1228 KB |
Output is correct |
21 |
Correct |
0 ms |
460 KB |
Output is correct |
22 |
Correct |
5 ms |
3404 KB |
Output is correct |
23 |
Correct |
5 ms |
3404 KB |
Output is correct |
24 |
Correct |
4 ms |
3404 KB |
Output is correct |
25 |
Correct |
3 ms |
3148 KB |
Output is correct |
26 |
Correct |
4 ms |
3200 KB |
Output is correct |
27 |
Correct |
4 ms |
3148 KB |
Output is correct |
28 |
Correct |
4 ms |
3148 KB |
Output is correct |
29 |
Correct |
3 ms |
3020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
1228 KB |
Output is correct |
3 |
Correct |
1 ms |
1356 KB |
Output is correct |
4 |
Correct |
1 ms |
1356 KB |
Output is correct |
5 |
Correct |
1 ms |
1228 KB |
Output is correct |
6 |
Correct |
1 ms |
1228 KB |
Output is correct |
7 |
Correct |
1 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
1228 KB |
Output is correct |
10 |
Correct |
1 ms |
1228 KB |
Output is correct |
11 |
Correct |
1 ms |
1228 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
588 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
5 ms |
3404 KB |
Output is correct |
18 |
Correct |
5 ms |
3404 KB |
Output is correct |
19 |
Correct |
4 ms |
3404 KB |
Output is correct |
20 |
Correct |
3 ms |
3148 KB |
Output is correct |
21 |
Correct |
4 ms |
3200 KB |
Output is correct |
22 |
Correct |
4 ms |
3148 KB |
Output is correct |
23 |
Correct |
4 ms |
3148 KB |
Output is correct |
24 |
Correct |
3 ms |
3020 KB |
Output is correct |
25 |
Correct |
0 ms |
332 KB |
Output is correct |
26 |
Correct |
0 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
1228 KB |
Output is correct |
28 |
Correct |
1 ms |
1228 KB |
Output is correct |
29 |
Correct |
0 ms |
460 KB |
Output is correct |
30 |
Correct |
23 ms |
10716 KB |
Output is correct |
31 |
Correct |
21 ms |
10700 KB |
Output is correct |
32 |
Correct |
23 ms |
10700 KB |
Output is correct |
33 |
Correct |
13 ms |
8524 KB |
Output is correct |
34 |
Correct |
17 ms |
9120 KB |
Output is correct |
35 |
Correct |
17 ms |
9064 KB |
Output is correct |
36 |
Correct |
20 ms |
9192 KB |
Output is correct |
37 |
Correct |
17 ms |
9036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
1228 KB |
Output is correct |
3 |
Correct |
1 ms |
1356 KB |
Output is correct |
4 |
Correct |
1 ms |
1356 KB |
Output is correct |
5 |
Correct |
1 ms |
1228 KB |
Output is correct |
6 |
Correct |
1 ms |
1228 KB |
Output is correct |
7 |
Correct |
1 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
1228 KB |
Output is correct |
10 |
Correct |
1 ms |
1228 KB |
Output is correct |
11 |
Correct |
1 ms |
1228 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
588 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
5 ms |
3404 KB |
Output is correct |
18 |
Correct |
5 ms |
3404 KB |
Output is correct |
19 |
Correct |
4 ms |
3404 KB |
Output is correct |
20 |
Correct |
3 ms |
3148 KB |
Output is correct |
21 |
Correct |
4 ms |
3200 KB |
Output is correct |
22 |
Correct |
4 ms |
3148 KB |
Output is correct |
23 |
Correct |
4 ms |
3148 KB |
Output is correct |
24 |
Correct |
3 ms |
3020 KB |
Output is correct |
25 |
Correct |
23 ms |
10716 KB |
Output is correct |
26 |
Correct |
21 ms |
10700 KB |
Output is correct |
27 |
Correct |
23 ms |
10700 KB |
Output is correct |
28 |
Correct |
13 ms |
8524 KB |
Output is correct |
29 |
Correct |
17 ms |
9120 KB |
Output is correct |
30 |
Correct |
17 ms |
9064 KB |
Output is correct |
31 |
Correct |
20 ms |
9192 KB |
Output is correct |
32 |
Correct |
17 ms |
9036 KB |
Output is correct |
33 |
Correct |
0 ms |
332 KB |
Output is correct |
34 |
Correct |
0 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
1228 KB |
Output is correct |
36 |
Correct |
1 ms |
1228 KB |
Output is correct |
37 |
Correct |
0 ms |
460 KB |
Output is correct |
38 |
Correct |
98 ms |
40240 KB |
Output is correct |
39 |
Correct |
91 ms |
39984 KB |
Output is correct |
40 |
Correct |
87 ms |
39992 KB |
Output is correct |
41 |
Correct |
82 ms |
40004 KB |
Output is correct |
42 |
Correct |
314 ms |
72376 KB |
Output is correct |
43 |
Correct |
304 ms |
72388 KB |
Output is correct |
44 |
Correct |
323 ms |
72508 KB |
Output is correct |
45 |
Correct |
289 ms |
67768 KB |
Output is correct |
46 |
Correct |
123 ms |
43192 KB |
Output is correct |
47 |
Correct |
134 ms |
44868 KB |
Output is correct |
48 |
Correct |
192 ms |
52444 KB |
Output is correct |
49 |
Correct |
201 ms |
52408 KB |
Output is correct |
50 |
Correct |
105 ms |
37612 KB |
Output is correct |
51 |
Correct |
95 ms |
26320 KB |
Output is correct |
52 |
Correct |
199 ms |
52292 KB |
Output is correct |
53 |
Correct |
197 ms |
52356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
716 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
2 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
588 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
1228 KB |
Output is correct |
4 |
Correct |
1 ms |
1228 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
588 KB |
Output is correct |
7 |
Correct |
757 ms |
128552 KB |
Output is correct |
8 |
Correct |
1620 ms |
263384 KB |
Output is correct |
9 |
Correct |
1667 ms |
264736 KB |
Output is correct |
10 |
Correct |
1685 ms |
264892 KB |
Output is correct |
11 |
Correct |
468 ms |
122952 KB |
Output is correct |
12 |
Correct |
925 ms |
245864 KB |
Output is correct |
13 |
Correct |
966 ms |
248972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
1228 KB |
Output is correct |
3 |
Correct |
1 ms |
1356 KB |
Output is correct |
4 |
Correct |
1 ms |
1356 KB |
Output is correct |
5 |
Correct |
1 ms |
1228 KB |
Output is correct |
6 |
Correct |
1 ms |
1228 KB |
Output is correct |
7 |
Correct |
1 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
1228 KB |
Output is correct |
10 |
Correct |
1 ms |
1228 KB |
Output is correct |
11 |
Correct |
1 ms |
1228 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
588 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
5 ms |
3404 KB |
Output is correct |
18 |
Correct |
5 ms |
3404 KB |
Output is correct |
19 |
Correct |
4 ms |
3404 KB |
Output is correct |
20 |
Correct |
3 ms |
3148 KB |
Output is correct |
21 |
Correct |
4 ms |
3200 KB |
Output is correct |
22 |
Correct |
4 ms |
3148 KB |
Output is correct |
23 |
Correct |
4 ms |
3148 KB |
Output is correct |
24 |
Correct |
3 ms |
3020 KB |
Output is correct |
25 |
Correct |
23 ms |
10716 KB |
Output is correct |
26 |
Correct |
21 ms |
10700 KB |
Output is correct |
27 |
Correct |
23 ms |
10700 KB |
Output is correct |
28 |
Correct |
13 ms |
8524 KB |
Output is correct |
29 |
Correct |
17 ms |
9120 KB |
Output is correct |
30 |
Correct |
17 ms |
9064 KB |
Output is correct |
31 |
Correct |
20 ms |
9192 KB |
Output is correct |
32 |
Correct |
17 ms |
9036 KB |
Output is correct |
33 |
Correct |
98 ms |
40240 KB |
Output is correct |
34 |
Correct |
91 ms |
39984 KB |
Output is correct |
35 |
Correct |
87 ms |
39992 KB |
Output is correct |
36 |
Correct |
82 ms |
40004 KB |
Output is correct |
37 |
Correct |
314 ms |
72376 KB |
Output is correct |
38 |
Correct |
304 ms |
72388 KB |
Output is correct |
39 |
Correct |
323 ms |
72508 KB |
Output is correct |
40 |
Correct |
289 ms |
67768 KB |
Output is correct |
41 |
Correct |
123 ms |
43192 KB |
Output is correct |
42 |
Correct |
134 ms |
44868 KB |
Output is correct |
43 |
Correct |
192 ms |
52444 KB |
Output is correct |
44 |
Correct |
201 ms |
52408 KB |
Output is correct |
45 |
Correct |
105 ms |
37612 KB |
Output is correct |
46 |
Correct |
95 ms |
26320 KB |
Output is correct |
47 |
Correct |
199 ms |
52292 KB |
Output is correct |
48 |
Correct |
197 ms |
52356 KB |
Output is correct |
49 |
Correct |
2 ms |
716 KB |
Output is correct |
50 |
Correct |
1 ms |
588 KB |
Output is correct |
51 |
Correct |
1 ms |
588 KB |
Output is correct |
52 |
Correct |
1 ms |
332 KB |
Output is correct |
53 |
Correct |
2 ms |
588 KB |
Output is correct |
54 |
Correct |
2 ms |
588 KB |
Output is correct |
55 |
Correct |
2 ms |
588 KB |
Output is correct |
56 |
Correct |
1 ms |
588 KB |
Output is correct |
57 |
Correct |
1 ms |
588 KB |
Output is correct |
58 |
Correct |
1 ms |
332 KB |
Output is correct |
59 |
Correct |
1 ms |
460 KB |
Output is correct |
60 |
Correct |
1 ms |
588 KB |
Output is correct |
61 |
Correct |
757 ms |
128552 KB |
Output is correct |
62 |
Correct |
1620 ms |
263384 KB |
Output is correct |
63 |
Correct |
1667 ms |
264736 KB |
Output is correct |
64 |
Correct |
1685 ms |
264892 KB |
Output is correct |
65 |
Correct |
468 ms |
122952 KB |
Output is correct |
66 |
Correct |
925 ms |
245864 KB |
Output is correct |
67 |
Correct |
966 ms |
248972 KB |
Output is correct |
68 |
Correct |
0 ms |
332 KB |
Output is correct |
69 |
Correct |
0 ms |
332 KB |
Output is correct |
70 |
Correct |
1 ms |
1228 KB |
Output is correct |
71 |
Correct |
1 ms |
1228 KB |
Output is correct |
72 |
Correct |
0 ms |
460 KB |
Output is correct |
73 |
Correct |
1336 ms |
240164 KB |
Output is correct |
74 |
Correct |
1143 ms |
239928 KB |
Output is correct |
75 |
Correct |
1118 ms |
239992 KB |
Output is correct |
76 |
Correct |
1041 ms |
240000 KB |
Output is correct |
77 |
Correct |
4896 ms |
639764 KB |
Output is correct |
78 |
Correct |
1518 ms |
229456 KB |
Output is correct |
79 |
Correct |
1632 ms |
315616 KB |
Output is correct |
80 |
Correct |
2571 ms |
382128 KB |
Output is correct |
81 |
Correct |
1617 ms |
230032 KB |
Output is correct |
82 |
Correct |
2257 ms |
346440 KB |
Output is correct |
83 |
Correct |
2807 ms |
383300 KB |
Output is correct |
84 |
Correct |
1496 ms |
229284 KB |
Output is correct |
85 |
Correct |
2595 ms |
382404 KB |
Output is correct |
86 |
Correct |
2501 ms |
371780 KB |
Output is correct |
87 |
Correct |
2741 ms |
461668 KB |
Output is correct |
88 |
Correct |
4954 ms |
639508 KB |
Output is correct |
89 |
Correct |
4927 ms |
639716 KB |
Output is correct |
90 |
Correct |
4957 ms |
639744 KB |
Output is correct |