#include "rect.h"
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
//#define int long long
#define ll long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
long long count_rectangles(vvi a) {
int n = a.size();
int m = a[0].size();
vector<vvi> validRows(m, vvi(m));
for (int i = 1; i < n - 1; i++) {
map<int, vi, greater<int>> values;
loop(j, m) {
values[a[i][j]].push_back(j);
}
map<int, int> rec;
for (auto [val, vec] : values) {
loop(idx, vec.size()) {
if (rec.size() == 0) {
rec[vec[idx]] = val;
continue;
}
auto next = rec.upper_bound(vec[idx]);
if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
validRows[vec[idx]][next->first].push_back(i);
}
if (next != rec.begin()) {
next--;
if (vec[idx] - next->first > 1) {
validRows[next->first][vec[idx]].push_back(i);
}
}
rec[vec[idx]] = val;
}
}
}
vector<vvi> validCols(n, vvi(n));
for (int j = 1; j < m - 1; j++) {
map<int, vi, greater<int>> values;
loop(i, n) {
values[a[i][j]].push_back(i);
}
map<int, int> rec;
for (auto [val, vec] : values) {
loop(idx, vec.size()) {
if (rec.size() == 0) {
rec[vec[idx]] = val;
continue;
}
auto next = rec.upper_bound(vec[idx]);
if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
validCols[vec[idx]][next->first].push_back(j);
}
if (next != rec.begin()) {
next--;
if (vec[idx] - next->first > 1) {
validCols[next->first][vec[idx]].push_back(j);
}
}
rec[vec[idx]] = val;
}
}
}
ll result = 0;
for (int j1 = 0; j1 < m; j1++) {
for (int j2 = j1 + 2; j2 < m; j2++) {
const auto& valid = validRows[j1][j2];
loop(idx, valid.size()) {
int furthest = idx;
while (furthest < valid.size() - 1 && valid[furthest + 1] == valid[furthest] + 1) {
furthest++;
}
for (int idx2 = idx; idx2 <= furthest; idx2++) {
const auto& relevantCols = validCols[valid[idx] - 1][valid[idx2] + 1];
auto start = lower_bound(all(relevantCols), j1 + 1);
auto end = lower_bound(all(relevantCols), j2 - 1);
if (start == relevantCols.end() || end == relevantCols.end() || *start != j1 + 1 || *end != j2 - 1 || (end - start) != j2 - j1 - 2) {
}
else {
result++;
}
}
}
}
}
// for (int i = 1; i < n - 1; i++) {
// for (auto [x, y] : validRows[i]) {
// int furthest = i;
// while (validRows[furthest + 1].count({x, y})) furthest++;
// vi freq(furthest - i + 1);
// for (int j = x + 1; j <= y - 1; j++) {
// for (int i2 = i; i2 <= furthest; i2++) {
// if (validCols[j].count({i - 1, i2 + 1}))
// freq[i2 - i]++;
// }
// }
// ll extra = 0;
// for (int k = 0; k < furthest - i + 1; k++) {
// if (freq[k] == y - x - 1)
// extra++;
// }
// result += extra;
// }
// }
return result;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(vvi)':
rect.cpp:20:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | #define loop(X, N) for(int X = 0; X < (N); X++)
| ^
rect.cpp:47:13: note: in expansion of macro 'loop'
47 | loop(idx, vec.size()) {
| ^~~~
rect.cpp:54:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
| ~~~~^~~~~~~~~~~~~~~~~
rect.cpp:20:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | #define loop(X, N) for(int X = 0; X < (N); X++)
| ^
rect.cpp:78:13: note: in expansion of macro 'loop'
78 | loop(idx, vec.size()) {
| ^~~~
rect.cpp:85:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
| ~~~~^~~~~~~~~~~~~~~~~
rect.cpp:20:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | #define loop(X, N) for(int X = 0; X < (N); X++)
| ^
rect.cpp:105:13: note: in expansion of macro 'loop'
105 | loop(idx, valid.size()) {
| ^~~~
rect.cpp:107:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | while (furthest < valid.size() - 1 && valid[furthest + 1] == valid[furthest] + 1) {
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
476 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
428 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
432 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
476 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
428 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
432 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
4 ms |
856 KB |
Output is correct |
23 |
Correct |
4 ms |
860 KB |
Output is correct |
24 |
Correct |
4 ms |
860 KB |
Output is correct |
25 |
Correct |
4 ms |
696 KB |
Output is correct |
26 |
Correct |
4 ms |
860 KB |
Output is correct |
27 |
Correct |
5 ms |
860 KB |
Output is correct |
28 |
Correct |
4 ms |
684 KB |
Output is correct |
29 |
Correct |
2 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
476 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
428 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
432 KB |
Output is correct |
17 |
Correct |
4 ms |
856 KB |
Output is correct |
18 |
Correct |
4 ms |
860 KB |
Output is correct |
19 |
Correct |
4 ms |
860 KB |
Output is correct |
20 |
Correct |
4 ms |
696 KB |
Output is correct |
21 |
Correct |
4 ms |
860 KB |
Output is correct |
22 |
Correct |
5 ms |
860 KB |
Output is correct |
23 |
Correct |
4 ms |
684 KB |
Output is correct |
24 |
Correct |
2 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
34 ms |
3312 KB |
Output is correct |
31 |
Correct |
52 ms |
3164 KB |
Output is correct |
32 |
Correct |
32 ms |
3160 KB |
Output is correct |
33 |
Correct |
14 ms |
2940 KB |
Output is correct |
34 |
Correct |
28 ms |
3412 KB |
Output is correct |
35 |
Correct |
28 ms |
3416 KB |
Output is correct |
36 |
Correct |
29 ms |
3304 KB |
Output is correct |
37 |
Correct |
34 ms |
3456 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
476 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
428 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
432 KB |
Output is correct |
17 |
Correct |
4 ms |
856 KB |
Output is correct |
18 |
Correct |
4 ms |
860 KB |
Output is correct |
19 |
Correct |
4 ms |
860 KB |
Output is correct |
20 |
Correct |
4 ms |
696 KB |
Output is correct |
21 |
Correct |
4 ms |
860 KB |
Output is correct |
22 |
Correct |
5 ms |
860 KB |
Output is correct |
23 |
Correct |
4 ms |
684 KB |
Output is correct |
24 |
Correct |
2 ms |
604 KB |
Output is correct |
25 |
Correct |
34 ms |
3312 KB |
Output is correct |
26 |
Correct |
52 ms |
3164 KB |
Output is correct |
27 |
Correct |
32 ms |
3160 KB |
Output is correct |
28 |
Correct |
14 ms |
2940 KB |
Output is correct |
29 |
Correct |
28 ms |
3412 KB |
Output is correct |
30 |
Correct |
28 ms |
3416 KB |
Output is correct |
31 |
Correct |
29 ms |
3304 KB |
Output is correct |
32 |
Correct |
34 ms |
3456 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
348 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
252 ms |
46108 KB |
Output is correct |
39 |
Correct |
245 ms |
46056 KB |
Output is correct |
40 |
Correct |
248 ms |
45976 KB |
Output is correct |
41 |
Correct |
235 ms |
46068 KB |
Output is correct |
42 |
Correct |
1071 ms |
36480 KB |
Output is correct |
43 |
Correct |
1094 ms |
36500 KB |
Output is correct |
44 |
Correct |
1077 ms |
36632 KB |
Output is correct |
45 |
Correct |
1058 ms |
34860 KB |
Output is correct |
46 |
Correct |
195 ms |
29816 KB |
Output is correct |
47 |
Correct |
187 ms |
30804 KB |
Output is correct |
48 |
Correct |
422 ms |
35452 KB |
Output is correct |
49 |
Correct |
516 ms |
37460 KB |
Output is correct |
50 |
Correct |
228 ms |
22100 KB |
Output is correct |
51 |
Correct |
228 ms |
21968 KB |
Output is correct |
52 |
Correct |
499 ms |
35620 KB |
Output is correct |
53 |
Correct |
475 ms |
36468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
99 ms |
147652 KB |
Output is correct |
2 |
Correct |
81 ms |
106580 KB |
Output is correct |
3 |
Correct |
74 ms |
147280 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
97 ms |
147704 KB |
Output is correct |
6 |
Correct |
106 ms |
147792 KB |
Output is correct |
7 |
Correct |
83 ms |
147796 KB |
Output is correct |
8 |
Correct |
72 ms |
147544 KB |
Output is correct |
9 |
Correct |
71 ms |
147792 KB |
Output is correct |
10 |
Correct |
103 ms |
147268 KB |
Output is correct |
11 |
Correct |
79 ms |
147340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1149 ms |
201240 KB |
Output is correct |
8 |
Correct |
2594 ms |
375464 KB |
Output is correct |
9 |
Correct |
2619 ms |
376796 KB |
Output is correct |
10 |
Correct |
2608 ms |
377380 KB |
Output is correct |
11 |
Correct |
727 ms |
213332 KB |
Output is correct |
12 |
Correct |
1377 ms |
334092 KB |
Output is correct |
13 |
Correct |
1381 ms |
355612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
476 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
428 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
432 KB |
Output is correct |
17 |
Correct |
4 ms |
856 KB |
Output is correct |
18 |
Correct |
4 ms |
860 KB |
Output is correct |
19 |
Correct |
4 ms |
860 KB |
Output is correct |
20 |
Correct |
4 ms |
696 KB |
Output is correct |
21 |
Correct |
4 ms |
860 KB |
Output is correct |
22 |
Correct |
5 ms |
860 KB |
Output is correct |
23 |
Correct |
4 ms |
684 KB |
Output is correct |
24 |
Correct |
2 ms |
604 KB |
Output is correct |
25 |
Correct |
34 ms |
3312 KB |
Output is correct |
26 |
Correct |
52 ms |
3164 KB |
Output is correct |
27 |
Correct |
32 ms |
3160 KB |
Output is correct |
28 |
Correct |
14 ms |
2940 KB |
Output is correct |
29 |
Correct |
28 ms |
3412 KB |
Output is correct |
30 |
Correct |
28 ms |
3416 KB |
Output is correct |
31 |
Correct |
29 ms |
3304 KB |
Output is correct |
32 |
Correct |
34 ms |
3456 KB |
Output is correct |
33 |
Correct |
252 ms |
46108 KB |
Output is correct |
34 |
Correct |
245 ms |
46056 KB |
Output is correct |
35 |
Correct |
248 ms |
45976 KB |
Output is correct |
36 |
Correct |
235 ms |
46068 KB |
Output is correct |
37 |
Correct |
1071 ms |
36480 KB |
Output is correct |
38 |
Correct |
1094 ms |
36500 KB |
Output is correct |
39 |
Correct |
1077 ms |
36632 KB |
Output is correct |
40 |
Correct |
1058 ms |
34860 KB |
Output is correct |
41 |
Correct |
195 ms |
29816 KB |
Output is correct |
42 |
Correct |
187 ms |
30804 KB |
Output is correct |
43 |
Correct |
422 ms |
35452 KB |
Output is correct |
44 |
Correct |
516 ms |
37460 KB |
Output is correct |
45 |
Correct |
228 ms |
22100 KB |
Output is correct |
46 |
Correct |
228 ms |
21968 KB |
Output is correct |
47 |
Correct |
499 ms |
35620 KB |
Output is correct |
48 |
Correct |
475 ms |
36468 KB |
Output is correct |
49 |
Correct |
99 ms |
147652 KB |
Output is correct |
50 |
Correct |
81 ms |
106580 KB |
Output is correct |
51 |
Correct |
74 ms |
147280 KB |
Output is correct |
52 |
Correct |
1 ms |
348 KB |
Output is correct |
53 |
Correct |
97 ms |
147704 KB |
Output is correct |
54 |
Correct |
106 ms |
147792 KB |
Output is correct |
55 |
Correct |
83 ms |
147796 KB |
Output is correct |
56 |
Correct |
72 ms |
147544 KB |
Output is correct |
57 |
Correct |
71 ms |
147792 KB |
Output is correct |
58 |
Correct |
103 ms |
147268 KB |
Output is correct |
59 |
Correct |
79 ms |
147340 KB |
Output is correct |
60 |
Correct |
0 ms |
348 KB |
Output is correct |
61 |
Correct |
1149 ms |
201240 KB |
Output is correct |
62 |
Correct |
2594 ms |
375464 KB |
Output is correct |
63 |
Correct |
2619 ms |
376796 KB |
Output is correct |
64 |
Correct |
2608 ms |
377380 KB |
Output is correct |
65 |
Correct |
727 ms |
213332 KB |
Output is correct |
66 |
Correct |
1377 ms |
334092 KB |
Output is correct |
67 |
Correct |
1381 ms |
355612 KB |
Output is correct |
68 |
Correct |
1 ms |
348 KB |
Output is correct |
69 |
Correct |
0 ms |
348 KB |
Output is correct |
70 |
Correct |
1 ms |
348 KB |
Output is correct |
71 |
Correct |
1 ms |
348 KB |
Output is correct |
72 |
Correct |
1 ms |
348 KB |
Output is correct |
73 |
Correct |
3618 ms |
595588 KB |
Output is correct |
74 |
Correct |
3420 ms |
595692 KB |
Output is correct |
75 |
Correct |
3672 ms |
595640 KB |
Output is correct |
76 |
Correct |
3394 ms |
595784 KB |
Output is correct |
77 |
Execution timed out |
5071 ms |
467820 KB |
Time limit exceeded |
78 |
Halted |
0 ms |
0 KB |
- |