// moreflags=grader.cpp
// 13
// It's hard to guess what's the bottleneck...
#include "rect.h"
#include<vector>
#include<set>
#include<algorithm>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
#include<climits>
struct T{
short right, depth;
T& operator=(T) && = delete;
};
struct Vector{
struct Node{T t; int next;};
static std::vector<Node> data;
int node;
int back;
Vector(): node(-1)
, back(-1)
{}
bool empty()const{return node<0;}
//struct Sentinel{};
struct Iterator: std::iterator<std::forward_iterator_tag, T>{
//using iterator_category=std::forward_iterator_tag;
int node;
Iterator(int node): node(node){} // because of the inheritance...
//bool operator==(Sentinel) const{return node<0;}
bool operator==(Iterator other) const{return node==other.node;}
bool operator!=(Iterator other) const{return node!=other.node;}
T& operator*() const{return data[node].t;} // too lazy to implement const-correctness correctly
T* operator->() const{return &data[node].t;}
Iterator& operator++(){ node=data[node].next; return *this; }
};
Iterator begin()const{ return {node}; }
Iterator end()const{ return {-1}; }
//Sentinel end(){ return {}; }
void push_back(T value){
if(node<0){
node=back=(int)data.size();
data.push_back({value, -1});
return;
}
assert(data[back].next<0);
back=data[back].next=(int)data.size();
data.push_back({value, -1});
}
void push_front(T value){
auto const newNode=(int)data.size();
data.push_back({value, node});
node=newNode;
}
};
std::vector<Vector::Node> Vector::data; // ...
long long count_rectangles(std::vector<std::vector<int> > a) {
using std::begin; using std::end;
if(a.size()<3 or a[0].size()<3) return 0;
Vector::data.reserve(2*a.size()*a[0].size());
using Segments=std::vector<Vector>;
auto const getSegments=[&](std::vector<int> const& data)->Segments{
if(data.empty()) return {};
Segments result(data.size()-1); // [l] -> list of valid r in reverse sorted order
struct Item{int value, index;};
std::vector<Item> stack; // strictly decreasing value, increasing index
for(int index=0; index<(int)data.size(); ++index){
auto const curValue=data[index];
while(not stack.empty()){
auto [prevValue, prevIndex]=stack.back();
if(prevValue<=curValue){
stack.pop_back();
if(prevIndex!=index-1) result[prevIndex+1].push_front({index, 1});
if(prevValue==curValue) break;
}else{
if(prevIndex!=index-1) result[prevIndex+1].push_front({index, 1});
break;
}
}
stack.push_back({curValue, index});
}
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());
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];
if(not v.empty()){
auto iterator=v.begin();
for(auto& [right, depth]: data[row][left]){
assert(depth==1);
while(true){
if(iterator==v.end()) goto break_outer;
if(iterator->right<=right) break;
++iterator;
}
if(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;}));
}
}
break_outer:;
}
}
}
};
computeDepth(rows);
computeDepth(cols);
struct Bit{
std::vector<int> data;
Bit(int number): data(number){}
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;
int64_t result{};
for(int up=1; up<(int)a.size()-1; ++up)
for(int left=1; left<(int)a[0].size()-1; ++left){
if(rows[up][left].empty() or cols[left][up].empty()) continue;
events.clear();
for(auto [right, depthDown]: rows[up][left])
events.push_back({EventType::get, right-left, depthDown});
for(auto [down, depthRight]: cols[left][up])
events.push_back({EventType::add, depthRight, down-up});
std::sort(begin(events), end(events));
for(auto [type, x, y]: events)
if(type==EventType::add){
bit.add(x, 1);
}else{
result+=bit.sumSuffix(x);
}
for(auto [type, x, y]: events)
if(type==EventType::add){
bit.add(x, -1);
}
}
return result;
}
Compilation message
rect.cpp: In lambda function:
rect.cpp:85:61: warning: narrowing conversion of 'index' from 'int' to 'short int' [-Wnarrowing]
85 | if(prevIndex!=index-1) result[prevIndex+1].push_front({index, 1});
| ^~~~~
rect.cpp:88:61: warning: narrowing conversion of 'index' from 'int' to 'short int' [-Wnarrowing]
88 | if(prevIndex!=index-1) result[prevIndex+1].push_front({index, 1});
| ^~~~~
rect.cpp:95:13: warning: unused variable 'it' [-Wunused-variable]
95 | for(auto& it: result)
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
0 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 |
1 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 |
0 ms |
256 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 |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
0 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 |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
512 KB |
Output is correct |
18 |
Correct |
1 ms |
512 KB |
Output is correct |
19 |
Correct |
1 ms |
512 KB |
Output is correct |
20 |
Correct |
1 ms |
512 KB |
Output is correct |
21 |
Correct |
2 ms |
512 KB |
Output is correct |
22 |
Correct |
1 ms |
512 KB |
Output is correct |
23 |
Correct |
2 ms |
512 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
0 ms |
256 KB |
Output is correct |
26 |
Correct |
0 ms |
256 KB |
Output is correct |
27 |
Correct |
0 ms |
256 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 |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
0 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 |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
512 KB |
Output is correct |
18 |
Correct |
1 ms |
512 KB |
Output is correct |
19 |
Correct |
1 ms |
512 KB |
Output is correct |
20 |
Correct |
1 ms |
512 KB |
Output is correct |
21 |
Correct |
2 ms |
512 KB |
Output is correct |
22 |
Correct |
1 ms |
512 KB |
Output is correct |
23 |
Correct |
2 ms |
512 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
6 ms |
1920 KB |
Output is correct |
26 |
Correct |
7 ms |
1920 KB |
Output is correct |
27 |
Correct |
8 ms |
1920 KB |
Output is correct |
28 |
Correct |
5 ms |
1536 KB |
Output is correct |
29 |
Correct |
7 ms |
1792 KB |
Output is correct |
30 |
Correct |
8 ms |
1792 KB |
Output is correct |
31 |
Correct |
7 ms |
1792 KB |
Output is correct |
32 |
Correct |
8 ms |
1792 KB |
Output is correct |
33 |
Correct |
0 ms |
256 KB |
Output is correct |
34 |
Correct |
0 ms |
256 KB |
Output is correct |
35 |
Correct |
0 ms |
256 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 |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
0 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 |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
512 KB |
Output is correct |
18 |
Correct |
1 ms |
512 KB |
Output is correct |
19 |
Correct |
1 ms |
512 KB |
Output is correct |
20 |
Correct |
1 ms |
512 KB |
Output is correct |
21 |
Correct |
2 ms |
512 KB |
Output is correct |
22 |
Correct |
1 ms |
512 KB |
Output is correct |
23 |
Correct |
2 ms |
512 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
6 ms |
1920 KB |
Output is correct |
26 |
Correct |
7 ms |
1920 KB |
Output is correct |
27 |
Correct |
8 ms |
1920 KB |
Output is correct |
28 |
Correct |
5 ms |
1536 KB |
Output is correct |
29 |
Correct |
7 ms |
1792 KB |
Output is correct |
30 |
Correct |
8 ms |
1792 KB |
Output is correct |
31 |
Correct |
7 ms |
1792 KB |
Output is correct |
32 |
Correct |
8 ms |
1792 KB |
Output is correct |
33 |
Correct |
37 ms |
15736 KB |
Output is correct |
34 |
Correct |
45 ms |
15736 KB |
Output is correct |
35 |
Correct |
52 ms |
15768 KB |
Output is correct |
36 |
Correct |
52 ms |
15736 KB |
Output is correct |
37 |
Correct |
81 ms |
19448 KB |
Output is correct |
38 |
Correct |
80 ms |
19448 KB |
Output is correct |
39 |
Correct |
83 ms |
19448 KB |
Output is correct |
40 |
Correct |
77 ms |
18296 KB |
Output is correct |
41 |
Correct |
39 ms |
13816 KB |
Output is correct |
42 |
Correct |
50 ms |
14840 KB |
Output is correct |
43 |
Correct |
94 ms |
19320 KB |
Output is correct |
44 |
Correct |
104 ms |
19348 KB |
Output is correct |
45 |
Correct |
50 ms |
9856 KB |
Output is correct |
46 |
Correct |
48 ms |
9848 KB |
Output is correct |
47 |
Correct |
93 ms |
18936 KB |
Output is correct |
48 |
Correct |
98 ms |
18812 KB |
Output is correct |
49 |
Correct |
0 ms |
256 KB |
Output is correct |
50 |
Correct |
0 ms |
256 KB |
Output is correct |
51 |
Correct |
0 ms |
256 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 |
2 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
512 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 |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
260 ms |
78840 KB |
Output is correct |
3 |
Correct |
589 ms |
170872 KB |
Output is correct |
4 |
Correct |
600 ms |
171748 KB |
Output is correct |
5 |
Correct |
592 ms |
171772 KB |
Output is correct |
6 |
Correct |
121 ms |
72856 KB |
Output is correct |
7 |
Correct |
272 ms |
138232 KB |
Output is correct |
8 |
Correct |
291 ms |
147320 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
256 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 |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
0 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 |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
512 KB |
Output is correct |
18 |
Correct |
1 ms |
512 KB |
Output is correct |
19 |
Correct |
1 ms |
512 KB |
Output is correct |
20 |
Correct |
1 ms |
512 KB |
Output is correct |
21 |
Correct |
2 ms |
512 KB |
Output is correct |
22 |
Correct |
1 ms |
512 KB |
Output is correct |
23 |
Correct |
2 ms |
512 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
6 ms |
1920 KB |
Output is correct |
26 |
Correct |
7 ms |
1920 KB |
Output is correct |
27 |
Correct |
8 ms |
1920 KB |
Output is correct |
28 |
Correct |
5 ms |
1536 KB |
Output is correct |
29 |
Correct |
7 ms |
1792 KB |
Output is correct |
30 |
Correct |
8 ms |
1792 KB |
Output is correct |
31 |
Correct |
7 ms |
1792 KB |
Output is correct |
32 |
Correct |
8 ms |
1792 KB |
Output is correct |
33 |
Correct |
37 ms |
15736 KB |
Output is correct |
34 |
Correct |
45 ms |
15736 KB |
Output is correct |
35 |
Correct |
52 ms |
15768 KB |
Output is correct |
36 |
Correct |
52 ms |
15736 KB |
Output is correct |
37 |
Correct |
81 ms |
19448 KB |
Output is correct |
38 |
Correct |
80 ms |
19448 KB |
Output is correct |
39 |
Correct |
83 ms |
19448 KB |
Output is correct |
40 |
Correct |
77 ms |
18296 KB |
Output is correct |
41 |
Correct |
39 ms |
13816 KB |
Output is correct |
42 |
Correct |
50 ms |
14840 KB |
Output is correct |
43 |
Correct |
94 ms |
19320 KB |
Output is correct |
44 |
Correct |
104 ms |
19348 KB |
Output is correct |
45 |
Correct |
50 ms |
9856 KB |
Output is correct |
46 |
Correct |
48 ms |
9848 KB |
Output is correct |
47 |
Correct |
93 ms |
18936 KB |
Output is correct |
48 |
Correct |
98 ms |
18812 KB |
Output is correct |
49 |
Correct |
2 ms |
512 KB |
Output is correct |
50 |
Correct |
1 ms |
512 KB |
Output is correct |
51 |
Correct |
1 ms |
512 KB |
Output is correct |
52 |
Correct |
0 ms |
256 KB |
Output is correct |
53 |
Correct |
1 ms |
512 KB |
Output is correct |
54 |
Correct |
1 ms |
512 KB |
Output is correct |
55 |
Correct |
1 ms |
512 KB |
Output is correct |
56 |
Correct |
1 ms |
512 KB |
Output is correct |
57 |
Correct |
1 ms |
512 KB |
Output is correct |
58 |
Correct |
0 ms |
384 KB |
Output is correct |
59 |
Correct |
0 ms |
384 KB |
Output is correct |
60 |
Correct |
0 ms |
256 KB |
Output is correct |
61 |
Correct |
260 ms |
78840 KB |
Output is correct |
62 |
Correct |
589 ms |
170872 KB |
Output is correct |
63 |
Correct |
600 ms |
171748 KB |
Output is correct |
64 |
Correct |
592 ms |
171772 KB |
Output is correct |
65 |
Correct |
121 ms |
72856 KB |
Output is correct |
66 |
Correct |
272 ms |
138232 KB |
Output is correct |
67 |
Correct |
291 ms |
147320 KB |
Output is correct |
68 |
Correct |
578 ms |
196432 KB |
Output is correct |
69 |
Correct |
636 ms |
196216 KB |
Output is correct |
70 |
Correct |
643 ms |
196348 KB |
Output is correct |
71 |
Correct |
736 ms |
196472 KB |
Output is correct |
72 |
Correct |
1611 ms |
245112 KB |
Output is correct |
73 |
Correct |
799 ms |
146072 KB |
Output is correct |
74 |
Correct |
884 ms |
154488 KB |
Output is correct |
75 |
Correct |
1351 ms |
243192 KB |
Output is correct |
76 |
Correct |
856 ms |
146680 KB |
Output is correct |
77 |
Correct |
1150 ms |
195832 KB |
Output is correct |
78 |
Correct |
1432 ms |
244600 KB |
Output is correct |
79 |
Correct |
793 ms |
142328 KB |
Output is correct |
80 |
Correct |
1422 ms |
237816 KB |
Output is correct |
81 |
Correct |
1383 ms |
231164 KB |
Output is correct |
82 |
Correct |
929 ms |
147320 KB |
Output is correct |
83 |
Correct |
1670 ms |
244940 KB |
Output is correct |
84 |
Correct |
1630 ms |
245368 KB |
Output is correct |
85 |
Correct |
1614 ms |
245240 KB |
Output is correct |
86 |
Correct |
0 ms |
256 KB |
Output is correct |
87 |
Correct |
0 ms |
256 KB |
Output is correct |
88 |
Correct |
0 ms |
256 KB |
Output is correct |
89 |
Correct |
0 ms |
256 KB |
Output is correct |
90 |
Correct |
0 ms |
256 KB |
Output is correct |