#include "rect.h"
#include<iostream>
#include<vector>
#include<bitset>
#include<cassert>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=s; --i)
#define PB push_back
const int MAXN = 800;
bitset<MAXN> mask[MAXN][MAXN]; // column, start row
bitset<MAXN> one("1"), full;
int n, m, arr[MAXN][MAXN], brr[MAXN][MAXN];
int far[MAXN][MAXN][MAXN]; // row, l, r
void calc1(){
dforn(row, n){
forsn(i, 1, m-1){
int mx = -1;
forsn(j, i, m-1){
mx = max(mx, arr[row][j]);
if(mx<arr[row][i-1] && mx<arr[row][j+1]){
far[row][i][j]=far[row+1][i][j];
}
else far[row][i][j]=row;
}
}
}
}
void calc2(){
forn(col, m){
forsn(i, 1, n-1){
int mx = -1;
forsn(j, i, n-1){
mx = max(mx, brr[col][j]);
if(mx<brr[col][i-1] && mx<brr[col][j+1]){
mask[i][col]|=(one<<j);
}
}
}
}
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n=(int)a.size(), m=(int)a[0].size();
assert(n<MAXN-4);
assert(m<MAXN-4);
forn(i, MAXN-3) full|=(one<<i);
forn(i, n) forn(j, m) brr[j][i]=arr[i][j]=a[i][j];
forn(i, m) forn(j, m) far[n][i][j]=n;
calc1();
calc2();
ll ans=0;
forsn(row, 1, n-1){
forsn(i, 1, m-1){
bitset<MAXN> bt("0");
bt|=full;
forsn(j, i, m-1){
bt&=mask[row][j];
ans+=(bt&(full>>(MAXN-3-far[row][i][j]))).count();
}
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
3540 KB |
Output is correct |
3 |
Correct |
2 ms |
3540 KB |
Output is correct |
4 |
Correct |
2 ms |
3540 KB |
Output is correct |
5 |
Correct |
2 ms |
3288 KB |
Output is correct |
6 |
Correct |
3 ms |
3540 KB |
Output is correct |
7 |
Correct |
1 ms |
1748 KB |
Output is correct |
8 |
Correct |
1 ms |
1748 KB |
Output is correct |
9 |
Correct |
2 ms |
3540 KB |
Output is correct |
10 |
Correct |
2 ms |
3540 KB |
Output is correct |
11 |
Correct |
2 ms |
3540 KB |
Output is correct |
12 |
Correct |
2 ms |
3540 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
2 ms |
3540 KB |
Output is correct |
20 |
Correct |
1 ms |
1748 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
3540 KB |
Output is correct |
3 |
Correct |
2 ms |
3540 KB |
Output is correct |
4 |
Correct |
2 ms |
3540 KB |
Output is correct |
5 |
Correct |
2 ms |
3288 KB |
Output is correct |
6 |
Correct |
3 ms |
3540 KB |
Output is correct |
7 |
Correct |
1 ms |
1748 KB |
Output is correct |
8 |
Correct |
1 ms |
1748 KB |
Output is correct |
9 |
Correct |
2 ms |
3540 KB |
Output is correct |
10 |
Correct |
2 ms |
3540 KB |
Output is correct |
11 |
Correct |
2 ms |
3540 KB |
Output is correct |
12 |
Correct |
2 ms |
3540 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
2 ms |
3540 KB |
Output is correct |
20 |
Correct |
1 ms |
1748 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
21 ms |
21940 KB |
Output is correct |
23 |
Correct |
21 ms |
21944 KB |
Output is correct |
24 |
Correct |
21 ms |
21948 KB |
Output is correct |
25 |
Correct |
25 ms |
21940 KB |
Output is correct |
26 |
Correct |
21 ms |
21684 KB |
Output is correct |
27 |
Correct |
23 ms |
21588 KB |
Output is correct |
28 |
Correct |
22 ms |
21932 KB |
Output is correct |
29 |
Correct |
8 ms |
11348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
3540 KB |
Output is correct |
3 |
Correct |
2 ms |
3540 KB |
Output is correct |
4 |
Correct |
2 ms |
3540 KB |
Output is correct |
5 |
Correct |
2 ms |
3288 KB |
Output is correct |
6 |
Correct |
3 ms |
3540 KB |
Output is correct |
7 |
Correct |
1 ms |
1748 KB |
Output is correct |
8 |
Correct |
1 ms |
1748 KB |
Output is correct |
9 |
Correct |
2 ms |
3540 KB |
Output is correct |
10 |
Correct |
2 ms |
3540 KB |
Output is correct |
11 |
Correct |
2 ms |
3540 KB |
Output is correct |
12 |
Correct |
2 ms |
3540 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
21 ms |
21940 KB |
Output is correct |
18 |
Correct |
21 ms |
21944 KB |
Output is correct |
19 |
Correct |
21 ms |
21948 KB |
Output is correct |
20 |
Correct |
25 ms |
21940 KB |
Output is correct |
21 |
Correct |
21 ms |
21684 KB |
Output is correct |
22 |
Correct |
23 ms |
21588 KB |
Output is correct |
23 |
Correct |
22 ms |
21932 KB |
Output is correct |
24 |
Correct |
8 ms |
11348 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
2 ms |
3540 KB |
Output is correct |
28 |
Correct |
1 ms |
1748 KB |
Output is correct |
29 |
Correct |
0 ms |
340 KB |
Output is correct |
30 |
Correct |
257 ms |
132212 KB |
Output is correct |
31 |
Correct |
299 ms |
132284 KB |
Output is correct |
32 |
Correct |
260 ms |
132272 KB |
Output is correct |
33 |
Correct |
256 ms |
132264 KB |
Output is correct |
34 |
Correct |
261 ms |
132380 KB |
Output is correct |
35 |
Correct |
262 ms |
132332 KB |
Output is correct |
36 |
Correct |
261 ms |
132216 KB |
Output is correct |
37 |
Correct |
252 ms |
129884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
3540 KB |
Output is correct |
3 |
Correct |
2 ms |
3540 KB |
Output is correct |
4 |
Correct |
2 ms |
3540 KB |
Output is correct |
5 |
Correct |
2 ms |
3288 KB |
Output is correct |
6 |
Correct |
3 ms |
3540 KB |
Output is correct |
7 |
Correct |
1 ms |
1748 KB |
Output is correct |
8 |
Correct |
1 ms |
1748 KB |
Output is correct |
9 |
Correct |
2 ms |
3540 KB |
Output is correct |
10 |
Correct |
2 ms |
3540 KB |
Output is correct |
11 |
Correct |
2 ms |
3540 KB |
Output is correct |
12 |
Correct |
2 ms |
3540 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
21 ms |
21940 KB |
Output is correct |
18 |
Correct |
21 ms |
21944 KB |
Output is correct |
19 |
Correct |
21 ms |
21948 KB |
Output is correct |
20 |
Correct |
25 ms |
21940 KB |
Output is correct |
21 |
Correct |
21 ms |
21684 KB |
Output is correct |
22 |
Correct |
23 ms |
21588 KB |
Output is correct |
23 |
Correct |
22 ms |
21932 KB |
Output is correct |
24 |
Correct |
8 ms |
11348 KB |
Output is correct |
25 |
Correct |
257 ms |
132212 KB |
Output is correct |
26 |
Correct |
299 ms |
132284 KB |
Output is correct |
27 |
Correct |
260 ms |
132272 KB |
Output is correct |
28 |
Correct |
256 ms |
132264 KB |
Output is correct |
29 |
Correct |
261 ms |
132380 KB |
Output is correct |
30 |
Correct |
262 ms |
132332 KB |
Output is correct |
31 |
Correct |
261 ms |
132216 KB |
Output is correct |
32 |
Correct |
252 ms |
129884 KB |
Output is correct |
33 |
Correct |
0 ms |
340 KB |
Output is correct |
34 |
Correct |
0 ms |
340 KB |
Output is correct |
35 |
Correct |
2 ms |
3540 KB |
Output is correct |
36 |
Correct |
1 ms |
1748 KB |
Output is correct |
37 |
Correct |
0 ms |
340 KB |
Output is correct |
38 |
Runtime error |
402 ms |
1048576 KB |
Execution killed with signal 9 |
39 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
27 ms |
468 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
3540 KB |
Output is correct |
4 |
Correct |
1 ms |
1748 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Runtime error |
54 ms |
22884 KB |
Execution killed with signal 6 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
3540 KB |
Output is correct |
3 |
Correct |
2 ms |
3540 KB |
Output is correct |
4 |
Correct |
2 ms |
3540 KB |
Output is correct |
5 |
Correct |
2 ms |
3288 KB |
Output is correct |
6 |
Correct |
3 ms |
3540 KB |
Output is correct |
7 |
Correct |
1 ms |
1748 KB |
Output is correct |
8 |
Correct |
1 ms |
1748 KB |
Output is correct |
9 |
Correct |
2 ms |
3540 KB |
Output is correct |
10 |
Correct |
2 ms |
3540 KB |
Output is correct |
11 |
Correct |
2 ms |
3540 KB |
Output is correct |
12 |
Correct |
2 ms |
3540 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
21 ms |
21940 KB |
Output is correct |
18 |
Correct |
21 ms |
21944 KB |
Output is correct |
19 |
Correct |
21 ms |
21948 KB |
Output is correct |
20 |
Correct |
25 ms |
21940 KB |
Output is correct |
21 |
Correct |
21 ms |
21684 KB |
Output is correct |
22 |
Correct |
23 ms |
21588 KB |
Output is correct |
23 |
Correct |
22 ms |
21932 KB |
Output is correct |
24 |
Correct |
8 ms |
11348 KB |
Output is correct |
25 |
Correct |
257 ms |
132212 KB |
Output is correct |
26 |
Correct |
299 ms |
132284 KB |
Output is correct |
27 |
Correct |
260 ms |
132272 KB |
Output is correct |
28 |
Correct |
256 ms |
132264 KB |
Output is correct |
29 |
Correct |
261 ms |
132380 KB |
Output is correct |
30 |
Correct |
262 ms |
132332 KB |
Output is correct |
31 |
Correct |
261 ms |
132216 KB |
Output is correct |
32 |
Correct |
252 ms |
129884 KB |
Output is correct |
33 |
Runtime error |
402 ms |
1048576 KB |
Execution killed with signal 9 |
34 |
Halted |
0 ms |
0 KB |
- |