# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1069800 |
2024-08-22T09:03:48 Z |
Gromp15 |
Rectangles (IOI19_rect) |
C++17 |
|
2355 ms |
832084 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include "rect.h"
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
using namespace std;
template<typename T> struct fenwick {
int n; vector<T> bit;
fenwick(int a) : n(a), bit(a+1) {}
T sum(int pos) {
T s = 0;
for (; pos; s += bit[pos], pos -= pos&-pos);
return s;
}
T query(int l, int r) {
return sum(r+1) - sum(l);
}
void update(int pos, T x) {
pos++;
for (; pos <= n; bit[pos] += x, pos += pos&-pos);
}
};
const int nax = 2505;
short u[nax][nax], d[nax][nax], l[nax][nax], r[nax][nax], st[nax], idx[nax], idx2[nax];
vector<ar<short, 2>> who[nax][nax], who2[nax][nax];
fenwick<int> fw(nax);
long long count_rectangles(std::vector<std::vector<int>> a) {
int n = sz(a), m = sz(a[0]);
for (int i = 0, tp = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
while (tp && a[i][j] >= a[i][st[tp]]) tp--;
l[i][j] = tp ? st[tp] : m + 1;
st[++tp] = j;
}
tp = 0;
for (int j = m-1; j >= 0; j--) {
while (tp && a[i][j] >= a[i][st[tp]]) tp--;
r[i][j] = tp ? st[tp] : -2;
st[++tp] = j;
}
}
for (int i = 0, tp = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
while (tp && a[j][i] >= a[st[tp]][i]) tp--;
u[j][i] = tp ? st[tp] : n + 1;
st[++tp] = j;
}
tp = 0;
for (int j = n-1; j >= 0; j--) {
while (tp && a[j][i] >= a[st[tp]][i]) tp--;
d[j][i] = tp ? st[tp] : -2;
st[++tp] = j;
}
}
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
int L = l[i][j] + 1, R = r[i][j] - 1;
if (L <= R) who[i][L].push_back({R, 0});
int U = u[i][j] + 1, D = d[i][j] - 1;
if (U <= D) who2[U][j].push_back({D, 0});
}
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
sort(all(who[i][j]));
sort(all(who2[i][j]));
who[i][j].erase(unique(all(who[i][j])), who[i][j].end());
who2[i][j].erase(unique(all(who2[i][j])), who2[i][j].end());
}
for (int i = n-1; i >= 0; i--) {
for (int j = m-1; j >= 0; j--) {
for (int k = 0; k < sz(who[i][j]); k++) {
int r = who[i][j][k][0];
if (i+1 < n) {
auto it = lower_bound(all(who[i+1][j]), ar<short, 2>{r, 0});
if (it != who[i+1][j].end() && (*it)[0] == r) who[i][j][k][1] = (*it)[1];
else who[i][j][k][1] = i;
}
else who[i][j][k][1] = i;
}
for (int k = 0; k < sz(who2[i][j]); k++) {
int d = who2[i][j][k][0];
if (j+1 < m) {
auto it = lower_bound(all(who2[i][j+1]), ar<short, 2>{d, 0});
if (it != who2[i][j+1].end() && (*it)[0] == d) who2[i][j][k][1] = (*it)[1];
else who2[i][j][k][1] = j;
}
else who2[i][j][k][1] = j;
}
}
}
ll ans = 0;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
iota(idx, idx + sz(who[i][j]), 0);
sort(idx, idx + sz(who[i][j]), [&](int x, int y) { return who[i][j][x][0] < who[i][j][y][0]; });
iota(idx2, idx2 + sz(who2[i][j]), 0);
sort(idx2, idx2 + sz(who2[i][j]), [&](int x, int y) { return who2[i][j][x][1] < who2[i][j][y][1]; });
int t = 0;
for (int k = 0; k < sz(who2[i][j]); k++) {
while (t < sz(who[i][j]) && who[i][j][idx[t]][0] <= who2[i][j][idx2[k]][1]) {
fw.update(who[i][j][idx[t++]][1], 1);
}
ans += fw.query(who2[i][j][idx2[k]][0], nax-1);
}
for (int k = 0; k < t; k++) fw.update(who[i][j][idx[k]][1], -1);
}
return ans;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:67:36: warning: narrowing conversion of 'R' from 'int' to 'short int' [-Wnarrowing]
67 | if (L <= R) who[i][L].push_back({R, 0});
| ^
rect.cpp:69:37: warning: narrowing conversion of 'D' from 'int' to 'short int' [-Wnarrowing]
69 | if (U <= D) who2[U][j].push_back({D, 0});
| ^
rect.cpp:82:59: warning: narrowing conversion of 'r' from 'int' to 'short int' [-Wnarrowing]
82 | auto it = lower_bound(all(who[i+1][j]), ar<short, 2>{r, 0});
| ^
rect.cpp:91:60: warning: narrowing conversion of 'd' from 'int' to 'short int' [-Wnarrowing]
91 | auto it = lower_bound(all(who2[i][j+1]), ar<short, 2>{d, 0});
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
296016 KB |
Output is correct |
2 |
Correct |
59 ms |
296504 KB |
Output is correct |
3 |
Correct |
61 ms |
296276 KB |
Output is correct |
4 |
Correct |
64 ms |
296504 KB |
Output is correct |
5 |
Correct |
61 ms |
296272 KB |
Output is correct |
6 |
Correct |
62 ms |
296248 KB |
Output is correct |
7 |
Correct |
59 ms |
296276 KB |
Output is correct |
8 |
Correct |
59 ms |
296016 KB |
Output is correct |
9 |
Correct |
61 ms |
296272 KB |
Output is correct |
10 |
Correct |
63 ms |
296372 KB |
Output is correct |
11 |
Correct |
64 ms |
296384 KB |
Output is correct |
12 |
Correct |
63 ms |
296388 KB |
Output is correct |
13 |
Correct |
58 ms |
296016 KB |
Output is correct |
14 |
Correct |
59 ms |
296144 KB |
Output is correct |
15 |
Correct |
58 ms |
296020 KB |
Output is correct |
16 |
Correct |
56 ms |
296020 KB |
Output is correct |
17 |
Correct |
62 ms |
296016 KB |
Output is correct |
18 |
Correct |
61 ms |
296020 KB |
Output is correct |
19 |
Correct |
84 ms |
296420 KB |
Output is correct |
20 |
Correct |
62 ms |
296276 KB |
Output is correct |
21 |
Correct |
61 ms |
296020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
296016 KB |
Output is correct |
2 |
Correct |
59 ms |
296504 KB |
Output is correct |
3 |
Correct |
61 ms |
296276 KB |
Output is correct |
4 |
Correct |
64 ms |
296504 KB |
Output is correct |
5 |
Correct |
61 ms |
296272 KB |
Output is correct |
6 |
Correct |
62 ms |
296248 KB |
Output is correct |
7 |
Correct |
59 ms |
296276 KB |
Output is correct |
8 |
Correct |
59 ms |
296016 KB |
Output is correct |
9 |
Correct |
61 ms |
296272 KB |
Output is correct |
10 |
Correct |
63 ms |
296372 KB |
Output is correct |
11 |
Correct |
64 ms |
296384 KB |
Output is correct |
12 |
Correct |
63 ms |
296388 KB |
Output is correct |
13 |
Correct |
58 ms |
296016 KB |
Output is correct |
14 |
Correct |
59 ms |
296144 KB |
Output is correct |
15 |
Correct |
58 ms |
296020 KB |
Output is correct |
16 |
Correct |
56 ms |
296020 KB |
Output is correct |
17 |
Correct |
62 ms |
296016 KB |
Output is correct |
18 |
Correct |
61 ms |
296020 KB |
Output is correct |
19 |
Correct |
84 ms |
296420 KB |
Output is correct |
20 |
Correct |
62 ms |
296276 KB |
Output is correct |
21 |
Correct |
61 ms |
296020 KB |
Output is correct |
22 |
Correct |
62 ms |
297392 KB |
Output is correct |
23 |
Correct |
65 ms |
297300 KB |
Output is correct |
24 |
Correct |
63 ms |
297336 KB |
Output is correct |
25 |
Correct |
72 ms |
297216 KB |
Output is correct |
26 |
Correct |
61 ms |
297296 KB |
Output is correct |
27 |
Correct |
60 ms |
297296 KB |
Output is correct |
28 |
Correct |
60 ms |
297300 KB |
Output is correct |
29 |
Correct |
68 ms |
296996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
296016 KB |
Output is correct |
2 |
Correct |
59 ms |
296504 KB |
Output is correct |
3 |
Correct |
61 ms |
296276 KB |
Output is correct |
4 |
Correct |
64 ms |
296504 KB |
Output is correct |
5 |
Correct |
61 ms |
296272 KB |
Output is correct |
6 |
Correct |
62 ms |
296248 KB |
Output is correct |
7 |
Correct |
59 ms |
296276 KB |
Output is correct |
8 |
Correct |
59 ms |
296016 KB |
Output is correct |
9 |
Correct |
61 ms |
296272 KB |
Output is correct |
10 |
Correct |
63 ms |
296372 KB |
Output is correct |
11 |
Correct |
64 ms |
296384 KB |
Output is correct |
12 |
Correct |
63 ms |
296388 KB |
Output is correct |
13 |
Correct |
58 ms |
296016 KB |
Output is correct |
14 |
Correct |
59 ms |
296144 KB |
Output is correct |
15 |
Correct |
58 ms |
296020 KB |
Output is correct |
16 |
Correct |
56 ms |
296020 KB |
Output is correct |
17 |
Correct |
62 ms |
297392 KB |
Output is correct |
18 |
Correct |
65 ms |
297300 KB |
Output is correct |
19 |
Correct |
63 ms |
297336 KB |
Output is correct |
20 |
Correct |
72 ms |
297216 KB |
Output is correct |
21 |
Correct |
61 ms |
297296 KB |
Output is correct |
22 |
Correct |
60 ms |
297296 KB |
Output is correct |
23 |
Correct |
60 ms |
297300 KB |
Output is correct |
24 |
Correct |
68 ms |
296996 KB |
Output is correct |
25 |
Correct |
62 ms |
296016 KB |
Output is correct |
26 |
Correct |
61 ms |
296020 KB |
Output is correct |
27 |
Correct |
84 ms |
296420 KB |
Output is correct |
28 |
Correct |
62 ms |
296276 KB |
Output is correct |
29 |
Correct |
61 ms |
296020 KB |
Output is correct |
30 |
Correct |
83 ms |
301396 KB |
Output is correct |
31 |
Correct |
79 ms |
301412 KB |
Output is correct |
32 |
Correct |
86 ms |
301512 KB |
Output is correct |
33 |
Correct |
68 ms |
299752 KB |
Output is correct |
34 |
Correct |
77 ms |
300380 KB |
Output is correct |
35 |
Correct |
70 ms |
300356 KB |
Output is correct |
36 |
Correct |
95 ms |
300124 KB |
Output is correct |
37 |
Correct |
82 ms |
300248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
296016 KB |
Output is correct |
2 |
Correct |
59 ms |
296504 KB |
Output is correct |
3 |
Correct |
61 ms |
296276 KB |
Output is correct |
4 |
Correct |
64 ms |
296504 KB |
Output is correct |
5 |
Correct |
61 ms |
296272 KB |
Output is correct |
6 |
Correct |
62 ms |
296248 KB |
Output is correct |
7 |
Correct |
59 ms |
296276 KB |
Output is correct |
8 |
Correct |
59 ms |
296016 KB |
Output is correct |
9 |
Correct |
61 ms |
296272 KB |
Output is correct |
10 |
Correct |
63 ms |
296372 KB |
Output is correct |
11 |
Correct |
64 ms |
296384 KB |
Output is correct |
12 |
Correct |
63 ms |
296388 KB |
Output is correct |
13 |
Correct |
58 ms |
296016 KB |
Output is correct |
14 |
Correct |
59 ms |
296144 KB |
Output is correct |
15 |
Correct |
58 ms |
296020 KB |
Output is correct |
16 |
Correct |
56 ms |
296020 KB |
Output is correct |
17 |
Correct |
62 ms |
297392 KB |
Output is correct |
18 |
Correct |
65 ms |
297300 KB |
Output is correct |
19 |
Correct |
63 ms |
297336 KB |
Output is correct |
20 |
Correct |
72 ms |
297216 KB |
Output is correct |
21 |
Correct |
61 ms |
297296 KB |
Output is correct |
22 |
Correct |
60 ms |
297296 KB |
Output is correct |
23 |
Correct |
60 ms |
297300 KB |
Output is correct |
24 |
Correct |
68 ms |
296996 KB |
Output is correct |
25 |
Correct |
83 ms |
301396 KB |
Output is correct |
26 |
Correct |
79 ms |
301412 KB |
Output is correct |
27 |
Correct |
86 ms |
301512 KB |
Output is correct |
28 |
Correct |
68 ms |
299752 KB |
Output is correct |
29 |
Correct |
77 ms |
300380 KB |
Output is correct |
30 |
Correct |
70 ms |
300356 KB |
Output is correct |
31 |
Correct |
95 ms |
300124 KB |
Output is correct |
32 |
Correct |
82 ms |
300248 KB |
Output is correct |
33 |
Correct |
62 ms |
296016 KB |
Output is correct |
34 |
Correct |
61 ms |
296020 KB |
Output is correct |
35 |
Correct |
84 ms |
296420 KB |
Output is correct |
36 |
Correct |
62 ms |
296276 KB |
Output is correct |
37 |
Correct |
61 ms |
296020 KB |
Output is correct |
38 |
Correct |
111 ms |
327860 KB |
Output is correct |
39 |
Correct |
118 ms |
321792 KB |
Output is correct |
40 |
Correct |
117 ms |
321616 KB |
Output is correct |
41 |
Correct |
110 ms |
315472 KB |
Output is correct |
42 |
Correct |
147 ms |
343120 KB |
Output is correct |
43 |
Correct |
153 ms |
343120 KB |
Output is correct |
44 |
Correct |
153 ms |
343120 KB |
Output is correct |
45 |
Correct |
154 ms |
340160 KB |
Output is correct |
46 |
Correct |
145 ms |
320596 KB |
Output is correct |
47 |
Correct |
187 ms |
323152 KB |
Output is correct |
48 |
Correct |
202 ms |
328280 KB |
Output is correct |
49 |
Correct |
214 ms |
328296 KB |
Output is correct |
50 |
Correct |
150 ms |
318032 KB |
Output is correct |
51 |
Correct |
139 ms |
311680 KB |
Output is correct |
52 |
Correct |
229 ms |
327764 KB |
Output is correct |
53 |
Correct |
218 ms |
327396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
296296 KB |
Output is correct |
2 |
Correct |
63 ms |
296276 KB |
Output is correct |
3 |
Correct |
74 ms |
296220 KB |
Output is correct |
4 |
Correct |
60 ms |
296016 KB |
Output is correct |
5 |
Correct |
68 ms |
296132 KB |
Output is correct |
6 |
Correct |
64 ms |
296276 KB |
Output is correct |
7 |
Correct |
62 ms |
296164 KB |
Output is correct |
8 |
Correct |
73 ms |
296276 KB |
Output is correct |
9 |
Correct |
69 ms |
296268 KB |
Output is correct |
10 |
Correct |
61 ms |
295996 KB |
Output is correct |
11 |
Correct |
65 ms |
296020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
296016 KB |
Output is correct |
2 |
Correct |
61 ms |
296020 KB |
Output is correct |
3 |
Correct |
84 ms |
296420 KB |
Output is correct |
4 |
Correct |
62 ms |
296276 KB |
Output is correct |
5 |
Correct |
61 ms |
296020 KB |
Output is correct |
6 |
Correct |
61 ms |
296016 KB |
Output is correct |
7 |
Correct |
500 ms |
388176 KB |
Output is correct |
8 |
Correct |
1084 ms |
493404 KB |
Output is correct |
9 |
Correct |
1016 ms |
494300 KB |
Output is correct |
10 |
Correct |
1006 ms |
494416 KB |
Output is correct |
11 |
Correct |
177 ms |
343376 KB |
Output is correct |
12 |
Correct |
293 ms |
390116 KB |
Output is correct |
13 |
Correct |
350 ms |
393296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
296016 KB |
Output is correct |
2 |
Correct |
59 ms |
296504 KB |
Output is correct |
3 |
Correct |
61 ms |
296276 KB |
Output is correct |
4 |
Correct |
64 ms |
296504 KB |
Output is correct |
5 |
Correct |
61 ms |
296272 KB |
Output is correct |
6 |
Correct |
62 ms |
296248 KB |
Output is correct |
7 |
Correct |
59 ms |
296276 KB |
Output is correct |
8 |
Correct |
59 ms |
296016 KB |
Output is correct |
9 |
Correct |
61 ms |
296272 KB |
Output is correct |
10 |
Correct |
63 ms |
296372 KB |
Output is correct |
11 |
Correct |
64 ms |
296384 KB |
Output is correct |
12 |
Correct |
63 ms |
296388 KB |
Output is correct |
13 |
Correct |
58 ms |
296016 KB |
Output is correct |
14 |
Correct |
59 ms |
296144 KB |
Output is correct |
15 |
Correct |
58 ms |
296020 KB |
Output is correct |
16 |
Correct |
56 ms |
296020 KB |
Output is correct |
17 |
Correct |
62 ms |
297392 KB |
Output is correct |
18 |
Correct |
65 ms |
297300 KB |
Output is correct |
19 |
Correct |
63 ms |
297336 KB |
Output is correct |
20 |
Correct |
72 ms |
297216 KB |
Output is correct |
21 |
Correct |
61 ms |
297296 KB |
Output is correct |
22 |
Correct |
60 ms |
297296 KB |
Output is correct |
23 |
Correct |
60 ms |
297300 KB |
Output is correct |
24 |
Correct |
68 ms |
296996 KB |
Output is correct |
25 |
Correct |
83 ms |
301396 KB |
Output is correct |
26 |
Correct |
79 ms |
301412 KB |
Output is correct |
27 |
Correct |
86 ms |
301512 KB |
Output is correct |
28 |
Correct |
68 ms |
299752 KB |
Output is correct |
29 |
Correct |
77 ms |
300380 KB |
Output is correct |
30 |
Correct |
70 ms |
300356 KB |
Output is correct |
31 |
Correct |
95 ms |
300124 KB |
Output is correct |
32 |
Correct |
82 ms |
300248 KB |
Output is correct |
33 |
Correct |
111 ms |
327860 KB |
Output is correct |
34 |
Correct |
118 ms |
321792 KB |
Output is correct |
35 |
Correct |
117 ms |
321616 KB |
Output is correct |
36 |
Correct |
110 ms |
315472 KB |
Output is correct |
37 |
Correct |
147 ms |
343120 KB |
Output is correct |
38 |
Correct |
153 ms |
343120 KB |
Output is correct |
39 |
Correct |
153 ms |
343120 KB |
Output is correct |
40 |
Correct |
154 ms |
340160 KB |
Output is correct |
41 |
Correct |
145 ms |
320596 KB |
Output is correct |
42 |
Correct |
187 ms |
323152 KB |
Output is correct |
43 |
Correct |
202 ms |
328280 KB |
Output is correct |
44 |
Correct |
214 ms |
328296 KB |
Output is correct |
45 |
Correct |
150 ms |
318032 KB |
Output is correct |
46 |
Correct |
139 ms |
311680 KB |
Output is correct |
47 |
Correct |
229 ms |
327764 KB |
Output is correct |
48 |
Correct |
218 ms |
327396 KB |
Output is correct |
49 |
Correct |
64 ms |
296296 KB |
Output is correct |
50 |
Correct |
63 ms |
296276 KB |
Output is correct |
51 |
Correct |
74 ms |
296220 KB |
Output is correct |
52 |
Correct |
60 ms |
296016 KB |
Output is correct |
53 |
Correct |
68 ms |
296132 KB |
Output is correct |
54 |
Correct |
64 ms |
296276 KB |
Output is correct |
55 |
Correct |
62 ms |
296164 KB |
Output is correct |
56 |
Correct |
73 ms |
296276 KB |
Output is correct |
57 |
Correct |
69 ms |
296268 KB |
Output is correct |
58 |
Correct |
61 ms |
295996 KB |
Output is correct |
59 |
Correct |
65 ms |
296020 KB |
Output is correct |
60 |
Correct |
61 ms |
296016 KB |
Output is correct |
61 |
Correct |
500 ms |
388176 KB |
Output is correct |
62 |
Correct |
1084 ms |
493404 KB |
Output is correct |
63 |
Correct |
1016 ms |
494300 KB |
Output is correct |
64 |
Correct |
1006 ms |
494416 KB |
Output is correct |
65 |
Correct |
177 ms |
343376 KB |
Output is correct |
66 |
Correct |
293 ms |
390116 KB |
Output is correct |
67 |
Correct |
350 ms |
393296 KB |
Output is correct |
68 |
Correct |
62 ms |
296016 KB |
Output is correct |
69 |
Correct |
61 ms |
296020 KB |
Output is correct |
70 |
Correct |
84 ms |
296420 KB |
Output is correct |
71 |
Correct |
62 ms |
296276 KB |
Output is correct |
72 |
Correct |
61 ms |
296020 KB |
Output is correct |
73 |
Correct |
764 ms |
593472 KB |
Output is correct |
74 |
Correct |
808 ms |
507732 KB |
Output is correct |
75 |
Correct |
761 ms |
507984 KB |
Output is correct |
76 |
Correct |
765 ms |
426836 KB |
Output is correct |
77 |
Correct |
1155 ms |
808196 KB |
Output is correct |
78 |
Correct |
1247 ms |
482040 KB |
Output is correct |
79 |
Correct |
1321 ms |
513980 KB |
Output is correct |
80 |
Correct |
2116 ms |
606452 KB |
Output is correct |
81 |
Correct |
1328 ms |
489576 KB |
Output is correct |
82 |
Correct |
1940 ms |
563820 KB |
Output is correct |
83 |
Correct |
2355 ms |
637528 KB |
Output is correct |
84 |
Correct |
1299 ms |
487856 KB |
Output is correct |
85 |
Correct |
2062 ms |
627924 KB |
Output is correct |
86 |
Correct |
2096 ms |
618160 KB |
Output is correct |
87 |
Correct |
760 ms |
636740 KB |
Output is correct |
88 |
Correct |
1229 ms |
831672 KB |
Output is correct |
89 |
Correct |
1223 ms |
831812 KB |
Output is correct |
90 |
Correct |
1215 ms |
832084 KB |
Output is correct |