#include "rect.h"
#include <cstdio>
#include <algorithm>
using namespace std;
bool goodRect(int i, int j, int exp) {
return j - i - 1 > 0 && exp >= j - i - 1;
}
struct Column {
int l1, l2, c;
};
const int MAX_N = 2500;
const int MAX_L = 12;
vector<Column> getColumns(const vector<vector<int> > matr) {
int N = matr.size(), M = matr[0].size();
vector<int> stiva(N, 0);
vector<Column> rez;
int top;
for(int c = 0; c < M; ++c) {
top = 0;
for(int l = 0; l < N; ++l) {
bool eq = false;
while(top > 0 && matr[l][c] >= matr[stiva[top - 1]][c]) {
if(l - stiva[top - 1] > 1)
rez.push_back({stiva[top - 1], l, c});
if(matr[l][c] == matr[stiva[top - 1]][c])
eq = true;
--top;
}
if(!eq && top > 0 && l - stiva[top - 1] > 1)
rez.push_back({stiva[top - 1], l, c});
stiva[top++] = l;
}
}
return rez;
}
bool cmp(Column a, Column b) {
return a.l1 < b.l1 || (a.l1 == b.l1 && a.l2 < b.l2) || (a.l1 == b.l1 && a.l2 == b.l2 && a.c < b.c);
}
int mylog[1+MAX_N];
int rmqleft[MAX_L][MAX_N][MAX_N];
int rmqright[MAX_L][MAX_N][MAX_N];
void initRmq(const vector<vector<int> > &a) {
int N = a.size(), M = a[0].size();
vector<int> stiva(M);
int top;
for(int l = 0; l < N; ++l)
for(int c = 0; c < M; ++c) {
rmqleft[0][l][c] = 0;
rmqright[0][l][c] = M - 1;
}
for(int l = 0; l < N; ++l) {
top = 0;
for(int c = 0; c < M; ++c) {
bool eq = false;
while(top > 0 && a[l][c] >= a[l][stiva[top - 1]]) {
rmqright[0][l][stiva[top - 1]] = c;
if(a[l][stiva[top - 1]] == a[l][c]) {
rmqleft[0][l][c] = stiva[top - 1];
eq = true;
}
--top;
}
if(!eq && top > 0)
rmqleft[0][l][c] = stiva[top - 1];
stiva[top++] = c;
}
}
for(int lg = 1; lg < MAX_L; ++lg)
for(int l = 0; l < N; ++l)
for(int c = 0; c < M; ++c) {
rmqleft[lg][l][c] = max(rmqleft[lg - 1][l][c], rmqleft[lg - 1][l + (1 << (lg - 1))][c]);
rmqright[lg][l][c] = min(rmqright[lg - 1][l][c], rmqright[lg - 1][l + (1 << (lg - 1))][c]);
}
for(int i = 2; i <= MAX_N; ++i)
mylog[i] = mylog[i / 2] + 1;
}
int queryRmq(int c, int l1, int l2, bool left) {
int lg = mylog[l2 - l1 + 1];
if(left)
return max(rmqleft[lg][l1][c], rmqleft[lg][l2 - (1 << lg) + 1][c]);
else
return min(rmqright[lg][l1][c], rmqright[lg][l2 - (1 << lg) + 1][c]);
}
int aib[1+MAX_N];
static inline int lsb(int x) {
return x & (-x);
}
void update(int poz, int val) {
poz++;
while(poz <= MAX_N) {
aib[poz] += val;
poz += lsb(poz);
}
}
int query(int poz) {
int rez = 0;
poz++;
while(poz > 0) {
rez += aib[poz];
poz -= lsb(poz);
}
return rez;
}
enum TypeEvent {
INSERT,
ERASE
};
struct Event {
TypeEvent type;
int x, c;
};
bool cmpEvent(Event &a, Event &b) {
return a.x < b.x || (a.x == b.x && a.type < b.type);
}
long long processRectangle(int c1, int c2, int l1, int l2) {
vector<Event> evs;
++l1;
--l2;
for(int c = c1; c <= c2; ++c) {
int left, right;
right = queryRmq(c, l1, l2, false);
evs.push_back({INSERT, c, c});
evs.push_back({ERASE, right, c});
}
sort(evs.begin(), evs.end(), cmpEvent);
int lastup = 0;
long long rez = 0LL;
for(int c = c1; c <= c2; ++c) {
while(lastup < evs.size() && evs[lastup].x == c && evs[lastup].type == INSERT) {
update(evs[lastup].c, 1);
++lastup;
}
int left = queryRmq(c, l1, l2, true);
rez = rez + query(max(c - 2, -1)) - query(max(left - 1, -1));
while(lastup < evs.size() && evs[lastup].x == c && evs[lastup].type == ERASE) {
update(evs[lastup].c, -1);
++lastup;
}
}
while(lastup < evs.size()) {
if(evs[lastup].type == INSERT)
update(evs[lastup].c, 1);
else
update(evs[lastup].c, -1);
++lastup;
}
return rez;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
int N, M;
long long sum = 0LL;
N = a.size();
M = a[0].size();
initRmq(a);
vector<Column> rez;
rez = getColumns(a);
sort(rez.begin(), rez.end(), cmp);
int i, j;
i = j = 0;
while(i < rez.size()) {
while(j < rez.size() && rez[i].l1 == rez[j].l1 && rez[i].l2 == rez[j].l2 && rez[i].c + (j - i) == rez[j].c)
++j;
sum = sum + processRectangle(max(0, rez[i].c - 1), min(M - 1, rez[j - 1].c + 1), rez[i].l1, rez[i].l2);
i = j;
}
return sum;
}
Compilation message
rect.cpp: In function 'long long int processRectangle(int, int, int, int)':
rect.cpp:148:7: warning: unused variable 'left' [-Wunused-variable]
int left, right;
^~~~
rect.cpp:160:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(lastup < evs.size() && evs[lastup].x == c && evs[lastup].type == INSERT) {
~~~~~~~^~~~~~~~~~~~
rect.cpp:168:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(lastup < evs.size() && evs[lastup].x == c && evs[lastup].type == ERASE) {
~~~~~~~^~~~~~~~~~~~
rect.cpp:174:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(lastup < evs.size()) {
~~~~~~~^~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:200:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i < rez.size()) {
~~^~~~~~~~~~~~
rect.cpp:201:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < rez.size() && rez[i].l1 == rez[j].l1 && rez[i].l2 == rez[j].l2 && rez[i].c + (j - i) == rez[j].c)
~~^~~~~~~~~~~~
rect.cpp:185:6: warning: variable 'N' set but not used [-Wunused-but-set-variable]
int N, M;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1016 KB |
Output is correct |
2 |
Correct |
5 ms |
3448 KB |
Output is correct |
3 |
Correct |
5 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3448 KB |
Output is correct |
5 |
Correct |
5 ms |
3368 KB |
Output is correct |
6 |
Correct |
5 ms |
3448 KB |
Output is correct |
7 |
Correct |
5 ms |
3320 KB |
Output is correct |
8 |
Correct |
3 ms |
1656 KB |
Output is correct |
9 |
Correct |
5 ms |
3448 KB |
Output is correct |
10 |
Correct |
5 ms |
3448 KB |
Output is correct |
11 |
Correct |
5 ms |
3448 KB |
Output is correct |
12 |
Correct |
5 ms |
3448 KB |
Output is correct |
13 |
Correct |
2 ms |
504 KB |
Output is correct |
14 |
Correct |
3 ms |
1400 KB |
Output is correct |
15 |
Correct |
3 ms |
1400 KB |
Output is correct |
16 |
Correct |
2 ms |
760 KB |
Output is correct |
17 |
Correct |
2 ms |
504 KB |
Output is correct |
18 |
Correct |
2 ms |
504 KB |
Output is correct |
19 |
Correct |
5 ms |
3448 KB |
Output is correct |
20 |
Correct |
5 ms |
3320 KB |
Output is correct |
21 |
Correct |
3 ms |
1400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1016 KB |
Output is correct |
2 |
Correct |
5 ms |
3448 KB |
Output is correct |
3 |
Correct |
5 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3448 KB |
Output is correct |
5 |
Correct |
5 ms |
3368 KB |
Output is correct |
6 |
Correct |
5 ms |
3448 KB |
Output is correct |
7 |
Correct |
5 ms |
3320 KB |
Output is correct |
8 |
Correct |
3 ms |
1656 KB |
Output is correct |
9 |
Correct |
5 ms |
3448 KB |
Output is correct |
10 |
Correct |
5 ms |
3448 KB |
Output is correct |
11 |
Correct |
5 ms |
3448 KB |
Output is correct |
12 |
Correct |
5 ms |
3448 KB |
Output is correct |
13 |
Correct |
2 ms |
504 KB |
Output is correct |
14 |
Correct |
3 ms |
1400 KB |
Output is correct |
15 |
Correct |
3 ms |
1400 KB |
Output is correct |
16 |
Correct |
2 ms |
760 KB |
Output is correct |
17 |
Correct |
12 ms |
8952 KB |
Output is correct |
18 |
Correct |
12 ms |
8952 KB |
Output is correct |
19 |
Correct |
12 ms |
8976 KB |
Output is correct |
20 |
Correct |
11 ms |
8824 KB |
Output is correct |
21 |
Correct |
15 ms |
8824 KB |
Output is correct |
22 |
Correct |
14 ms |
8952 KB |
Output is correct |
23 |
Correct |
13 ms |
8952 KB |
Output is correct |
24 |
Correct |
11 ms |
8568 KB |
Output is correct |
25 |
Correct |
2 ms |
504 KB |
Output is correct |
26 |
Correct |
2 ms |
504 KB |
Output is correct |
27 |
Correct |
5 ms |
3448 KB |
Output is correct |
28 |
Correct |
5 ms |
3320 KB |
Output is correct |
29 |
Correct |
3 ms |
1400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1016 KB |
Output is correct |
2 |
Correct |
5 ms |
3448 KB |
Output is correct |
3 |
Correct |
5 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3448 KB |
Output is correct |
5 |
Correct |
5 ms |
3368 KB |
Output is correct |
6 |
Correct |
5 ms |
3448 KB |
Output is correct |
7 |
Correct |
5 ms |
3320 KB |
Output is correct |
8 |
Correct |
3 ms |
1656 KB |
Output is correct |
9 |
Correct |
5 ms |
3448 KB |
Output is correct |
10 |
Correct |
5 ms |
3448 KB |
Output is correct |
11 |
Correct |
5 ms |
3448 KB |
Output is correct |
12 |
Correct |
5 ms |
3448 KB |
Output is correct |
13 |
Correct |
2 ms |
504 KB |
Output is correct |
14 |
Correct |
3 ms |
1400 KB |
Output is correct |
15 |
Correct |
3 ms |
1400 KB |
Output is correct |
16 |
Correct |
2 ms |
760 KB |
Output is correct |
17 |
Correct |
12 ms |
8952 KB |
Output is correct |
18 |
Correct |
12 ms |
8952 KB |
Output is correct |
19 |
Correct |
12 ms |
8976 KB |
Output is correct |
20 |
Correct |
11 ms |
8824 KB |
Output is correct |
21 |
Correct |
15 ms |
8824 KB |
Output is correct |
22 |
Correct |
14 ms |
8952 KB |
Output is correct |
23 |
Correct |
13 ms |
8952 KB |
Output is correct |
24 |
Correct |
11 ms |
8568 KB |
Output is correct |
25 |
Correct |
37 ms |
24820 KB |
Output is correct |
26 |
Correct |
37 ms |
24820 KB |
Output is correct |
27 |
Correct |
38 ms |
24820 KB |
Output is correct |
28 |
Correct |
35 ms |
24248 KB |
Output is correct |
29 |
Correct |
52 ms |
24820 KB |
Output is correct |
30 |
Correct |
50 ms |
24820 KB |
Output is correct |
31 |
Correct |
47 ms |
24816 KB |
Output is correct |
32 |
Correct |
47 ms |
24688 KB |
Output is correct |
33 |
Correct |
2 ms |
504 KB |
Output is correct |
34 |
Correct |
2 ms |
504 KB |
Output is correct |
35 |
Correct |
5 ms |
3448 KB |
Output is correct |
36 |
Correct |
5 ms |
3320 KB |
Output is correct |
37 |
Correct |
3 ms |
1400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1016 KB |
Output is correct |
2 |
Correct |
5 ms |
3448 KB |
Output is correct |
3 |
Correct |
5 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3448 KB |
Output is correct |
5 |
Correct |
5 ms |
3368 KB |
Output is correct |
6 |
Correct |
5 ms |
3448 KB |
Output is correct |
7 |
Correct |
5 ms |
3320 KB |
Output is correct |
8 |
Correct |
3 ms |
1656 KB |
Output is correct |
9 |
Correct |
5 ms |
3448 KB |
Output is correct |
10 |
Correct |
5 ms |
3448 KB |
Output is correct |
11 |
Correct |
5 ms |
3448 KB |
Output is correct |
12 |
Correct |
5 ms |
3448 KB |
Output is correct |
13 |
Correct |
2 ms |
504 KB |
Output is correct |
14 |
Correct |
3 ms |
1400 KB |
Output is correct |
15 |
Correct |
3 ms |
1400 KB |
Output is correct |
16 |
Correct |
2 ms |
760 KB |
Output is correct |
17 |
Correct |
12 ms |
8952 KB |
Output is correct |
18 |
Correct |
12 ms |
8952 KB |
Output is correct |
19 |
Correct |
12 ms |
8976 KB |
Output is correct |
20 |
Correct |
11 ms |
8824 KB |
Output is correct |
21 |
Correct |
15 ms |
8824 KB |
Output is correct |
22 |
Correct |
14 ms |
8952 KB |
Output is correct |
23 |
Correct |
13 ms |
8952 KB |
Output is correct |
24 |
Correct |
11 ms |
8568 KB |
Output is correct |
25 |
Correct |
37 ms |
24820 KB |
Output is correct |
26 |
Correct |
37 ms |
24820 KB |
Output is correct |
27 |
Correct |
38 ms |
24820 KB |
Output is correct |
28 |
Correct |
35 ms |
24248 KB |
Output is correct |
29 |
Correct |
52 ms |
24820 KB |
Output is correct |
30 |
Correct |
50 ms |
24820 KB |
Output is correct |
31 |
Correct |
47 ms |
24816 KB |
Output is correct |
32 |
Correct |
47 ms |
24688 KB |
Output is correct |
33 |
Correct |
277 ms |
122700 KB |
Output is correct |
34 |
Correct |
282 ms |
122672 KB |
Output is correct |
35 |
Correct |
268 ms |
122728 KB |
Output is correct |
36 |
Correct |
261 ms |
122748 KB |
Output is correct |
37 |
Correct |
306 ms |
125792 KB |
Output is correct |
38 |
Correct |
304 ms |
125924 KB |
Output is correct |
39 |
Correct |
306 ms |
125796 KB |
Output is correct |
40 |
Correct |
293 ms |
117988 KB |
Output is correct |
41 |
Correct |
210 ms |
121196 KB |
Output is correct |
42 |
Correct |
258 ms |
122728 KB |
Output is correct |
43 |
Correct |
451 ms |
125796 KB |
Output is correct |
44 |
Correct |
468 ms |
125764 KB |
Output is correct |
45 |
Correct |
262 ms |
97000 KB |
Output is correct |
46 |
Correct |
229 ms |
63204 KB |
Output is correct |
47 |
Correct |
412 ms |
125888 KB |
Output is correct |
48 |
Correct |
417 ms |
125968 KB |
Output is correct |
49 |
Correct |
2 ms |
504 KB |
Output is correct |
50 |
Correct |
2 ms |
504 KB |
Output is correct |
51 |
Correct |
5 ms |
3448 KB |
Output is correct |
52 |
Correct |
5 ms |
3320 KB |
Output is correct |
53 |
Correct |
3 ms |
1400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1528 KB |
Output is correct |
2 |
Correct |
4 ms |
1404 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
2 ms |
760 KB |
Output is correct |
5 |
Correct |
4 ms |
1400 KB |
Output is correct |
6 |
Correct |
4 ms |
1400 KB |
Output is correct |
7 |
Correct |
4 ms |
1400 KB |
Output is correct |
8 |
Correct |
4 ms |
1400 KB |
Output is correct |
9 |
Correct |
4 ms |
1400 KB |
Output is correct |
10 |
Correct |
3 ms |
888 KB |
Output is correct |
11 |
Correct |
3 ms |
1016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1400 KB |
Output is correct |
2 |
Correct |
950 ms |
336600 KB |
Output is correct |
3 |
Correct |
2003 ms |
682724 KB |
Output is correct |
4 |
Correct |
2016 ms |
686096 KB |
Output is correct |
5 |
Correct |
1980 ms |
685924 KB |
Output is correct |
6 |
Correct |
396 ms |
326776 KB |
Output is correct |
7 |
Correct |
803 ms |
656656 KB |
Output is correct |
8 |
Correct |
834 ms |
661144 KB |
Output is correct |
9 |
Correct |
2 ms |
504 KB |
Output is correct |
10 |
Correct |
2 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
3448 KB |
Output is correct |
12 |
Correct |
5 ms |
3320 KB |
Output is correct |
13 |
Correct |
3 ms |
1400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1016 KB |
Output is correct |
2 |
Correct |
5 ms |
3448 KB |
Output is correct |
3 |
Correct |
5 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3448 KB |
Output is correct |
5 |
Correct |
5 ms |
3368 KB |
Output is correct |
6 |
Correct |
5 ms |
3448 KB |
Output is correct |
7 |
Correct |
5 ms |
3320 KB |
Output is correct |
8 |
Correct |
3 ms |
1656 KB |
Output is correct |
9 |
Correct |
5 ms |
3448 KB |
Output is correct |
10 |
Correct |
5 ms |
3448 KB |
Output is correct |
11 |
Correct |
5 ms |
3448 KB |
Output is correct |
12 |
Correct |
5 ms |
3448 KB |
Output is correct |
13 |
Correct |
2 ms |
504 KB |
Output is correct |
14 |
Correct |
3 ms |
1400 KB |
Output is correct |
15 |
Correct |
3 ms |
1400 KB |
Output is correct |
16 |
Correct |
2 ms |
760 KB |
Output is correct |
17 |
Correct |
12 ms |
8952 KB |
Output is correct |
18 |
Correct |
12 ms |
8952 KB |
Output is correct |
19 |
Correct |
12 ms |
8976 KB |
Output is correct |
20 |
Correct |
11 ms |
8824 KB |
Output is correct |
21 |
Correct |
15 ms |
8824 KB |
Output is correct |
22 |
Correct |
14 ms |
8952 KB |
Output is correct |
23 |
Correct |
13 ms |
8952 KB |
Output is correct |
24 |
Correct |
11 ms |
8568 KB |
Output is correct |
25 |
Correct |
37 ms |
24820 KB |
Output is correct |
26 |
Correct |
37 ms |
24820 KB |
Output is correct |
27 |
Correct |
38 ms |
24820 KB |
Output is correct |
28 |
Correct |
35 ms |
24248 KB |
Output is correct |
29 |
Correct |
52 ms |
24820 KB |
Output is correct |
30 |
Correct |
50 ms |
24820 KB |
Output is correct |
31 |
Correct |
47 ms |
24816 KB |
Output is correct |
32 |
Correct |
47 ms |
24688 KB |
Output is correct |
33 |
Correct |
277 ms |
122700 KB |
Output is correct |
34 |
Correct |
282 ms |
122672 KB |
Output is correct |
35 |
Correct |
268 ms |
122728 KB |
Output is correct |
36 |
Correct |
261 ms |
122748 KB |
Output is correct |
37 |
Correct |
306 ms |
125792 KB |
Output is correct |
38 |
Correct |
304 ms |
125924 KB |
Output is correct |
39 |
Correct |
306 ms |
125796 KB |
Output is correct |
40 |
Correct |
293 ms |
117988 KB |
Output is correct |
41 |
Correct |
210 ms |
121196 KB |
Output is correct |
42 |
Correct |
258 ms |
122728 KB |
Output is correct |
43 |
Correct |
451 ms |
125796 KB |
Output is correct |
44 |
Correct |
468 ms |
125764 KB |
Output is correct |
45 |
Correct |
262 ms |
97000 KB |
Output is correct |
46 |
Correct |
229 ms |
63204 KB |
Output is correct |
47 |
Correct |
412 ms |
125888 KB |
Output is correct |
48 |
Correct |
417 ms |
125968 KB |
Output is correct |
49 |
Correct |
4 ms |
1528 KB |
Output is correct |
50 |
Correct |
4 ms |
1404 KB |
Output is correct |
51 |
Correct |
3 ms |
1272 KB |
Output is correct |
52 |
Correct |
2 ms |
760 KB |
Output is correct |
53 |
Correct |
4 ms |
1400 KB |
Output is correct |
54 |
Correct |
4 ms |
1400 KB |
Output is correct |
55 |
Correct |
4 ms |
1400 KB |
Output is correct |
56 |
Correct |
4 ms |
1400 KB |
Output is correct |
57 |
Correct |
4 ms |
1400 KB |
Output is correct |
58 |
Correct |
3 ms |
888 KB |
Output is correct |
59 |
Correct |
3 ms |
1016 KB |
Output is correct |
60 |
Correct |
3 ms |
1400 KB |
Output is correct |
61 |
Correct |
950 ms |
336600 KB |
Output is correct |
62 |
Correct |
2003 ms |
682724 KB |
Output is correct |
63 |
Correct |
2016 ms |
686096 KB |
Output is correct |
64 |
Correct |
1980 ms |
685924 KB |
Output is correct |
65 |
Correct |
396 ms |
326776 KB |
Output is correct |
66 |
Correct |
803 ms |
656656 KB |
Output is correct |
67 |
Correct |
834 ms |
661144 KB |
Output is correct |
68 |
Correct |
2962 ms |
710592 KB |
Output is correct |
69 |
Correct |
3410 ms |
710644 KB |
Output is correct |
70 |
Correct |
2905 ms |
710704 KB |
Output is correct |
71 |
Correct |
2770 ms |
710600 KB |
Output is correct |
72 |
Correct |
3523 ms |
759944 KB |
Output is correct |
73 |
Correct |
3146 ms |
446572 KB |
Output is correct |
74 |
Correct |
3513 ms |
683508 KB |
Output is correct |
75 |
Execution timed out |
5156 ms |
759856 KB |
Time limit exceeded |
76 |
Halted |
0 ms |
0 KB |
- |