# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
289120 |
2020-09-02T11:22:26 Z |
amiratou |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
124792 KB |
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
typedef long long ll;
const int MX = 2505;
int cl[MX][MX]; // smallest row>i on same column containing one
int nxt[MX][MX]; // furthest col on same row tel que same close
int cum[MX][MX]; // normal cum on columns
int gimme(int col,int a,int b){
return cum[b][col] - (a?cum[a-1][col]:0);
}
ll count_rectangles(vector<vector<int> > a) {
ll ans=0;
int n=sz(a),m=sz(a[0]);
if(n<=3){
if(n<=2)return 0;
for (int i = 1; i < m-1; ++i)
{
if(a[1][i]>=a[1][i-1])continue;
for (int j = i; j < m-1; ++j){
if(a[1][j]>=a[0][j] || a[1][j]>=a[2][j])break;
ans+=((a[1][j]<a[1][j+1]) && (a[1][j]<a[1][i-1]) && (a[1][i]<a[1][j+1]));
}
}
return ans;
}
bool f=1;
for (int j = 0; j < m; ++j)
{
int last=-1;
for (int i = n-1; i >= 0; i--){
if(a[i][j]>1)f=0;
if(a[i][j]){
cl[i][j]=last,last=i;
if((i+1) == cl[i][j])cl[i][j]=-1;
}
else cl[i][j]=-1;
}
}
if(!f){
for (int r1 = 1; r1 <= n-2; ++r1)
for (int r2 = r1; r2 <= n-2; ++r2)
for (int c1 = 1; c1 <= m-2; ++c1)
for (int c2 = c1; c2 <= m-2; ++c2)
{
bool ok=1;
for (int i = r1; i <= r2; ++i){
for (int j = c1; j <= c2; ++j)
if(a[i][j]>=a[i][c1-1] || a[i][j]>=a[i][c2+1] || a[i][j]>=a[r1-1][j] || a[i][j]>=a[r2+1][j]){ok=0;break;}
if(!ok)break;
}
ans+=ok;
}
return ans;
}
for (int i = 0; i < n; ++i){
for (int j = 0; j < m; )
{
if(cl[i][j]==-1){
nxt[i][j]=-1,j++;
continue;
}
int z=j;
while(z<m && cl[i][z]==cl[i][j])
z++;
for (int A = j; A < z; ++A)
nxt[i][A]=z;
j=z;
}
for (int j = 0; j < m; ++j){
cum[i][j]=(!a[i][j]);
if(i)cum[i][j]+=cum[i-1][j];
}
}
for (int i = 0; i < n-2; ++i)
for (int j = 1; j < m-1; ++j)
if(a[i][j] && cl[i][j]!=-1 && !gimme(j-1,i+1,cl[i][j]-1) && nxt[i][j]!=m && !gimme(nxt[i][j],i+1,cl[i][j]-1))
ans++;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
512 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 |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
640 KB |
Output is correct |
20 |
Correct |
1 ms |
640 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 |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
512 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 |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
49 ms |
808 KB |
Output is correct |
18 |
Correct |
48 ms |
768 KB |
Output is correct |
19 |
Correct |
48 ms |
812 KB |
Output is correct |
20 |
Correct |
44 ms |
768 KB |
Output is correct |
21 |
Correct |
52 ms |
768 KB |
Output is correct |
22 |
Correct |
53 ms |
800 KB |
Output is correct |
23 |
Correct |
52 ms |
768 KB |
Output is correct |
24 |
Correct |
14 ms |
768 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
256 KB |
Output is correct |
27 |
Correct |
1 ms |
640 KB |
Output is correct |
28 |
Correct |
1 ms |
640 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 |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
512 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 |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
49 ms |
808 KB |
Output is correct |
18 |
Correct |
48 ms |
768 KB |
Output is correct |
19 |
Correct |
48 ms |
812 KB |
Output is correct |
20 |
Correct |
44 ms |
768 KB |
Output is correct |
21 |
Correct |
52 ms |
768 KB |
Output is correct |
22 |
Correct |
53 ms |
800 KB |
Output is correct |
23 |
Correct |
52 ms |
768 KB |
Output is correct |
24 |
Correct |
14 ms |
768 KB |
Output is correct |
25 |
Correct |
1788 ms |
1860 KB |
Output is correct |
26 |
Correct |
1778 ms |
1912 KB |
Output is correct |
27 |
Correct |
1783 ms |
2040 KB |
Output is correct |
28 |
Correct |
1737 ms |
1664 KB |
Output is correct |
29 |
Correct |
2090 ms |
1784 KB |
Output is correct |
30 |
Correct |
2095 ms |
1912 KB |
Output is correct |
31 |
Correct |
2003 ms |
1912 KB |
Output is correct |
32 |
Correct |
1944 ms |
1916 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
256 KB |
Output is correct |
35 |
Correct |
1 ms |
640 KB |
Output is correct |
36 |
Correct |
1 ms |
640 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 |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
512 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 |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
49 ms |
808 KB |
Output is correct |
18 |
Correct |
48 ms |
768 KB |
Output is correct |
19 |
Correct |
48 ms |
812 KB |
Output is correct |
20 |
Correct |
44 ms |
768 KB |
Output is correct |
21 |
Correct |
52 ms |
768 KB |
Output is correct |
22 |
Correct |
53 ms |
800 KB |
Output is correct |
23 |
Correct |
52 ms |
768 KB |
Output is correct |
24 |
Correct |
14 ms |
768 KB |
Output is correct |
25 |
Correct |
1788 ms |
1860 KB |
Output is correct |
26 |
Correct |
1778 ms |
1912 KB |
Output is correct |
27 |
Correct |
1783 ms |
2040 KB |
Output is correct |
28 |
Correct |
1737 ms |
1664 KB |
Output is correct |
29 |
Correct |
2090 ms |
1784 KB |
Output is correct |
30 |
Correct |
2095 ms |
1912 KB |
Output is correct |
31 |
Correct |
2003 ms |
1912 KB |
Output is correct |
32 |
Correct |
1944 ms |
1916 KB |
Output is correct |
33 |
Execution timed out |
5042 ms |
9208 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
384 KB |
Output is correct |
2 |
Correct |
8 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
165 ms |
59512 KB |
Output is correct |
3 |
Correct |
364 ms |
124028 KB |
Output is correct |
4 |
Correct |
361 ms |
124792 KB |
Output is correct |
5 |
Correct |
357 ms |
124780 KB |
Output is correct |
6 |
Correct |
143 ms |
62840 KB |
Output is correct |
7 |
Correct |
271 ms |
121592 KB |
Output is correct |
8 |
Correct |
283 ms |
124792 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
640 KB |
Output is correct |
12 |
Correct |
1 ms |
640 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 |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
512 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 |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
49 ms |
808 KB |
Output is correct |
18 |
Correct |
48 ms |
768 KB |
Output is correct |
19 |
Correct |
48 ms |
812 KB |
Output is correct |
20 |
Correct |
44 ms |
768 KB |
Output is correct |
21 |
Correct |
52 ms |
768 KB |
Output is correct |
22 |
Correct |
53 ms |
800 KB |
Output is correct |
23 |
Correct |
52 ms |
768 KB |
Output is correct |
24 |
Correct |
14 ms |
768 KB |
Output is correct |
25 |
Correct |
1788 ms |
1860 KB |
Output is correct |
26 |
Correct |
1778 ms |
1912 KB |
Output is correct |
27 |
Correct |
1783 ms |
2040 KB |
Output is correct |
28 |
Correct |
1737 ms |
1664 KB |
Output is correct |
29 |
Correct |
2090 ms |
1784 KB |
Output is correct |
30 |
Correct |
2095 ms |
1912 KB |
Output is correct |
31 |
Correct |
2003 ms |
1912 KB |
Output is correct |
32 |
Correct |
1944 ms |
1916 KB |
Output is correct |
33 |
Execution timed out |
5042 ms |
9208 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |