#include "rect.h"
#include <vector>
#include <cassert>
#include <cmath>
#include <stack>
#include <algorithm>
#include <iostream>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 2500;
std::vector<std::pair<int,int>> down[1 + nmax][1 + nmax];
std::vector<std::pair<int,int>> right[1 + nmax][1 + nmax];
class FenwickTree{
private:
std::vector<int> aib;
int n;
public:
FenwickTree(int n_) {
n = n_;
aib.resize(1 + n);
}
void update(int pos, int val) {
for(int x = pos; x <= n; x += (x ^ (x & (x - 1))))
aib[x] += val;
}
int query(int pos) {
int result = 0;
for(int x = pos; 0 < x; x = (x & (x - 1)))
result += aib[x];
return result;
}
};
struct Event{
int type;
int time;
int val;
bool operator < (Event const &a) const {
if(time != a.time)
return time > a.time;
else
return type < a.type;
}
};
long long count_rectangles(std::vector<std::vector<int>> v) {
int n = v.size();
int m = v[0].size();
for(int i = 0; i < n; i++) {
std::stack<int> st;
for(int j = m - 1; 0 <= j; j--) {
while(0 < st.size() && v[i][st.top()] < v[i][j]) {
if(j + 1 <= st.top() - 1)
right[i][j + 1].push_back({st.top() - 1 - j, 1});
st.pop();
}
if(0 < st.size()) {
if(j + 1 <= st.top() - 1)
right[i][j + 1].push_back({st.top() - 1 - j, 1});
if(v[i][st.top()] == v[i][j])
st.pop();
}
st.push(j);
}
}
for(int i = 0; i < m; i++) {
std::stack<int> st;
for(int j = n - 1; 0 <= j; j--) {
while(0 < st.size() && v[st.top()][i] < v[j][i]) {
if(j + 1 <= st.top() - 1)
down[j + 1][i].push_back({st.top() - 1 - j, 1});
st.pop();
}
if(0 < st.size()) {
if(j + 1 <= st.top() - 1)
down[j + 1][i].push_back({st.top() - 1 - j, 1});
if(v[st.top()][i] == v[j][i])
st.pop();
}
st.push(j);
}
}
for(int i = n - 1; 0 <= i; i--) {
for(int j = m - 1; 0 <= j; j--) {
for(int h = 0; h < right[i][j].size(); h++) {
std::pair<int,int> &el = right[i][j][h];
std::vector<std::pair<int,int>>::iterator it = std::lower_bound(right[i + 1][j].begin(), right[i + 1][j].end(), el);
if(it != right[i + 1][j].end() && it->first == el.first) {
el.second = it->second + 1;
}
}
for(int h = 0; h < down[i][j].size(); h++) {
std::pair<int,int> &el = down[i][j][h];
std::vector<std::pair<int,int>>::iterator it = std::lower_bound(down[i][j + 1].begin(), down[i][j + 1].end(), el);
if(it != down[i][j + 1].end() && it->first == el.first)
el.second = it->second + 1;
}
}
}
FenwickTree aib(nmax);
ll result = 0;
for(int i = 1; i <= n - 2; i++) {
for(int j = 1;j <= m - 2; j++) {
std::vector<Event> events;
for(int h = 0; h < right[i][j].size(); h++)
events.push_back({2, right[i][j][h].first, right[i][j][h].second});
for(int h = 0; h < down[i][j].size(); h++)
events.push_back({1, down[i][j][h].second, down[i][j][h].first});
std::sort(events.begin(), events.end());
for(int h = 0; h < events.size(); h++) {
if(events[h].type == 1)
aib.update(events[h].val, 1);
else
result += aib.query(events[h].val);
}
for(int h = 0; h < events.size(); h++)
if(events[h].type == 1)
aib.update(events[h].val, -1);
}
}
return result;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:90:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int h = 0; h < right[i][j].size(); h++) {
| ~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:97:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int h = 0; h < down[i][j].size(); h++) {
| ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:110:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int h = 0; h < right[i][j].size(); h++)
| ~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:112:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int h = 0; h < down[i][j].size(); h++)
| ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:115:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int h = 0; h < events.size(); h++) {
| ~~^~~~~~~~~~~~~~~
rect.cpp:121:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int h = 0; h < events.size(); h++)
| ~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
294264 KB |
Output is correct |
2 |
Correct |
190 ms |
294136 KB |
Output is correct |
3 |
Correct |
194 ms |
294104 KB |
Output is correct |
4 |
Correct |
194 ms |
294136 KB |
Output is correct |
5 |
Correct |
193 ms |
294076 KB |
Output is correct |
6 |
Correct |
190 ms |
294136 KB |
Output is correct |
7 |
Correct |
190 ms |
294136 KB |
Output is correct |
8 |
Correct |
193 ms |
294136 KB |
Output is correct |
9 |
Correct |
195 ms |
294136 KB |
Output is correct |
10 |
Correct |
194 ms |
294136 KB |
Output is correct |
11 |
Correct |
193 ms |
294136 KB |
Output is correct |
12 |
Correct |
192 ms |
294136 KB |
Output is correct |
13 |
Correct |
187 ms |
294136 KB |
Output is correct |
14 |
Correct |
189 ms |
294136 KB |
Output is correct |
15 |
Correct |
192 ms |
294136 KB |
Output is correct |
16 |
Correct |
193 ms |
294136 KB |
Output is correct |
17 |
Correct |
194 ms |
294136 KB |
Output is correct |
18 |
Correct |
194 ms |
294084 KB |
Output is correct |
19 |
Correct |
188 ms |
294136 KB |
Output is correct |
20 |
Correct |
192 ms |
294136 KB |
Output is correct |
21 |
Correct |
190 ms |
294136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
294264 KB |
Output is correct |
2 |
Correct |
190 ms |
294136 KB |
Output is correct |
3 |
Correct |
194 ms |
294104 KB |
Output is correct |
4 |
Correct |
194 ms |
294136 KB |
Output is correct |
5 |
Correct |
193 ms |
294076 KB |
Output is correct |
6 |
Correct |
190 ms |
294136 KB |
Output is correct |
7 |
Correct |
190 ms |
294136 KB |
Output is correct |
8 |
Correct |
193 ms |
294136 KB |
Output is correct |
9 |
Correct |
195 ms |
294136 KB |
Output is correct |
10 |
Correct |
194 ms |
294136 KB |
Output is correct |
11 |
Correct |
193 ms |
294136 KB |
Output is correct |
12 |
Correct |
192 ms |
294136 KB |
Output is correct |
13 |
Correct |
187 ms |
294136 KB |
Output is correct |
14 |
Correct |
189 ms |
294136 KB |
Output is correct |
15 |
Correct |
192 ms |
294136 KB |
Output is correct |
16 |
Correct |
193 ms |
294136 KB |
Output is correct |
17 |
Correct |
193 ms |
294648 KB |
Output is correct |
18 |
Correct |
192 ms |
294520 KB |
Output is correct |
19 |
Correct |
194 ms |
294520 KB |
Output is correct |
20 |
Correct |
192 ms |
294264 KB |
Output is correct |
21 |
Correct |
192 ms |
294392 KB |
Output is correct |
22 |
Correct |
197 ms |
294520 KB |
Output is correct |
23 |
Correct |
194 ms |
294392 KB |
Output is correct |
24 |
Correct |
192 ms |
294288 KB |
Output is correct |
25 |
Correct |
194 ms |
294136 KB |
Output is correct |
26 |
Correct |
194 ms |
294084 KB |
Output is correct |
27 |
Correct |
188 ms |
294136 KB |
Output is correct |
28 |
Correct |
192 ms |
294136 KB |
Output is correct |
29 |
Correct |
190 ms |
294136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
294264 KB |
Output is correct |
2 |
Correct |
190 ms |
294136 KB |
Output is correct |
3 |
Correct |
194 ms |
294104 KB |
Output is correct |
4 |
Correct |
194 ms |
294136 KB |
Output is correct |
5 |
Correct |
193 ms |
294076 KB |
Output is correct |
6 |
Correct |
190 ms |
294136 KB |
Output is correct |
7 |
Correct |
190 ms |
294136 KB |
Output is correct |
8 |
Correct |
193 ms |
294136 KB |
Output is correct |
9 |
Correct |
195 ms |
294136 KB |
Output is correct |
10 |
Correct |
194 ms |
294136 KB |
Output is correct |
11 |
Correct |
193 ms |
294136 KB |
Output is correct |
12 |
Correct |
192 ms |
294136 KB |
Output is correct |
13 |
Correct |
187 ms |
294136 KB |
Output is correct |
14 |
Correct |
189 ms |
294136 KB |
Output is correct |
15 |
Correct |
192 ms |
294136 KB |
Output is correct |
16 |
Correct |
193 ms |
294136 KB |
Output is correct |
17 |
Correct |
193 ms |
294648 KB |
Output is correct |
18 |
Correct |
192 ms |
294520 KB |
Output is correct |
19 |
Correct |
194 ms |
294520 KB |
Output is correct |
20 |
Correct |
192 ms |
294264 KB |
Output is correct |
21 |
Correct |
192 ms |
294392 KB |
Output is correct |
22 |
Correct |
197 ms |
294520 KB |
Output is correct |
23 |
Correct |
194 ms |
294392 KB |
Output is correct |
24 |
Correct |
192 ms |
294288 KB |
Output is correct |
25 |
Correct |
207 ms |
297080 KB |
Output is correct |
26 |
Correct |
209 ms |
297212 KB |
Output is correct |
27 |
Correct |
209 ms |
297208 KB |
Output is correct |
28 |
Correct |
208 ms |
295288 KB |
Output is correct |
29 |
Correct |
209 ms |
296056 KB |
Output is correct |
30 |
Correct |
211 ms |
296184 KB |
Output is correct |
31 |
Correct |
207 ms |
296028 KB |
Output is correct |
32 |
Correct |
207 ms |
296056 KB |
Output is correct |
33 |
Correct |
194 ms |
294136 KB |
Output is correct |
34 |
Correct |
194 ms |
294084 KB |
Output is correct |
35 |
Correct |
188 ms |
294136 KB |
Output is correct |
36 |
Correct |
192 ms |
294136 KB |
Output is correct |
37 |
Correct |
190 ms |
294136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
294264 KB |
Output is correct |
2 |
Correct |
190 ms |
294136 KB |
Output is correct |
3 |
Correct |
194 ms |
294104 KB |
Output is correct |
4 |
Correct |
194 ms |
294136 KB |
Output is correct |
5 |
Correct |
193 ms |
294076 KB |
Output is correct |
6 |
Correct |
190 ms |
294136 KB |
Output is correct |
7 |
Correct |
190 ms |
294136 KB |
Output is correct |
8 |
Correct |
193 ms |
294136 KB |
Output is correct |
9 |
Correct |
195 ms |
294136 KB |
Output is correct |
10 |
Correct |
194 ms |
294136 KB |
Output is correct |
11 |
Correct |
193 ms |
294136 KB |
Output is correct |
12 |
Correct |
192 ms |
294136 KB |
Output is correct |
13 |
Correct |
187 ms |
294136 KB |
Output is correct |
14 |
Correct |
189 ms |
294136 KB |
Output is correct |
15 |
Correct |
192 ms |
294136 KB |
Output is correct |
16 |
Correct |
193 ms |
294136 KB |
Output is correct |
17 |
Correct |
193 ms |
294648 KB |
Output is correct |
18 |
Correct |
192 ms |
294520 KB |
Output is correct |
19 |
Correct |
194 ms |
294520 KB |
Output is correct |
20 |
Correct |
192 ms |
294264 KB |
Output is correct |
21 |
Correct |
192 ms |
294392 KB |
Output is correct |
22 |
Correct |
197 ms |
294520 KB |
Output is correct |
23 |
Correct |
194 ms |
294392 KB |
Output is correct |
24 |
Correct |
192 ms |
294288 KB |
Output is correct |
25 |
Correct |
207 ms |
297080 KB |
Output is correct |
26 |
Correct |
209 ms |
297212 KB |
Output is correct |
27 |
Correct |
209 ms |
297208 KB |
Output is correct |
28 |
Correct |
208 ms |
295288 KB |
Output is correct |
29 |
Correct |
209 ms |
296056 KB |
Output is correct |
30 |
Correct |
211 ms |
296184 KB |
Output is correct |
31 |
Correct |
207 ms |
296028 KB |
Output is correct |
32 |
Correct |
207 ms |
296056 KB |
Output is correct |
33 |
Correct |
309 ms |
316420 KB |
Output is correct |
34 |
Correct |
306 ms |
311860 KB |
Output is correct |
35 |
Correct |
282 ms |
311672 KB |
Output is correct |
36 |
Correct |
281 ms |
306936 KB |
Output is correct |
37 |
Correct |
387 ms |
331752 KB |
Output is correct |
38 |
Correct |
377 ms |
331768 KB |
Output is correct |
39 |
Correct |
434 ms |
332152 KB |
Output is correct |
40 |
Correct |
379 ms |
329848 KB |
Output is correct |
41 |
Correct |
278 ms |
306712 KB |
Output is correct |
42 |
Correct |
304 ms |
309112 KB |
Output is correct |
43 |
Correct |
413 ms |
317788 KB |
Output is correct |
44 |
Correct |
431 ms |
319880 KB |
Output is correct |
45 |
Correct |
312 ms |
306960 KB |
Output is correct |
46 |
Correct |
313 ms |
306936 KB |
Output is correct |
47 |
Correct |
414 ms |
317568 KB |
Output is correct |
48 |
Correct |
419 ms |
318384 KB |
Output is correct |
49 |
Correct |
194 ms |
294136 KB |
Output is correct |
50 |
Correct |
194 ms |
294084 KB |
Output is correct |
51 |
Correct |
188 ms |
294136 KB |
Output is correct |
52 |
Correct |
192 ms |
294136 KB |
Output is correct |
53 |
Correct |
190 ms |
294136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
203 ms |
294504 KB |
Output is correct |
2 |
Correct |
203 ms |
294392 KB |
Output is correct |
3 |
Correct |
202 ms |
294168 KB |
Output is correct |
4 |
Correct |
198 ms |
294136 KB |
Output is correct |
5 |
Correct |
205 ms |
294392 KB |
Output is correct |
6 |
Correct |
200 ms |
294392 KB |
Output is correct |
7 |
Correct |
201 ms |
294392 KB |
Output is correct |
8 |
Correct |
200 ms |
294392 KB |
Output is correct |
9 |
Correct |
211 ms |
294392 KB |
Output is correct |
10 |
Correct |
205 ms |
294136 KB |
Output is correct |
11 |
Correct |
199 ms |
294316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
203 ms |
294136 KB |
Output is correct |
2 |
Correct |
774 ms |
367096 KB |
Output is correct |
3 |
Correct |
1523 ms |
452372 KB |
Output is correct |
4 |
Correct |
1522 ms |
453136 KB |
Output is correct |
5 |
Correct |
1509 ms |
453200 KB |
Output is correct |
6 |
Correct |
346 ms |
324368 KB |
Output is correct |
7 |
Correct |
487 ms |
351608 KB |
Output is correct |
8 |
Correct |
495 ms |
355576 KB |
Output is correct |
9 |
Correct |
194 ms |
294136 KB |
Output is correct |
10 |
Correct |
194 ms |
294084 KB |
Output is correct |
11 |
Correct |
188 ms |
294136 KB |
Output is correct |
12 |
Correct |
192 ms |
294136 KB |
Output is correct |
13 |
Correct |
190 ms |
294136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
294264 KB |
Output is correct |
2 |
Correct |
190 ms |
294136 KB |
Output is correct |
3 |
Correct |
194 ms |
294104 KB |
Output is correct |
4 |
Correct |
194 ms |
294136 KB |
Output is correct |
5 |
Correct |
193 ms |
294076 KB |
Output is correct |
6 |
Correct |
190 ms |
294136 KB |
Output is correct |
7 |
Correct |
190 ms |
294136 KB |
Output is correct |
8 |
Correct |
193 ms |
294136 KB |
Output is correct |
9 |
Correct |
195 ms |
294136 KB |
Output is correct |
10 |
Correct |
194 ms |
294136 KB |
Output is correct |
11 |
Correct |
193 ms |
294136 KB |
Output is correct |
12 |
Correct |
192 ms |
294136 KB |
Output is correct |
13 |
Correct |
187 ms |
294136 KB |
Output is correct |
14 |
Correct |
189 ms |
294136 KB |
Output is correct |
15 |
Correct |
192 ms |
294136 KB |
Output is correct |
16 |
Correct |
193 ms |
294136 KB |
Output is correct |
17 |
Correct |
193 ms |
294648 KB |
Output is correct |
18 |
Correct |
192 ms |
294520 KB |
Output is correct |
19 |
Correct |
194 ms |
294520 KB |
Output is correct |
20 |
Correct |
192 ms |
294264 KB |
Output is correct |
21 |
Correct |
192 ms |
294392 KB |
Output is correct |
22 |
Correct |
197 ms |
294520 KB |
Output is correct |
23 |
Correct |
194 ms |
294392 KB |
Output is correct |
24 |
Correct |
192 ms |
294288 KB |
Output is correct |
25 |
Correct |
207 ms |
297080 KB |
Output is correct |
26 |
Correct |
209 ms |
297212 KB |
Output is correct |
27 |
Correct |
209 ms |
297208 KB |
Output is correct |
28 |
Correct |
208 ms |
295288 KB |
Output is correct |
29 |
Correct |
209 ms |
296056 KB |
Output is correct |
30 |
Correct |
211 ms |
296184 KB |
Output is correct |
31 |
Correct |
207 ms |
296028 KB |
Output is correct |
32 |
Correct |
207 ms |
296056 KB |
Output is correct |
33 |
Correct |
309 ms |
316420 KB |
Output is correct |
34 |
Correct |
306 ms |
311860 KB |
Output is correct |
35 |
Correct |
282 ms |
311672 KB |
Output is correct |
36 |
Correct |
281 ms |
306936 KB |
Output is correct |
37 |
Correct |
387 ms |
331752 KB |
Output is correct |
38 |
Correct |
377 ms |
331768 KB |
Output is correct |
39 |
Correct |
434 ms |
332152 KB |
Output is correct |
40 |
Correct |
379 ms |
329848 KB |
Output is correct |
41 |
Correct |
278 ms |
306712 KB |
Output is correct |
42 |
Correct |
304 ms |
309112 KB |
Output is correct |
43 |
Correct |
413 ms |
317788 KB |
Output is correct |
44 |
Correct |
431 ms |
319880 KB |
Output is correct |
45 |
Correct |
312 ms |
306960 KB |
Output is correct |
46 |
Correct |
313 ms |
306936 KB |
Output is correct |
47 |
Correct |
414 ms |
317568 KB |
Output is correct |
48 |
Correct |
419 ms |
318384 KB |
Output is correct |
49 |
Correct |
203 ms |
294504 KB |
Output is correct |
50 |
Correct |
203 ms |
294392 KB |
Output is correct |
51 |
Correct |
202 ms |
294168 KB |
Output is correct |
52 |
Correct |
198 ms |
294136 KB |
Output is correct |
53 |
Correct |
205 ms |
294392 KB |
Output is correct |
54 |
Correct |
200 ms |
294392 KB |
Output is correct |
55 |
Correct |
201 ms |
294392 KB |
Output is correct |
56 |
Correct |
200 ms |
294392 KB |
Output is correct |
57 |
Correct |
211 ms |
294392 KB |
Output is correct |
58 |
Correct |
205 ms |
294136 KB |
Output is correct |
59 |
Correct |
199 ms |
294316 KB |
Output is correct |
60 |
Correct |
203 ms |
294136 KB |
Output is correct |
61 |
Correct |
774 ms |
367096 KB |
Output is correct |
62 |
Correct |
1523 ms |
452372 KB |
Output is correct |
63 |
Correct |
1522 ms |
453136 KB |
Output is correct |
64 |
Correct |
1509 ms |
453200 KB |
Output is correct |
65 |
Correct |
346 ms |
324368 KB |
Output is correct |
66 |
Correct |
487 ms |
351608 KB |
Output is correct |
67 |
Correct |
495 ms |
355576 KB |
Output is correct |
68 |
Correct |
2033 ms |
550176 KB |
Output is correct |
69 |
Correct |
2040 ms |
483304 KB |
Output is correct |
70 |
Correct |
1350 ms |
483220 KB |
Output is correct |
71 |
Correct |
1373 ms |
416496 KB |
Output is correct |
72 |
Correct |
3535 ms |
746028 KB |
Output is correct |
73 |
Correct |
2180 ms |
475780 KB |
Output is correct |
74 |
Correct |
2224 ms |
477612 KB |
Output is correct |
75 |
Correct |
3477 ms |
575356 KB |
Output is correct |
76 |
Correct |
2231 ms |
471720 KB |
Output is correct |
77 |
Correct |
2789 ms |
531776 KB |
Output is correct |
78 |
Correct |
3563 ms |
579024 KB |
Output is correct |
79 |
Correct |
2060 ms |
453784 KB |
Output is correct |
80 |
Correct |
3391 ms |
562552 KB |
Output is correct |
81 |
Correct |
3309 ms |
567032 KB |
Output is correct |
82 |
Correct |
2102 ms |
566776 KB |
Output is correct |
83 |
Correct |
3482 ms |
736760 KB |
Output is correct |
84 |
Correct |
3446 ms |
736944 KB |
Output is correct |
85 |
Correct |
3476 ms |
736948 KB |
Output is correct |
86 |
Correct |
194 ms |
294136 KB |
Output is correct |
87 |
Correct |
194 ms |
294084 KB |
Output is correct |
88 |
Correct |
188 ms |
294136 KB |
Output is correct |
89 |
Correct |
192 ms |
294136 KB |
Output is correct |
90 |
Correct |
190 ms |
294136 KB |
Output is correct |