# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1070440 |
2024-08-22T14:13:31 Z |
j_vdd16 |
Rectangles (IOI19_rect) |
C++17 |
|
5000 ms |
202576 KB |
#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<set<ii>> validRows(n);
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[i].insert({vec[idx], next->first});
}
if (next != rec.begin()) {
next--;
if (vec[idx] - next->first > 1)
validRows[i].insert({next->first, vec[idx]});
}
rec[vec[idx]] = val;
}
}
}
vector<set<ii>> validCols(m);
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[j].insert({vec[idx], next->first});
}
if (next != rec.begin()) {
next--;
if (vec[idx] - next->first > 1)
validCols[j].insert({next->first, vec[idx]});
}
rec[vec[idx]] = val;
}
}
}
ll result = 0;
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:77:13: note: in expansion of macro 'loop'
77 | loop(idx, vec.size()) {
| ^~~~
rect.cpp:84:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
| ~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
532 KB |
Output is correct |
3 |
Correct |
2 ms |
416 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 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 |
428 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
532 KB |
Output is correct |
3 |
Correct |
2 ms |
416 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 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 |
428 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
78 ms |
860 KB |
Output is correct |
23 |
Correct |
77 ms |
1116 KB |
Output is correct |
24 |
Correct |
82 ms |
1116 KB |
Output is correct |
25 |
Correct |
4 ms |
604 KB |
Output is correct |
26 |
Correct |
6 ms |
860 KB |
Output is correct |
27 |
Correct |
6 ms |
1112 KB |
Output is correct |
28 |
Correct |
8 ms |
856 KB |
Output is correct |
29 |
Correct |
4 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
532 KB |
Output is correct |
3 |
Correct |
2 ms |
416 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 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 |
428 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
78 ms |
860 KB |
Output is correct |
18 |
Correct |
77 ms |
1116 KB |
Output is correct |
19 |
Correct |
82 ms |
1116 KB |
Output is correct |
20 |
Correct |
4 ms |
604 KB |
Output is correct |
21 |
Correct |
6 ms |
860 KB |
Output is correct |
22 |
Correct |
6 ms |
1112 KB |
Output is correct |
23 |
Correct |
8 ms |
856 KB |
Output is correct |
24 |
Correct |
4 ms |
604 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
3450 ms |
4708 KB |
Output is correct |
31 |
Correct |
3401 ms |
4696 KB |
Output is correct |
32 |
Correct |
3459 ms |
4696 KB |
Output is correct |
33 |
Correct |
19 ms |
2140 KB |
Output is correct |
34 |
Correct |
44 ms |
4228 KB |
Output is correct |
35 |
Correct |
50 ms |
4432 KB |
Output is correct |
36 |
Correct |
124 ms |
4176 KB |
Output is correct |
37 |
Correct |
80 ms |
4176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
532 KB |
Output is correct |
3 |
Correct |
2 ms |
416 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 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 |
428 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
78 ms |
860 KB |
Output is correct |
18 |
Correct |
77 ms |
1116 KB |
Output is correct |
19 |
Correct |
82 ms |
1116 KB |
Output is correct |
20 |
Correct |
4 ms |
604 KB |
Output is correct |
21 |
Correct |
6 ms |
860 KB |
Output is correct |
22 |
Correct |
6 ms |
1112 KB |
Output is correct |
23 |
Correct |
8 ms |
856 KB |
Output is correct |
24 |
Correct |
4 ms |
604 KB |
Output is correct |
25 |
Correct |
3450 ms |
4708 KB |
Output is correct |
26 |
Correct |
3401 ms |
4696 KB |
Output is correct |
27 |
Correct |
3459 ms |
4696 KB |
Output is correct |
28 |
Correct |
19 ms |
2140 KB |
Output is correct |
29 |
Correct |
44 ms |
4228 KB |
Output is correct |
30 |
Correct |
50 ms |
4432 KB |
Output is correct |
31 |
Correct |
124 ms |
4176 KB |
Output is correct |
32 |
Correct |
80 ms |
4176 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
4215 ms |
29008 KB |
Output is correct |
39 |
Correct |
4078 ms |
30524 KB |
Output is correct |
40 |
Correct |
4386 ms |
30524 KB |
Output is correct |
41 |
Execution timed out |
5081 ms |
30336 KB |
Time limit exceeded |
42 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
860 KB |
Output is correct |
2 |
Correct |
14 ms |
856 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
436 KB |
Output is correct |
5 |
Correct |
4 ms |
1040 KB |
Output is correct |
6 |
Correct |
5 ms |
1112 KB |
Output is correct |
7 |
Correct |
4 ms |
1116 KB |
Output is correct |
8 |
Correct |
4 ms |
1020 KB |
Output is correct |
9 |
Correct |
4 ms |
1084 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1428 ms |
93220 KB |
Output is correct |
8 |
Correct |
3116 ms |
201720 KB |
Output is correct |
9 |
Correct |
3167 ms |
202576 KB |
Output is correct |
10 |
Correct |
3059 ms |
202576 KB |
Output is correct |
11 |
Correct |
595 ms |
28244 KB |
Output is correct |
12 |
Correct |
1126 ms |
52508 KB |
Output is correct |
13 |
Correct |
1186 ms |
56300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
532 KB |
Output is correct |
3 |
Correct |
2 ms |
416 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 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 |
428 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
78 ms |
860 KB |
Output is correct |
18 |
Correct |
77 ms |
1116 KB |
Output is correct |
19 |
Correct |
82 ms |
1116 KB |
Output is correct |
20 |
Correct |
4 ms |
604 KB |
Output is correct |
21 |
Correct |
6 ms |
860 KB |
Output is correct |
22 |
Correct |
6 ms |
1112 KB |
Output is correct |
23 |
Correct |
8 ms |
856 KB |
Output is correct |
24 |
Correct |
4 ms |
604 KB |
Output is correct |
25 |
Correct |
3450 ms |
4708 KB |
Output is correct |
26 |
Correct |
3401 ms |
4696 KB |
Output is correct |
27 |
Correct |
3459 ms |
4696 KB |
Output is correct |
28 |
Correct |
19 ms |
2140 KB |
Output is correct |
29 |
Correct |
44 ms |
4228 KB |
Output is correct |
30 |
Correct |
50 ms |
4432 KB |
Output is correct |
31 |
Correct |
124 ms |
4176 KB |
Output is correct |
32 |
Correct |
80 ms |
4176 KB |
Output is correct |
33 |
Correct |
4215 ms |
29008 KB |
Output is correct |
34 |
Correct |
4078 ms |
30524 KB |
Output is correct |
35 |
Correct |
4386 ms |
30524 KB |
Output is correct |
36 |
Execution timed out |
5081 ms |
30336 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |