// moreflags=grader.cpp
// 13
// ...?
#include "rect.h"
#include<vector>
#include<set>
#include<algorithm>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
long long count_rectangles(std::vector<std::vector<int> > a) {
if(a.size()<3 or a[0].size()<3) return 0;
struct T{ int right, depth; };
using Segments=std::vector<std::vector<T>>;
auto const getSegments=[&](std::vector<int> const& data)->Segments{
Segments result(data.size()-1); // [l] -> list of valid r in reverse sorted order
struct Item{int value, index;};
std::vector<Item> items(data.size());
for(int index=0; index<(int)items.size(); ++index)
items[index]={data[index], index};
std::sort(begin(items), end(items),[&](Item first, Item sec){return first.value>sec.value;});
static std::set<int> done;
static std::vector<std::set<int>::node_type> segments;
if(segments.empty()){
for(int i=0; i<(int)std::max(a.size(), a[0].size()); ++i){
done.insert(i);
segments.push_back(done.extract(done.begin()));
}
}
assert(done.empty());
for(auto real: {false, true}){
assert(sizeof(Segments::value_type)>=sizeof(int));
for(auto& it: result)
assert(reinterpret_cast<int&>(it)==0);
for(auto [value, index]: items){
auto const [iterator, inserted, _nodeHandle]=done.insert(std::move(segments[index]));
assert(inserted);
auto const next=std::next(iterator);
if(iterator!=done.begin() and next!=done.end())
if(auto const prevValue=*std::prev(iterator); value<data[prevValue] and value<data[*next]){
if(real){
if(result[prevValue+1].size()>=result[prevValue+1].capacity()){ assert(false); __builtin_unreachable(); }
result[prevValue+1].push_back(T{*next, 1});
}else
++reinterpret_cast<int&>(result[prevValue+1]);
}
}
if(not real)
for(auto& it: result){
int const size=reinterpret_cast<int&>(it);
reinterpret_cast<int&>(it)=0;
it.reserve(size);
}
for(int index=0; index<(int)items.size(); ++index){
assert(*done.begin()==index);
segments[index]=done.extract(done.begin());
}
}
for(auto& it: result)
assert(std::is_sorted(begin(it), end(it), [&](T first, T sec){return first.right>sec.right;}));
return result;
};
std::vector<Segments> rows(a.size()-1), cols(a[0].size()-1);
for(int row=1; row<(int)a.size()-1; ++row)
rows[row]=getSegments(a[row]);
{
std::vector<int> tmp(a.size());
for(int col=1; col<(int)a[0].size()-1; ++col){
std::transform(begin(a), end(a), tmp.begin(),[&](std::vector<int> const& it){return it[col];});
cols[col]=getSegments(tmp);
}
}
auto const computeDepth=[&](std::vector<Segments>& data)->void{
if(data.size()<=2) return;
assert(data[0].empty()); // this is confusing.
for(int row=(int)data.size()-1; --row;){
for(int left=0; left<(int)data[row].size(); ++left){
auto const& v=data[row+1][left];
for(auto& [right, depth]: data[row][left]){
assert(depth==1);
auto const iterator=std::upper_bound(begin(v), end(v), right,
[&](int right, T item){ return item.right<=right; });
if(iterator!=v.end() and iterator->right==right)
depth=iterator->depth+1;
else{
assert(iterator==v.end() or iterator->right<right);
assert(iterator==v.begin() or iterator->right>right);
assert(std::is_sorted(begin(v), end(v), [&](T first, T sec){return first.right>sec.right;}));
}
}
}
}
};
computeDepth(rows);
computeDepth(cols);
struct Bit{
std::vector<int> data;
Bit(int number){reset(number);}
void reset(int number){data.assign(number, 0);}
void add(int index, int value){
for(; index>=0; index=(index&(index+1))-1)
data[index]+=value;
}
int sumSuffix(int index) const{
int result{};
for(; index<(int)data.size(); index|=index+1)
result+=data[index];
return result;
}
};
Bit bit((int)a[0].size()-1);
enum class EventType{ add, get };
struct Event{ EventType type; int x, y;
bool operator<(Event other) const{return std::tie(y, type)<std::tie(other.y, other.type);}
};
std::vector<Event> events;
std::vector<int> xs;
int64_t result{};
for(int up=1; up<(int)a.size()-1; ++up)
for(int left=1; left<(int)a[0].size()-1; ++left){
auto const A=(int)rows[up][left].size(), B=(int)cols[left][up].size();
if(A*B<=((31^__builtin_clz(A+B+4)))*(A+B)){
for(auto [right, depthDown]: rows[up][left])
for(auto [down, depthRight]: cols[left][up])
if(depthDown>=down-up and depthRight>=right-left)
++result;
}else{
events.clear();
xs.clear();
for(auto [right, depthDown]: rows[up][left]){
events.push_back({EventType::get, right-left, depthDown});
xs.push_back(right-left);
}
for(auto [down, depthRight]: cols[left][up]){
events.push_back({EventType::add, depthRight, down-up});
xs.push_back(depthRight);
}
std::sort(begin(events), end(events));
std::sort(begin(xs), end(xs));
xs.erase(std::unique(begin(xs), end(xs)), end(xs));
bit.reset(xs.size());
for(auto [type, x, y]: events){
x=int(std::lower_bound(begin(xs), end(xs), x)-begin(xs));
if(type==EventType::add){
bit.add(x, 1);
}else{
result+=bit.sumSuffix(x);
}
}
}
}
return result;
}
Compilation message
rect.cpp: In lambda function:
rect.cpp:40:14: warning: unused variable 'it' [-Wunused-variable]
40 | for(auto& it: result)
| ^~
rect.cpp:70:13: warning: unused variable 'it' [-Wunused-variable]
70 | for(auto& it: result)
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
0 ms |
256 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
0 ms |
256 KB |
Output is correct |
21 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
4 ms |
1024 KB |
Output is correct |
18 |
Correct |
4 ms |
1024 KB |
Output is correct |
19 |
Correct |
4 ms |
1024 KB |
Output is correct |
20 |
Correct |
5 ms |
768 KB |
Output is correct |
21 |
Correct |
5 ms |
896 KB |
Output is correct |
22 |
Correct |
5 ms |
896 KB |
Output is correct |
23 |
Correct |
5 ms |
896 KB |
Output is correct |
24 |
Correct |
3 ms |
512 KB |
Output is correct |
25 |
Correct |
0 ms |
256 KB |
Output is correct |
26 |
Correct |
0 ms |
256 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
0 ms |
256 KB |
Output is correct |
29 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
4 ms |
1024 KB |
Output is correct |
18 |
Correct |
4 ms |
1024 KB |
Output is correct |
19 |
Correct |
4 ms |
1024 KB |
Output is correct |
20 |
Correct |
5 ms |
768 KB |
Output is correct |
21 |
Correct |
5 ms |
896 KB |
Output is correct |
22 |
Correct |
5 ms |
896 KB |
Output is correct |
23 |
Correct |
5 ms |
896 KB |
Output is correct |
24 |
Correct |
3 ms |
512 KB |
Output is correct |
25 |
Correct |
26 ms |
4988 KB |
Output is correct |
26 |
Correct |
27 ms |
4992 KB |
Output is correct |
27 |
Correct |
27 ms |
4992 KB |
Output is correct |
28 |
Correct |
27 ms |
3328 KB |
Output is correct |
29 |
Correct |
33 ms |
3832 KB |
Output is correct |
30 |
Correct |
33 ms |
3832 KB |
Output is correct |
31 |
Correct |
33 ms |
3704 KB |
Output is correct |
32 |
Correct |
32 ms |
3712 KB |
Output is correct |
33 |
Correct |
0 ms |
256 KB |
Output is correct |
34 |
Correct |
0 ms |
256 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
0 ms |
256 KB |
Output is correct |
37 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
4 ms |
1024 KB |
Output is correct |
18 |
Correct |
4 ms |
1024 KB |
Output is correct |
19 |
Correct |
4 ms |
1024 KB |
Output is correct |
20 |
Correct |
5 ms |
768 KB |
Output is correct |
21 |
Correct |
5 ms |
896 KB |
Output is correct |
22 |
Correct |
5 ms |
896 KB |
Output is correct |
23 |
Correct |
5 ms |
896 KB |
Output is correct |
24 |
Correct |
3 ms |
512 KB |
Output is correct |
25 |
Correct |
26 ms |
4988 KB |
Output is correct |
26 |
Correct |
27 ms |
4992 KB |
Output is correct |
27 |
Correct |
27 ms |
4992 KB |
Output is correct |
28 |
Correct |
27 ms |
3328 KB |
Output is correct |
29 |
Correct |
33 ms |
3832 KB |
Output is correct |
30 |
Correct |
33 ms |
3832 KB |
Output is correct |
31 |
Correct |
33 ms |
3704 KB |
Output is correct |
32 |
Correct |
32 ms |
3712 KB |
Output is correct |
33 |
Correct |
298 ms |
42616 KB |
Output is correct |
34 |
Correct |
289 ms |
36732 KB |
Output is correct |
35 |
Correct |
289 ms |
36728 KB |
Output is correct |
36 |
Correct |
333 ms |
31224 KB |
Output is correct |
37 |
Correct |
356 ms |
57720 KB |
Output is correct |
38 |
Correct |
359 ms |
57592 KB |
Output is correct |
39 |
Correct |
363 ms |
57724 KB |
Output is correct |
40 |
Correct |
340 ms |
53880 KB |
Output is correct |
41 |
Correct |
349 ms |
34936 KB |
Output is correct |
42 |
Correct |
361 ms |
37368 KB |
Output is correct |
43 |
Correct |
464 ms |
43808 KB |
Output is correct |
44 |
Correct |
476 ms |
43616 KB |
Output is correct |
45 |
Correct |
229 ms |
21992 KB |
Output is correct |
46 |
Correct |
232 ms |
22008 KB |
Output is correct |
47 |
Correct |
455 ms |
42272 KB |
Output is correct |
48 |
Correct |
468 ms |
42232 KB |
Output is correct |
49 |
Correct |
0 ms |
256 KB |
Output is correct |
50 |
Correct |
0 ms |
256 KB |
Output is correct |
51 |
Correct |
1 ms |
384 KB |
Output is correct |
52 |
Correct |
0 ms |
256 KB |
Output is correct |
53 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
896 KB |
Output is correct |
2 |
Correct |
3 ms |
896 KB |
Output is correct |
3 |
Correct |
3 ms |
768 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
3 ms |
896 KB |
Output is correct |
6 |
Correct |
4 ms |
896 KB |
Output is correct |
7 |
Correct |
3 ms |
896 KB |
Output is correct |
8 |
Correct |
3 ms |
896 KB |
Output is correct |
9 |
Correct |
3 ms |
896 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
2080 ms |
202260 KB |
Output is correct |
3 |
Correct |
4618 ms |
438464 KB |
Output is correct |
4 |
Correct |
4637 ms |
440572 KB |
Output is correct |
5 |
Correct |
4709 ms |
440612 KB |
Output is correct |
6 |
Correct |
1712 ms |
169408 KB |
Output is correct |
7 |
Correct |
3418 ms |
321944 KB |
Output is correct |
8 |
Correct |
3557 ms |
343288 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
256 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
4 ms |
1024 KB |
Output is correct |
18 |
Correct |
4 ms |
1024 KB |
Output is correct |
19 |
Correct |
4 ms |
1024 KB |
Output is correct |
20 |
Correct |
5 ms |
768 KB |
Output is correct |
21 |
Correct |
5 ms |
896 KB |
Output is correct |
22 |
Correct |
5 ms |
896 KB |
Output is correct |
23 |
Correct |
5 ms |
896 KB |
Output is correct |
24 |
Correct |
3 ms |
512 KB |
Output is correct |
25 |
Correct |
26 ms |
4988 KB |
Output is correct |
26 |
Correct |
27 ms |
4992 KB |
Output is correct |
27 |
Correct |
27 ms |
4992 KB |
Output is correct |
28 |
Correct |
27 ms |
3328 KB |
Output is correct |
29 |
Correct |
33 ms |
3832 KB |
Output is correct |
30 |
Correct |
33 ms |
3832 KB |
Output is correct |
31 |
Correct |
33 ms |
3704 KB |
Output is correct |
32 |
Correct |
32 ms |
3712 KB |
Output is correct |
33 |
Correct |
298 ms |
42616 KB |
Output is correct |
34 |
Correct |
289 ms |
36732 KB |
Output is correct |
35 |
Correct |
289 ms |
36728 KB |
Output is correct |
36 |
Correct |
333 ms |
31224 KB |
Output is correct |
37 |
Correct |
356 ms |
57720 KB |
Output is correct |
38 |
Correct |
359 ms |
57592 KB |
Output is correct |
39 |
Correct |
363 ms |
57724 KB |
Output is correct |
40 |
Correct |
340 ms |
53880 KB |
Output is correct |
41 |
Correct |
349 ms |
34936 KB |
Output is correct |
42 |
Correct |
361 ms |
37368 KB |
Output is correct |
43 |
Correct |
464 ms |
43808 KB |
Output is correct |
44 |
Correct |
476 ms |
43616 KB |
Output is correct |
45 |
Correct |
229 ms |
21992 KB |
Output is correct |
46 |
Correct |
232 ms |
22008 KB |
Output is correct |
47 |
Correct |
455 ms |
42272 KB |
Output is correct |
48 |
Correct |
468 ms |
42232 KB |
Output is correct |
49 |
Correct |
4 ms |
896 KB |
Output is correct |
50 |
Correct |
3 ms |
896 KB |
Output is correct |
51 |
Correct |
3 ms |
768 KB |
Output is correct |
52 |
Correct |
0 ms |
256 KB |
Output is correct |
53 |
Correct |
3 ms |
896 KB |
Output is correct |
54 |
Correct |
4 ms |
896 KB |
Output is correct |
55 |
Correct |
3 ms |
896 KB |
Output is correct |
56 |
Correct |
3 ms |
896 KB |
Output is correct |
57 |
Correct |
3 ms |
896 KB |
Output is correct |
58 |
Correct |
0 ms |
384 KB |
Output is correct |
59 |
Correct |
0 ms |
384 KB |
Output is correct |
60 |
Correct |
1 ms |
256 KB |
Output is correct |
61 |
Correct |
2080 ms |
202260 KB |
Output is correct |
62 |
Correct |
4618 ms |
438464 KB |
Output is correct |
63 |
Correct |
4637 ms |
440572 KB |
Output is correct |
64 |
Correct |
4709 ms |
440612 KB |
Output is correct |
65 |
Correct |
1712 ms |
169408 KB |
Output is correct |
66 |
Correct |
3418 ms |
321944 KB |
Output is correct |
67 |
Correct |
3557 ms |
343288 KB |
Output is correct |
68 |
Correct |
4162 ms |
538628 KB |
Output is correct |
69 |
Correct |
4162 ms |
465352 KB |
Output is correct |
70 |
Correct |
4153 ms |
465244 KB |
Output is correct |
71 |
Correct |
4592 ms |
392068 KB |
Output is correct |
72 |
Execution timed out |
5084 ms |
733860 KB |
Time limit exceeded |
73 |
Halted |
0 ms |
0 KB |
- |