# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
837434 |
2023-08-25T10:48:51 Z |
finn__ |
Rectangles (IOI19_rect) |
C++17 |
|
3393 ms |
934116 KB |
#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
using L = long long;
template <typename T, int64_t N>
struct FenwickTree
{
T t[N];
void update(int64_t i, T x)
{
++i;
while (i <= N)
t[i - 1] += x, i += i & -i;
}
T prefix_sum(int64_t i)
{
T x = 0;
++i;
while (i)
x += t[i - 1], i -= i & -i;
return x;
}
};
constexpr size_t N = 2501;
vector<uint16_t> h[N][N];
vector<pair<uint16_t, uint16_t>> h_[N][N], v_[N][N];
FenwickTree<int32_t, N> tree;
L count_rectangles(vector<vector<int>> a)
{
size_t const n = a.size(), m = a[0].size();
for (size_t i = 0; i < n; ++i)
{
stack<size_t> s;
for (size_t j = 0; j < m; ++j)
{
while (!s.empty() && a[i][s.top()] < a[i][j])
s.pop();
if (!s.empty() && j - s.top() >= 2)
h[s.top()][j].push_back(i);
if (!s.empty() && a[i][s.top()] == a[i][j])
s.pop();
s.push(j);
}
while (!s.empty())
s.pop();
for (size_t j = m - 1; j < m; --j)
{
while (!s.empty() && a[i][s.top()] < a[i][j])
s.pop();
if (!s.empty() && s.top() - j >= 2 && a[i][s.top()] != a[i][j])
h[j][s.top()].push_back(i);
if (!s.empty() && a[i][s.top()] == a[i][j])
s.pop();
s.push(j);
}
}
for (size_t i = 0; i < m; ++i)
for (size_t j = i + 2; j < m; ++j)
for (size_t k = 0; k < h[i][j].size();)
{
size_t l = k + 1;
while (l < h[i][j].size() && h[i][j][l] == h[i][j][l - 1] + 1)
++l;
for (size_t p = k; p < l; ++p)
if (h[i][j][p])
h_[h[i][j][p] - 1][i].emplace_back(j, h[i][j][l - 1] + 1);
k = l;
}
for (auto &x : h)
for (auto &y : x)
y = vector<uint16_t>();
for (size_t j = 0; j < m; ++j)
{
stack<size_t> s;
for (size_t i = 0; i < n; ++i)
{
while (!s.empty() && a[s.top()][j] < a[i][j])
s.pop();
if (!s.empty() && i - s.top() >= 2)
h[s.top()][i].push_back(j);
if (!s.empty() && a[s.top()][j] == a[i][j])
s.pop();
s.push(i);
}
while (!s.empty())
s.pop();
for (size_t i = n - 1; i < n; --i)
{
while (!s.empty() && a[s.top()][j] < a[i][j])
s.pop();
if (!s.empty() && s.top() - i >= 2 && a[s.top()][j] != a[i][j])
h[i][s.top()].push_back(j);
if (!s.empty() && a[s.top()][j] == a[i][j])
s.pop();
s.push(i);
}
}
for (size_t i = 0; i < n; ++i)
for (size_t j = i + 2; j < n; ++j)
for (size_t k = 0; k < h[i][j].size();)
{
size_t l = k + 1;
while (l < h[i][j].size() && h[i][j][l] == h[i][j][l - 1] + 1)
++l;
for (size_t p = k; p < l; ++p)
if (h[i][j][p])
v_[i][h[i][j][p] - 1].emplace_back(j, h[i][j][l - 1] + 1);
k = l;
}
for (auto &x : h)
for (auto &y : x)
y = vector<uint16_t>();
L ans = 0;
for (size_t i = 0; i < n; ++i)
for (size_t j = 0; j < m; ++j)
{
sort(v_[i][j].begin(), v_[i][j].end(), [](auto const &a, auto const &b)
{ return a.second > b.second; });
sort(h_[i][j].begin(), h_[i][j].end(), [](auto const &a, auto const &b)
{ return a.first > b.first; });
auto it = v_[i][j].begin();
for (auto jt = h_[i][j].begin(); jt != h_[i][j].end(); ++jt)
{
while (it != v_[i][j].end() && it->second >= jt->first)
{
tree.update(it->first, 1);
++it;
}
L x = tree.prefix_sum(jt->second);
ans += x;
}
for (auto jt = v_[i][j].begin(); jt != it; ++jt)
tree.update(jt->first, -1);
v_[i][j] = vector<pair<uint16_t, uint16_t>>();
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
238 ms |
440956 KB |
Output is correct |
2 |
Correct |
243 ms |
441016 KB |
Output is correct |
3 |
Correct |
234 ms |
440968 KB |
Output is correct |
4 |
Correct |
240 ms |
441020 KB |
Output is correct |
5 |
Correct |
239 ms |
440956 KB |
Output is correct |
6 |
Correct |
233 ms |
440916 KB |
Output is correct |
7 |
Correct |
245 ms |
440924 KB |
Output is correct |
8 |
Correct |
243 ms |
440964 KB |
Output is correct |
9 |
Correct |
237 ms |
440972 KB |
Output is correct |
10 |
Correct |
236 ms |
440984 KB |
Output is correct |
11 |
Correct |
246 ms |
441100 KB |
Output is correct |
12 |
Correct |
235 ms |
440980 KB |
Output is correct |
13 |
Correct |
243 ms |
440864 KB |
Output is correct |
14 |
Correct |
235 ms |
440948 KB |
Output is correct |
15 |
Correct |
232 ms |
440956 KB |
Output is correct |
16 |
Correct |
234 ms |
440848 KB |
Output is correct |
17 |
Correct |
254 ms |
440908 KB |
Output is correct |
18 |
Correct |
232 ms |
440852 KB |
Output is correct |
19 |
Correct |
240 ms |
441044 KB |
Output is correct |
20 |
Correct |
239 ms |
440952 KB |
Output is correct |
21 |
Correct |
245 ms |
440948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
238 ms |
440956 KB |
Output is correct |
2 |
Correct |
243 ms |
441016 KB |
Output is correct |
3 |
Correct |
234 ms |
440968 KB |
Output is correct |
4 |
Correct |
240 ms |
441020 KB |
Output is correct |
5 |
Correct |
239 ms |
440956 KB |
Output is correct |
6 |
Correct |
233 ms |
440916 KB |
Output is correct |
7 |
Correct |
245 ms |
440924 KB |
Output is correct |
8 |
Correct |
243 ms |
440964 KB |
Output is correct |
9 |
Correct |
237 ms |
440972 KB |
Output is correct |
10 |
Correct |
236 ms |
440984 KB |
Output is correct |
11 |
Correct |
246 ms |
441100 KB |
Output is correct |
12 |
Correct |
235 ms |
440980 KB |
Output is correct |
13 |
Correct |
243 ms |
440864 KB |
Output is correct |
14 |
Correct |
235 ms |
440948 KB |
Output is correct |
15 |
Correct |
232 ms |
440956 KB |
Output is correct |
16 |
Correct |
234 ms |
440848 KB |
Output is correct |
17 |
Correct |
254 ms |
440908 KB |
Output is correct |
18 |
Correct |
232 ms |
440852 KB |
Output is correct |
19 |
Correct |
240 ms |
441044 KB |
Output is correct |
20 |
Correct |
239 ms |
440952 KB |
Output is correct |
21 |
Correct |
245 ms |
440948 KB |
Output is correct |
22 |
Correct |
246 ms |
441424 KB |
Output is correct |
23 |
Correct |
239 ms |
441404 KB |
Output is correct |
24 |
Correct |
243 ms |
441436 KB |
Output is correct |
25 |
Correct |
246 ms |
441084 KB |
Output is correct |
26 |
Correct |
256 ms |
441256 KB |
Output is correct |
27 |
Correct |
235 ms |
441180 KB |
Output is correct |
28 |
Correct |
250 ms |
441212 KB |
Output is correct |
29 |
Correct |
241 ms |
441056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
238 ms |
440956 KB |
Output is correct |
2 |
Correct |
243 ms |
441016 KB |
Output is correct |
3 |
Correct |
234 ms |
440968 KB |
Output is correct |
4 |
Correct |
240 ms |
441020 KB |
Output is correct |
5 |
Correct |
239 ms |
440956 KB |
Output is correct |
6 |
Correct |
233 ms |
440916 KB |
Output is correct |
7 |
Correct |
245 ms |
440924 KB |
Output is correct |
8 |
Correct |
243 ms |
440964 KB |
Output is correct |
9 |
Correct |
237 ms |
440972 KB |
Output is correct |
10 |
Correct |
236 ms |
440984 KB |
Output is correct |
11 |
Correct |
246 ms |
441100 KB |
Output is correct |
12 |
Correct |
235 ms |
440980 KB |
Output is correct |
13 |
Correct |
243 ms |
440864 KB |
Output is correct |
14 |
Correct |
235 ms |
440948 KB |
Output is correct |
15 |
Correct |
232 ms |
440956 KB |
Output is correct |
16 |
Correct |
234 ms |
440848 KB |
Output is correct |
17 |
Correct |
246 ms |
441424 KB |
Output is correct |
18 |
Correct |
239 ms |
441404 KB |
Output is correct |
19 |
Correct |
243 ms |
441436 KB |
Output is correct |
20 |
Correct |
246 ms |
441084 KB |
Output is correct |
21 |
Correct |
256 ms |
441256 KB |
Output is correct |
22 |
Correct |
235 ms |
441180 KB |
Output is correct |
23 |
Correct |
250 ms |
441212 KB |
Output is correct |
24 |
Correct |
241 ms |
441056 KB |
Output is correct |
25 |
Correct |
254 ms |
440908 KB |
Output is correct |
26 |
Correct |
232 ms |
440852 KB |
Output is correct |
27 |
Correct |
240 ms |
441044 KB |
Output is correct |
28 |
Correct |
239 ms |
440952 KB |
Output is correct |
29 |
Correct |
245 ms |
440948 KB |
Output is correct |
30 |
Correct |
253 ms |
443916 KB |
Output is correct |
31 |
Correct |
247 ms |
443976 KB |
Output is correct |
32 |
Correct |
255 ms |
443976 KB |
Output is correct |
33 |
Correct |
236 ms |
442220 KB |
Output is correct |
34 |
Correct |
261 ms |
442768 KB |
Output is correct |
35 |
Correct |
252 ms |
442888 KB |
Output is correct |
36 |
Correct |
259 ms |
442660 KB |
Output is correct |
37 |
Correct |
245 ms |
442696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
238 ms |
440956 KB |
Output is correct |
2 |
Correct |
243 ms |
441016 KB |
Output is correct |
3 |
Correct |
234 ms |
440968 KB |
Output is correct |
4 |
Correct |
240 ms |
441020 KB |
Output is correct |
5 |
Correct |
239 ms |
440956 KB |
Output is correct |
6 |
Correct |
233 ms |
440916 KB |
Output is correct |
7 |
Correct |
245 ms |
440924 KB |
Output is correct |
8 |
Correct |
243 ms |
440964 KB |
Output is correct |
9 |
Correct |
237 ms |
440972 KB |
Output is correct |
10 |
Correct |
236 ms |
440984 KB |
Output is correct |
11 |
Correct |
246 ms |
441100 KB |
Output is correct |
12 |
Correct |
235 ms |
440980 KB |
Output is correct |
13 |
Correct |
243 ms |
440864 KB |
Output is correct |
14 |
Correct |
235 ms |
440948 KB |
Output is correct |
15 |
Correct |
232 ms |
440956 KB |
Output is correct |
16 |
Correct |
234 ms |
440848 KB |
Output is correct |
17 |
Correct |
246 ms |
441424 KB |
Output is correct |
18 |
Correct |
239 ms |
441404 KB |
Output is correct |
19 |
Correct |
243 ms |
441436 KB |
Output is correct |
20 |
Correct |
246 ms |
441084 KB |
Output is correct |
21 |
Correct |
256 ms |
441256 KB |
Output is correct |
22 |
Correct |
235 ms |
441180 KB |
Output is correct |
23 |
Correct |
250 ms |
441212 KB |
Output is correct |
24 |
Correct |
241 ms |
441056 KB |
Output is correct |
25 |
Correct |
253 ms |
443916 KB |
Output is correct |
26 |
Correct |
247 ms |
443976 KB |
Output is correct |
27 |
Correct |
255 ms |
443976 KB |
Output is correct |
28 |
Correct |
236 ms |
442220 KB |
Output is correct |
29 |
Correct |
261 ms |
442768 KB |
Output is correct |
30 |
Correct |
252 ms |
442888 KB |
Output is correct |
31 |
Correct |
259 ms |
442660 KB |
Output is correct |
32 |
Correct |
245 ms |
442696 KB |
Output is correct |
33 |
Correct |
254 ms |
440908 KB |
Output is correct |
34 |
Correct |
232 ms |
440852 KB |
Output is correct |
35 |
Correct |
240 ms |
441044 KB |
Output is correct |
36 |
Correct |
239 ms |
440952 KB |
Output is correct |
37 |
Correct |
245 ms |
440948 KB |
Output is correct |
38 |
Correct |
358 ms |
467772 KB |
Output is correct |
39 |
Correct |
347 ms |
461576 KB |
Output is correct |
40 |
Correct |
331 ms |
461580 KB |
Output is correct |
41 |
Correct |
427 ms |
455556 KB |
Output is correct |
42 |
Correct |
324 ms |
476820 KB |
Output is correct |
43 |
Correct |
332 ms |
476896 KB |
Output is correct |
44 |
Correct |
331 ms |
476876 KB |
Output is correct |
45 |
Correct |
347 ms |
474572 KB |
Output is correct |
46 |
Correct |
320 ms |
453104 KB |
Output is correct |
47 |
Correct |
316 ms |
455788 KB |
Output is correct |
48 |
Correct |
393 ms |
462896 KB |
Output is correct |
49 |
Correct |
413 ms |
462796 KB |
Output is correct |
50 |
Correct |
340 ms |
452132 KB |
Output is correct |
51 |
Correct |
314 ms |
451888 KB |
Output is correct |
52 |
Correct |
389 ms |
460904 KB |
Output is correct |
53 |
Correct |
380 ms |
461012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
253 ms |
441244 KB |
Output is correct |
2 |
Correct |
266 ms |
441176 KB |
Output is correct |
3 |
Correct |
270 ms |
440920 KB |
Output is correct |
4 |
Correct |
342 ms |
441012 KB |
Output is correct |
5 |
Correct |
252 ms |
441336 KB |
Output is correct |
6 |
Correct |
251 ms |
441264 KB |
Output is correct |
7 |
Correct |
253 ms |
441236 KB |
Output is correct |
8 |
Correct |
257 ms |
441296 KB |
Output is correct |
9 |
Correct |
251 ms |
441192 KB |
Output is correct |
10 |
Correct |
263 ms |
441060 KB |
Output is correct |
11 |
Correct |
372 ms |
441100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
254 ms |
440908 KB |
Output is correct |
2 |
Correct |
232 ms |
440852 KB |
Output is correct |
3 |
Correct |
240 ms |
441044 KB |
Output is correct |
4 |
Correct |
239 ms |
440952 KB |
Output is correct |
5 |
Correct |
245 ms |
440948 KB |
Output is correct |
6 |
Correct |
242 ms |
440956 KB |
Output is correct |
7 |
Correct |
698 ms |
511188 KB |
Output is correct |
8 |
Correct |
1322 ms |
592580 KB |
Output is correct |
9 |
Correct |
1394 ms |
593356 KB |
Output is correct |
10 |
Correct |
1338 ms |
593432 KB |
Output is correct |
11 |
Correct |
372 ms |
465704 KB |
Output is correct |
12 |
Correct |
467 ms |
487400 KB |
Output is correct |
13 |
Correct |
528 ms |
490512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
238 ms |
440956 KB |
Output is correct |
2 |
Correct |
243 ms |
441016 KB |
Output is correct |
3 |
Correct |
234 ms |
440968 KB |
Output is correct |
4 |
Correct |
240 ms |
441020 KB |
Output is correct |
5 |
Correct |
239 ms |
440956 KB |
Output is correct |
6 |
Correct |
233 ms |
440916 KB |
Output is correct |
7 |
Correct |
245 ms |
440924 KB |
Output is correct |
8 |
Correct |
243 ms |
440964 KB |
Output is correct |
9 |
Correct |
237 ms |
440972 KB |
Output is correct |
10 |
Correct |
236 ms |
440984 KB |
Output is correct |
11 |
Correct |
246 ms |
441100 KB |
Output is correct |
12 |
Correct |
235 ms |
440980 KB |
Output is correct |
13 |
Correct |
243 ms |
440864 KB |
Output is correct |
14 |
Correct |
235 ms |
440948 KB |
Output is correct |
15 |
Correct |
232 ms |
440956 KB |
Output is correct |
16 |
Correct |
234 ms |
440848 KB |
Output is correct |
17 |
Correct |
246 ms |
441424 KB |
Output is correct |
18 |
Correct |
239 ms |
441404 KB |
Output is correct |
19 |
Correct |
243 ms |
441436 KB |
Output is correct |
20 |
Correct |
246 ms |
441084 KB |
Output is correct |
21 |
Correct |
256 ms |
441256 KB |
Output is correct |
22 |
Correct |
235 ms |
441180 KB |
Output is correct |
23 |
Correct |
250 ms |
441212 KB |
Output is correct |
24 |
Correct |
241 ms |
441056 KB |
Output is correct |
25 |
Correct |
253 ms |
443916 KB |
Output is correct |
26 |
Correct |
247 ms |
443976 KB |
Output is correct |
27 |
Correct |
255 ms |
443976 KB |
Output is correct |
28 |
Correct |
236 ms |
442220 KB |
Output is correct |
29 |
Correct |
261 ms |
442768 KB |
Output is correct |
30 |
Correct |
252 ms |
442888 KB |
Output is correct |
31 |
Correct |
259 ms |
442660 KB |
Output is correct |
32 |
Correct |
245 ms |
442696 KB |
Output is correct |
33 |
Correct |
358 ms |
467772 KB |
Output is correct |
34 |
Correct |
347 ms |
461576 KB |
Output is correct |
35 |
Correct |
331 ms |
461580 KB |
Output is correct |
36 |
Correct |
427 ms |
455556 KB |
Output is correct |
37 |
Correct |
324 ms |
476820 KB |
Output is correct |
38 |
Correct |
332 ms |
476896 KB |
Output is correct |
39 |
Correct |
331 ms |
476876 KB |
Output is correct |
40 |
Correct |
347 ms |
474572 KB |
Output is correct |
41 |
Correct |
320 ms |
453104 KB |
Output is correct |
42 |
Correct |
316 ms |
455788 KB |
Output is correct |
43 |
Correct |
393 ms |
462896 KB |
Output is correct |
44 |
Correct |
413 ms |
462796 KB |
Output is correct |
45 |
Correct |
340 ms |
452132 KB |
Output is correct |
46 |
Correct |
314 ms |
451888 KB |
Output is correct |
47 |
Correct |
389 ms |
460904 KB |
Output is correct |
48 |
Correct |
380 ms |
461012 KB |
Output is correct |
49 |
Correct |
253 ms |
441244 KB |
Output is correct |
50 |
Correct |
266 ms |
441176 KB |
Output is correct |
51 |
Correct |
270 ms |
440920 KB |
Output is correct |
52 |
Correct |
342 ms |
441012 KB |
Output is correct |
53 |
Correct |
252 ms |
441336 KB |
Output is correct |
54 |
Correct |
251 ms |
441264 KB |
Output is correct |
55 |
Correct |
253 ms |
441236 KB |
Output is correct |
56 |
Correct |
257 ms |
441296 KB |
Output is correct |
57 |
Correct |
251 ms |
441192 KB |
Output is correct |
58 |
Correct |
263 ms |
441060 KB |
Output is correct |
59 |
Correct |
372 ms |
441100 KB |
Output is correct |
60 |
Correct |
242 ms |
440956 KB |
Output is correct |
61 |
Correct |
698 ms |
511188 KB |
Output is correct |
62 |
Correct |
1322 ms |
592580 KB |
Output is correct |
63 |
Correct |
1394 ms |
593356 KB |
Output is correct |
64 |
Correct |
1338 ms |
593432 KB |
Output is correct |
65 |
Correct |
372 ms |
465704 KB |
Output is correct |
66 |
Correct |
467 ms |
487400 KB |
Output is correct |
67 |
Correct |
528 ms |
490512 KB |
Output is correct |
68 |
Correct |
254 ms |
440908 KB |
Output is correct |
69 |
Correct |
232 ms |
440852 KB |
Output is correct |
70 |
Correct |
240 ms |
441044 KB |
Output is correct |
71 |
Correct |
239 ms |
440952 KB |
Output is correct |
72 |
Correct |
245 ms |
440948 KB |
Output is correct |
73 |
Correct |
2125 ms |
783920 KB |
Output is correct |
74 |
Correct |
1710 ms |
702428 KB |
Output is correct |
75 |
Correct |
2258 ms |
702344 KB |
Output is correct |
76 |
Correct |
1086 ms |
621476 KB |
Output is correct |
77 |
Correct |
2499 ms |
904204 KB |
Output is correct |
78 |
Correct |
1701 ms |
604484 KB |
Output is correct |
79 |
Correct |
1946 ms |
616872 KB |
Output is correct |
80 |
Correct |
3006 ms |
712776 KB |
Output is correct |
81 |
Correct |
2039 ms |
604968 KB |
Output is correct |
82 |
Correct |
2600 ms |
662336 KB |
Output is correct |
83 |
Correct |
3393 ms |
714988 KB |
Output is correct |
84 |
Correct |
1708 ms |
592956 KB |
Output is correct |
85 |
Correct |
2836 ms |
696344 KB |
Output is correct |
86 |
Correct |
2578 ms |
688280 KB |
Output is correct |
87 |
Correct |
1637 ms |
715072 KB |
Output is correct |
88 |
Correct |
2569 ms |
926728 KB |
Output is correct |
89 |
Correct |
2699 ms |
934116 KB |
Output is correct |
90 |
Correct |
2696 ms |
933500 KB |
Output is correct |