#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4,popcnt,abm,mmx,tune=native")
#include <bits/stdc++.h>
#define INT_INF 0x3f3f3f3f
#define mp std::make_pair
#define MAXN 2501
typedef long long ll;
typedef std::pair<int,int> pii;
int num_rows,num_cols,arr[MAXN][MAXN],bit[MAXN],cnt[MAXN][MAXN],ans,l,r,lst[MAXN],pp;
std::vector<pii> row_dp[MAXN][MAXN],col_dp[MAXN][MAXN];
std::vector<std::pair<pii,int>> dep[MAXN];
pii dq[MAXN];
inline void update(int i, int val, int curr){
for(; i<=num_cols; i+=i&-i){
if(lst[i] != curr) bit[i] = val, lst[i] = curr;
else bit[i]+=val;
}
}
inline int query(int i, int curr){
static int res;
res = 0;
for(; i>0; i-=i&-i)
if(lst[i] == curr)
res+=bit[i];
return res;
}
inline void init_rows(){
// memset(cnt,0,sizeof cnt);
for(int i=2; i<num_rows; i++){
l = 1, r = 0;
for(int k=1; k<=num_cols; k++){
while(r-l+1 > 0 && dq[r].first < arr[i][k]) r--;
int lft = (r-l+1>0?dq[r].second:INT_INF);
if(lft < k-1 && (row_dp[lft+1][k-1].empty() || row_dp[lft+1][k-1].back().first != i))
row_dp[lft+1][k-1].emplace_back(i,i), cnt[lft+1][k-1]++; //rows[i].pb(mp(lft+1,k-1));
while(r-l+1 > 0 && dq[r].first == arr[i][k]) r--;
dq[++r] = mp(arr[i][k],k);
}
l = 1, r = 0;
for(int k=num_cols; k>=1; k--){
while(r-l+1 > 0 && dq[r].first < arr[i][k]) r--;
int rgt = (r-l+1>0?dq[r].second:-INT_INF);
if(rgt > k+1 && (row_dp[k+1][rgt-1].empty() || row_dp[k+1][rgt-1].back().first != i))
row_dp[k+1][rgt-1].emplace_back(i,i), cnt[k+1][rgt-1]++; //rows[i].pb(mp(k+1,rgt-1));
while(r-l+1 > 0 && dq[r].first == arr[i][k]) r--;
dq[++r] = mp(arr[i][k],k);
}
}
}
inline void init_cols(){
memset(cnt,0,sizeof cnt);
for(int i=2; i<num_cols; i++){
l = 1, r = 0;
for(int k=1; k<=num_rows; k++){
while(r-l+1 > 0 && dq[r].first < arr[k][i]) r--;
int lft = (r-l+1>0?dq[r].second:INT_INF);
if(lft < k-1 && (col_dp[lft+1][k-1].empty() || col_dp[lft+1][k-1].back().first != i))
col_dp[lft+1][k-1].emplace_back(i,i), cnt[lft+1][k-1]++; //cols[i].pb(mp(lft+1,k-1));
while(r-l+1 > 0 && dq[r].first == arr[k][i]) r--;
dq[++r] = mp(arr[k][i],k);
}
l = 1, r = 0;
for(int k=num_rows; k>=1; k--){
while(r-l+1 > 0 && dq[r].first < arr[k][i]) r--;
int rgt = (r-l+1>0?dq[r].second:-INT_INF);
if(rgt > k+1 && (col_dp[k+1][rgt-1].empty() || col_dp[k+1][rgt-1].back().first != i))
col_dp[k+1][rgt-1].emplace_back(i,i), cnt[k+1][rgt-1]++; //cols[i].pb(mp(k+1,rgt-1));
while(r-l+1 > 0 && dq[r].first == arr[k][i]) r--;
dq[++r] = mp(arr[k][i],k);
}
}
}
#define nums row_dp[l][r]
inline void calc_hor_dp(){
for(int l=2; l<=num_cols-1; l++){
for(int r=l; r<=num_cols-1; r++){
if(cnt[l][r] == 0) continue;
int lst = 0;
for(int i=1; i<cnt[l][r]; i++){
if(nums[i].first == nums[i-1].first+1) continue;
for(int k=nums[lst].first; k<=nums[i-1].first; k++)
dep[nums[i-1].first-k+1].emplace_back(mp(k,l),r);
lst = i;
}
for(int k=nums[lst].first; k<=nums[cnt[l][r]-1].first; k++)
dep[nums[cnt[l][r]-1].first-k+1].emplace_back(mp(k,l),r);
nums.clear();
}
}
for(int i=1; i<=num_rows; i++){
for(auto &check:dep[i])
row_dp[check.first.first][check.first.second].emplace_back(i,check.second);
}
}
#define nums col_dp[l][r]
inline void calc_col_dp(){
for(int l=2; l<=num_rows-1; l++){
for(int r=l; r<=num_rows-1; r++){
if(cnt[l][r] == 0) continue;
int lst = 0;
for(int i=1; i<cnt[l][r]; i++){
if(nums[i].first == nums[i-1].first+1) continue;
for(int k=nums[lst].first; k<=nums[i-1].first; k++)
col_dp[l][k].emplace_back(r,nums[i-1].first);
lst = i;
}
for(int k=nums[lst].first; k<=nums[cnt[l][r]-1].first; k++)
col_dp[l][k].emplace_back(r,nums[cnt[l][r]-1].first);
}
}
}
ll count_rectangles(std::vector<std::vector<int>> a){
num_rows = a.size(), num_cols = a[0].size();
for(int i=0; i<a.size(); i++)
for(int k=0; k<a[i].size(); k++)
arr[i+1][k+1] = a[i][k];
init_rows(); calc_hor_dp();
init_cols(); calc_col_dp();
for(int i=num_rows-1; i>=2; i--){
for(int k=num_cols-1; k>=2; k--){
int ptr = cnt[i][k], res = 0, cc = 0; ++pp;
for(int v=0; v<row_dp[i][k].size(); v++){
while(ptr < col_dp[i][k].size() && col_dp[i][k][ptr].first-i+1 <= row_dp[i][k][v].first){
update(col_dp[i][k][ptr].second-k+1,1,pp);
ptr++, cc++;
}
res+=cc-query(row_dp[i][k][v].second-k,pp);
}
ans+=res;
}
}
return ans;
}
Compilation message
rect.cpp:107:0: warning: "nums" redefined
#define nums col_dp[l][r]
rect.cpp:84:0: note: this is the location of the previous definition
#define nums row_dp[l][r]
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:128:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<a.size(); i++)
~^~~~~~~~~
rect.cpp:129:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0; k<a[i].size(); k++)
~^~~~~~~~~~~~
rect.cpp:136:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int v=0; v<row_dp[i][k].size(); v++){
~^~~~~~~~~~~~~~~~~~~~
rect.cpp:137:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ptr < col_dp[i][k].size() && col_dp[i][k][ptr].first-i+1 <= row_dp[i][k][v].first){
~~~~^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
310 ms |
318640 KB |
Output is correct |
2 |
Correct |
311 ms |
318844 KB |
Output is correct |
3 |
Correct |
310 ms |
318804 KB |
Output is correct |
4 |
Correct |
312 ms |
318824 KB |
Output is correct |
5 |
Correct |
309 ms |
318720 KB |
Output is correct |
6 |
Correct |
309 ms |
318864 KB |
Output is correct |
7 |
Correct |
310 ms |
318780 KB |
Output is correct |
8 |
Correct |
309 ms |
318824 KB |
Output is correct |
9 |
Correct |
313 ms |
318840 KB |
Output is correct |
10 |
Correct |
307 ms |
318812 KB |
Output is correct |
11 |
Correct |
312 ms |
318816 KB |
Output is correct |
12 |
Correct |
313 ms |
318828 KB |
Output is correct |
13 |
Correct |
312 ms |
318656 KB |
Output is correct |
14 |
Correct |
313 ms |
318620 KB |
Output is correct |
15 |
Correct |
310 ms |
318636 KB |
Output is correct |
16 |
Correct |
314 ms |
318584 KB |
Output is correct |
17 |
Correct |
308 ms |
318752 KB |
Output is correct |
18 |
Correct |
313 ms |
318632 KB |
Output is correct |
19 |
Correct |
314 ms |
318840 KB |
Output is correct |
20 |
Correct |
325 ms |
318840 KB |
Output is correct |
21 |
Correct |
334 ms |
318552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
310 ms |
318640 KB |
Output is correct |
2 |
Correct |
311 ms |
318844 KB |
Output is correct |
3 |
Correct |
310 ms |
318804 KB |
Output is correct |
4 |
Correct |
312 ms |
318824 KB |
Output is correct |
5 |
Correct |
309 ms |
318720 KB |
Output is correct |
6 |
Correct |
309 ms |
318864 KB |
Output is correct |
7 |
Correct |
310 ms |
318780 KB |
Output is correct |
8 |
Correct |
309 ms |
318824 KB |
Output is correct |
9 |
Correct |
313 ms |
318840 KB |
Output is correct |
10 |
Correct |
307 ms |
318812 KB |
Output is correct |
11 |
Correct |
312 ms |
318816 KB |
Output is correct |
12 |
Correct |
313 ms |
318828 KB |
Output is correct |
13 |
Correct |
312 ms |
318656 KB |
Output is correct |
14 |
Correct |
313 ms |
318620 KB |
Output is correct |
15 |
Correct |
310 ms |
318636 KB |
Output is correct |
16 |
Correct |
314 ms |
318584 KB |
Output is correct |
17 |
Correct |
318 ms |
319736 KB |
Output is correct |
18 |
Correct |
315 ms |
319832 KB |
Output is correct |
19 |
Correct |
311 ms |
319768 KB |
Output is correct |
20 |
Correct |
312 ms |
319312 KB |
Output is correct |
21 |
Correct |
313 ms |
319544 KB |
Output is correct |
22 |
Correct |
315 ms |
319480 KB |
Output is correct |
23 |
Correct |
318 ms |
319616 KB |
Output is correct |
24 |
Correct |
315 ms |
319356 KB |
Output is correct |
25 |
Correct |
308 ms |
318752 KB |
Output is correct |
26 |
Correct |
313 ms |
318632 KB |
Output is correct |
27 |
Correct |
314 ms |
318840 KB |
Output is correct |
28 |
Correct |
325 ms |
318840 KB |
Output is correct |
29 |
Correct |
334 ms |
318552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
310 ms |
318640 KB |
Output is correct |
2 |
Correct |
311 ms |
318844 KB |
Output is correct |
3 |
Correct |
310 ms |
318804 KB |
Output is correct |
4 |
Correct |
312 ms |
318824 KB |
Output is correct |
5 |
Correct |
309 ms |
318720 KB |
Output is correct |
6 |
Correct |
309 ms |
318864 KB |
Output is correct |
7 |
Correct |
310 ms |
318780 KB |
Output is correct |
8 |
Correct |
309 ms |
318824 KB |
Output is correct |
9 |
Correct |
313 ms |
318840 KB |
Output is correct |
10 |
Correct |
307 ms |
318812 KB |
Output is correct |
11 |
Correct |
312 ms |
318816 KB |
Output is correct |
12 |
Correct |
313 ms |
318828 KB |
Output is correct |
13 |
Correct |
312 ms |
318656 KB |
Output is correct |
14 |
Correct |
313 ms |
318620 KB |
Output is correct |
15 |
Correct |
310 ms |
318636 KB |
Output is correct |
16 |
Correct |
314 ms |
318584 KB |
Output is correct |
17 |
Correct |
318 ms |
319736 KB |
Output is correct |
18 |
Correct |
315 ms |
319832 KB |
Output is correct |
19 |
Correct |
311 ms |
319768 KB |
Output is correct |
20 |
Correct |
312 ms |
319312 KB |
Output is correct |
21 |
Correct |
313 ms |
319544 KB |
Output is correct |
22 |
Correct |
315 ms |
319480 KB |
Output is correct |
23 |
Correct |
318 ms |
319616 KB |
Output is correct |
24 |
Correct |
315 ms |
319356 KB |
Output is correct |
25 |
Correct |
326 ms |
324088 KB |
Output is correct |
26 |
Correct |
326 ms |
324048 KB |
Output is correct |
27 |
Correct |
327 ms |
323992 KB |
Output is correct |
28 |
Correct |
327 ms |
321460 KB |
Output is correct |
29 |
Correct |
334 ms |
323060 KB |
Output is correct |
30 |
Correct |
335 ms |
323020 KB |
Output is correct |
31 |
Correct |
346 ms |
322868 KB |
Output is correct |
32 |
Correct |
330 ms |
322780 KB |
Output is correct |
33 |
Correct |
308 ms |
318752 KB |
Output is correct |
34 |
Correct |
313 ms |
318632 KB |
Output is correct |
35 |
Correct |
314 ms |
318840 KB |
Output is correct |
36 |
Correct |
325 ms |
318840 KB |
Output is correct |
37 |
Correct |
334 ms |
318552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
310 ms |
318640 KB |
Output is correct |
2 |
Correct |
311 ms |
318844 KB |
Output is correct |
3 |
Correct |
310 ms |
318804 KB |
Output is correct |
4 |
Correct |
312 ms |
318824 KB |
Output is correct |
5 |
Correct |
309 ms |
318720 KB |
Output is correct |
6 |
Correct |
309 ms |
318864 KB |
Output is correct |
7 |
Correct |
310 ms |
318780 KB |
Output is correct |
8 |
Correct |
309 ms |
318824 KB |
Output is correct |
9 |
Correct |
313 ms |
318840 KB |
Output is correct |
10 |
Correct |
307 ms |
318812 KB |
Output is correct |
11 |
Correct |
312 ms |
318816 KB |
Output is correct |
12 |
Correct |
313 ms |
318828 KB |
Output is correct |
13 |
Correct |
312 ms |
318656 KB |
Output is correct |
14 |
Correct |
313 ms |
318620 KB |
Output is correct |
15 |
Correct |
310 ms |
318636 KB |
Output is correct |
16 |
Correct |
314 ms |
318584 KB |
Output is correct |
17 |
Correct |
318 ms |
319736 KB |
Output is correct |
18 |
Correct |
315 ms |
319832 KB |
Output is correct |
19 |
Correct |
311 ms |
319768 KB |
Output is correct |
20 |
Correct |
312 ms |
319312 KB |
Output is correct |
21 |
Correct |
313 ms |
319544 KB |
Output is correct |
22 |
Correct |
315 ms |
319480 KB |
Output is correct |
23 |
Correct |
318 ms |
319616 KB |
Output is correct |
24 |
Correct |
315 ms |
319356 KB |
Output is correct |
25 |
Correct |
326 ms |
324088 KB |
Output is correct |
26 |
Correct |
326 ms |
324048 KB |
Output is correct |
27 |
Correct |
327 ms |
323992 KB |
Output is correct |
28 |
Correct |
327 ms |
321460 KB |
Output is correct |
29 |
Correct |
334 ms |
323060 KB |
Output is correct |
30 |
Correct |
335 ms |
323020 KB |
Output is correct |
31 |
Correct |
346 ms |
322868 KB |
Output is correct |
32 |
Correct |
330 ms |
322780 KB |
Output is correct |
33 |
Correct |
495 ms |
353756 KB |
Output is correct |
34 |
Correct |
458 ms |
352740 KB |
Output is correct |
35 |
Correct |
458 ms |
352416 KB |
Output is correct |
36 |
Correct |
406 ms |
351328 KB |
Output is correct |
37 |
Correct |
521 ms |
377568 KB |
Output is correct |
38 |
Correct |
544 ms |
377552 KB |
Output is correct |
39 |
Correct |
525 ms |
377464 KB |
Output is correct |
40 |
Correct |
503 ms |
374056 KB |
Output is correct |
41 |
Correct |
428 ms |
339296 KB |
Output is correct |
42 |
Correct |
481 ms |
344292 KB |
Output is correct |
43 |
Correct |
648 ms |
361060 KB |
Output is correct |
44 |
Correct |
657 ms |
361352 KB |
Output is correct |
45 |
Correct |
507 ms |
341704 KB |
Output is correct |
46 |
Correct |
517 ms |
340324 KB |
Output is correct |
47 |
Correct |
615 ms |
359176 KB |
Output is correct |
48 |
Correct |
627 ms |
359664 KB |
Output is correct |
49 |
Correct |
308 ms |
318752 KB |
Output is correct |
50 |
Correct |
313 ms |
318632 KB |
Output is correct |
51 |
Correct |
314 ms |
318840 KB |
Output is correct |
52 |
Correct |
325 ms |
318840 KB |
Output is correct |
53 |
Correct |
334 ms |
318552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
323 ms |
319064 KB |
Output is correct |
2 |
Correct |
321 ms |
319112 KB |
Output is correct |
3 |
Correct |
323 ms |
318712 KB |
Output is correct |
4 |
Correct |
315 ms |
318672 KB |
Output is correct |
5 |
Correct |
325 ms |
319132 KB |
Output is correct |
6 |
Correct |
324 ms |
318968 KB |
Output is correct |
7 |
Correct |
323 ms |
319056 KB |
Output is correct |
8 |
Correct |
324 ms |
318968 KB |
Output is correct |
9 |
Correct |
336 ms |
319200 KB |
Output is correct |
10 |
Correct |
324 ms |
318712 KB |
Output is correct |
11 |
Correct |
325 ms |
318748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
311 ms |
318744 KB |
Output is correct |
2 |
Correct |
1165 ms |
425832 KB |
Output is correct |
3 |
Correct |
2281 ms |
549968 KB |
Output is correct |
4 |
Correct |
2311 ms |
550900 KB |
Output is correct |
5 |
Correct |
2325 ms |
550656 KB |
Output is correct |
6 |
Correct |
469 ms |
356872 KB |
Output is correct |
7 |
Correct |
619 ms |
391720 KB |
Output is correct |
8 |
Correct |
639 ms |
394716 KB |
Output is correct |
9 |
Correct |
308 ms |
318752 KB |
Output is correct |
10 |
Correct |
313 ms |
318632 KB |
Output is correct |
11 |
Correct |
314 ms |
318840 KB |
Output is correct |
12 |
Correct |
325 ms |
318840 KB |
Output is correct |
13 |
Correct |
334 ms |
318552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
310 ms |
318640 KB |
Output is correct |
2 |
Correct |
311 ms |
318844 KB |
Output is correct |
3 |
Correct |
310 ms |
318804 KB |
Output is correct |
4 |
Correct |
312 ms |
318824 KB |
Output is correct |
5 |
Correct |
309 ms |
318720 KB |
Output is correct |
6 |
Correct |
309 ms |
318864 KB |
Output is correct |
7 |
Correct |
310 ms |
318780 KB |
Output is correct |
8 |
Correct |
309 ms |
318824 KB |
Output is correct |
9 |
Correct |
313 ms |
318840 KB |
Output is correct |
10 |
Correct |
307 ms |
318812 KB |
Output is correct |
11 |
Correct |
312 ms |
318816 KB |
Output is correct |
12 |
Correct |
313 ms |
318828 KB |
Output is correct |
13 |
Correct |
312 ms |
318656 KB |
Output is correct |
14 |
Correct |
313 ms |
318620 KB |
Output is correct |
15 |
Correct |
310 ms |
318636 KB |
Output is correct |
16 |
Correct |
314 ms |
318584 KB |
Output is correct |
17 |
Correct |
318 ms |
319736 KB |
Output is correct |
18 |
Correct |
315 ms |
319832 KB |
Output is correct |
19 |
Correct |
311 ms |
319768 KB |
Output is correct |
20 |
Correct |
312 ms |
319312 KB |
Output is correct |
21 |
Correct |
313 ms |
319544 KB |
Output is correct |
22 |
Correct |
315 ms |
319480 KB |
Output is correct |
23 |
Correct |
318 ms |
319616 KB |
Output is correct |
24 |
Correct |
315 ms |
319356 KB |
Output is correct |
25 |
Correct |
326 ms |
324088 KB |
Output is correct |
26 |
Correct |
326 ms |
324048 KB |
Output is correct |
27 |
Correct |
327 ms |
323992 KB |
Output is correct |
28 |
Correct |
327 ms |
321460 KB |
Output is correct |
29 |
Correct |
334 ms |
323060 KB |
Output is correct |
30 |
Correct |
335 ms |
323020 KB |
Output is correct |
31 |
Correct |
346 ms |
322868 KB |
Output is correct |
32 |
Correct |
330 ms |
322780 KB |
Output is correct |
33 |
Correct |
495 ms |
353756 KB |
Output is correct |
34 |
Correct |
458 ms |
352740 KB |
Output is correct |
35 |
Correct |
458 ms |
352416 KB |
Output is correct |
36 |
Correct |
406 ms |
351328 KB |
Output is correct |
37 |
Correct |
521 ms |
377568 KB |
Output is correct |
38 |
Correct |
544 ms |
377552 KB |
Output is correct |
39 |
Correct |
525 ms |
377464 KB |
Output is correct |
40 |
Correct |
503 ms |
374056 KB |
Output is correct |
41 |
Correct |
428 ms |
339296 KB |
Output is correct |
42 |
Correct |
481 ms |
344292 KB |
Output is correct |
43 |
Correct |
648 ms |
361060 KB |
Output is correct |
44 |
Correct |
657 ms |
361352 KB |
Output is correct |
45 |
Correct |
507 ms |
341704 KB |
Output is correct |
46 |
Correct |
517 ms |
340324 KB |
Output is correct |
47 |
Correct |
615 ms |
359176 KB |
Output is correct |
48 |
Correct |
627 ms |
359664 KB |
Output is correct |
49 |
Correct |
323 ms |
319064 KB |
Output is correct |
50 |
Correct |
321 ms |
319112 KB |
Output is correct |
51 |
Correct |
323 ms |
318712 KB |
Output is correct |
52 |
Correct |
315 ms |
318672 KB |
Output is correct |
53 |
Correct |
325 ms |
319132 KB |
Output is correct |
54 |
Correct |
324 ms |
318968 KB |
Output is correct |
55 |
Correct |
323 ms |
319056 KB |
Output is correct |
56 |
Correct |
324 ms |
318968 KB |
Output is correct |
57 |
Correct |
336 ms |
319200 KB |
Output is correct |
58 |
Correct |
324 ms |
318712 KB |
Output is correct |
59 |
Correct |
325 ms |
318748 KB |
Output is correct |
60 |
Correct |
311 ms |
318744 KB |
Output is correct |
61 |
Correct |
1165 ms |
425832 KB |
Output is correct |
62 |
Correct |
2281 ms |
549968 KB |
Output is correct |
63 |
Correct |
2311 ms |
550900 KB |
Output is correct |
64 |
Correct |
2325 ms |
550656 KB |
Output is correct |
65 |
Correct |
469 ms |
356872 KB |
Output is correct |
66 |
Correct |
619 ms |
391720 KB |
Output is correct |
67 |
Correct |
639 ms |
394716 KB |
Output is correct |
68 |
Correct |
3292 ms |
723336 KB |
Output is correct |
69 |
Correct |
2647 ms |
705088 KB |
Output is correct |
70 |
Correct |
2548 ms |
705224 KB |
Output is correct |
71 |
Correct |
1603 ms |
687008 KB |
Output is correct |
72 |
Correct |
3455 ms |
1024288 KB |
Output is correct |
73 |
Correct |
3401 ms |
627524 KB |
Output is correct |
74 |
Correct |
3691 ms |
658836 KB |
Output is correct |
75 |
Execution timed out |
5107 ms |
824936 KB |
Time limit exceeded |
76 |
Halted |
0 ms |
0 KB |
- |