// incorrect/rect-peyman-n3-opt.cpp
//In the name of God
//Peyman Jabbarzade Ganje
//Boarder shouldn't be equal with inside
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 3000 + 10, maxx=1e7;
int n,m;
long long ans;
vector<int>vec, nozoli, will_remove;
map<int, int> fp[maxn][maxn];
vector<pii> sp[2][maxn][maxn];
void add_pair(int type, int lvl, int l, int r)
{
int tmp = 1;
if(fp[lvl][l].find(r) != fp[lvl][l].end())
tmp += fp[lvl][l][r];
if(type == 0) {
if(r-l-1>0)
sp[type][lvl+1][r].push_back(pii(r-l-1, tmp));
}
else {
if(r-l-1>0)
sp[type][r][lvl+1].push_back(pii(tmp, r-l-1));
}
fp[lvl+1][l][r] = tmp;
}
void extract_pairs(int type, int lvl)
{
nozoli.clear();
for(int i=0;i<vec.size();i++)
{
int last=-1;
while(nozoli.size() && vec[nozoli.back()] < vec[i])
{
if(vec[nozoli.back()] > last)
add_pair(type, lvl, nozoli.back(), i);
last = vec[nozoli.back()];
nozoli.pop_back();
}
if(nozoli.size()) add_pair(type, lvl, nozoli.back(), i);
nozoli.push_back(i);
}
}
long long count_rectangles(vector<vector<int> >a)
{
n = a.size();
m = a[0].size();
for(int i=0;i<n;i++)
{
vec.clear();
for(int j=0;j<m;j++)
vec.push_back(a[i][j]);
extract_pairs(0,i);
}
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
fp[i][j].clear();
for(int j=0;j<m;j++)
{
vec.clear();
for(int i=0;i<n;i++)
vec.push_back(a[i][j]);
extract_pairs(1,j);
}
int tt = 0;
for(int i=0;i<=max(n,m);i++) {
for(int j=0;j<=max(n,m);j++) {
// cerr << "(" << sp[0][i][j].size() << "," << sp[1][i][j].size() << ") ";
if(sp[0][i][j].size() && sp[1][i][j].size())
{
// sp[0].X fix sp[1].X moteghaier
for(int x=0;x<sp[0][i][j].size();x++)
for(int y=0;y<sp[1][i][j].size();y++) {
tt++;
if(sp[0][i][j][x].X <= sp[1][i][j][y].X && sp[0][i][j][x].Y >= sp[1][i][j][y].Y)
ans ++;
}
}
}
// cerr << endl;
}
return ans;
}
Compilation message
rect.cpp: In function 'void extract_pairs(int, int)':
rect.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vec.size();i++)
~^~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:87:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int x=0;x<sp[0][i][j].size();x++)
~^~~~~~~~~~~~~~~~~~~
rect.cpp:88:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int y=0;y<sp[1][i][j].size();y++) {
~^~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
803 ms |
851672 KB |
Output is correct |
2 |
Correct |
757 ms |
851560 KB |
Output is correct |
3 |
Correct |
769 ms |
851548 KB |
Output is correct |
4 |
Correct |
748 ms |
851588 KB |
Output is correct |
5 |
Correct |
749 ms |
851412 KB |
Output is correct |
6 |
Correct |
749 ms |
851468 KB |
Output is correct |
7 |
Correct |
800 ms |
851460 KB |
Output is correct |
8 |
Correct |
756 ms |
851540 KB |
Output is correct |
9 |
Correct |
755 ms |
851508 KB |
Output is correct |
10 |
Correct |
799 ms |
851576 KB |
Output is correct |
11 |
Correct |
757 ms |
851576 KB |
Output is correct |
12 |
Correct |
745 ms |
851460 KB |
Output is correct |
13 |
Correct |
752 ms |
851436 KB |
Output is correct |
14 |
Correct |
749 ms |
851448 KB |
Output is correct |
15 |
Correct |
752 ms |
851448 KB |
Output is correct |
16 |
Correct |
753 ms |
851448 KB |
Output is correct |
17 |
Correct |
745 ms |
851448 KB |
Output is correct |
18 |
Correct |
747 ms |
851376 KB |
Output is correct |
19 |
Correct |
844 ms |
851708 KB |
Output is correct |
20 |
Correct |
750 ms |
851576 KB |
Output is correct |
21 |
Correct |
749 ms |
851448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
803 ms |
851672 KB |
Output is correct |
2 |
Correct |
757 ms |
851560 KB |
Output is correct |
3 |
Correct |
769 ms |
851548 KB |
Output is correct |
4 |
Correct |
748 ms |
851588 KB |
Output is correct |
5 |
Correct |
749 ms |
851412 KB |
Output is correct |
6 |
Correct |
749 ms |
851468 KB |
Output is correct |
7 |
Correct |
800 ms |
851460 KB |
Output is correct |
8 |
Correct |
756 ms |
851540 KB |
Output is correct |
9 |
Correct |
755 ms |
851508 KB |
Output is correct |
10 |
Correct |
799 ms |
851576 KB |
Output is correct |
11 |
Correct |
757 ms |
851576 KB |
Output is correct |
12 |
Correct |
745 ms |
851460 KB |
Output is correct |
13 |
Correct |
752 ms |
851436 KB |
Output is correct |
14 |
Correct |
749 ms |
851448 KB |
Output is correct |
15 |
Correct |
752 ms |
851448 KB |
Output is correct |
16 |
Correct |
753 ms |
851448 KB |
Output is correct |
17 |
Correct |
756 ms |
852216 KB |
Output is correct |
18 |
Correct |
751 ms |
852216 KB |
Output is correct |
19 |
Correct |
748 ms |
852216 KB |
Output is correct |
20 |
Correct |
749 ms |
852044 KB |
Output is correct |
21 |
Correct |
749 ms |
852312 KB |
Output is correct |
22 |
Correct |
749 ms |
852352 KB |
Output is correct |
23 |
Correct |
757 ms |
852344 KB |
Output is correct |
24 |
Correct |
752 ms |
851700 KB |
Output is correct |
25 |
Correct |
745 ms |
851448 KB |
Output is correct |
26 |
Correct |
747 ms |
851376 KB |
Output is correct |
27 |
Correct |
844 ms |
851708 KB |
Output is correct |
28 |
Correct |
750 ms |
851576 KB |
Output is correct |
29 |
Correct |
749 ms |
851448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
803 ms |
851672 KB |
Output is correct |
2 |
Correct |
757 ms |
851560 KB |
Output is correct |
3 |
Correct |
769 ms |
851548 KB |
Output is correct |
4 |
Correct |
748 ms |
851588 KB |
Output is correct |
5 |
Correct |
749 ms |
851412 KB |
Output is correct |
6 |
Correct |
749 ms |
851468 KB |
Output is correct |
7 |
Correct |
800 ms |
851460 KB |
Output is correct |
8 |
Correct |
756 ms |
851540 KB |
Output is correct |
9 |
Correct |
755 ms |
851508 KB |
Output is correct |
10 |
Correct |
799 ms |
851576 KB |
Output is correct |
11 |
Correct |
757 ms |
851576 KB |
Output is correct |
12 |
Correct |
745 ms |
851460 KB |
Output is correct |
13 |
Correct |
752 ms |
851436 KB |
Output is correct |
14 |
Correct |
749 ms |
851448 KB |
Output is correct |
15 |
Correct |
752 ms |
851448 KB |
Output is correct |
16 |
Correct |
753 ms |
851448 KB |
Output is correct |
17 |
Correct |
756 ms |
852216 KB |
Output is correct |
18 |
Correct |
751 ms |
852216 KB |
Output is correct |
19 |
Correct |
748 ms |
852216 KB |
Output is correct |
20 |
Correct |
749 ms |
852044 KB |
Output is correct |
21 |
Correct |
749 ms |
852312 KB |
Output is correct |
22 |
Correct |
749 ms |
852352 KB |
Output is correct |
23 |
Correct |
757 ms |
852344 KB |
Output is correct |
24 |
Correct |
752 ms |
851700 KB |
Output is correct |
25 |
Correct |
764 ms |
856236 KB |
Output is correct |
26 |
Correct |
767 ms |
856188 KB |
Output is correct |
27 |
Correct |
816 ms |
856216 KB |
Output is correct |
28 |
Correct |
771 ms |
855416 KB |
Output is correct |
29 |
Correct |
785 ms |
856952 KB |
Output is correct |
30 |
Correct |
786 ms |
856952 KB |
Output is correct |
31 |
Correct |
815 ms |
856668 KB |
Output is correct |
32 |
Correct |
777 ms |
856568 KB |
Output is correct |
33 |
Correct |
745 ms |
851448 KB |
Output is correct |
34 |
Correct |
747 ms |
851376 KB |
Output is correct |
35 |
Correct |
844 ms |
851708 KB |
Output is correct |
36 |
Correct |
750 ms |
851576 KB |
Output is correct |
37 |
Correct |
749 ms |
851448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
803 ms |
851672 KB |
Output is correct |
2 |
Correct |
757 ms |
851560 KB |
Output is correct |
3 |
Correct |
769 ms |
851548 KB |
Output is correct |
4 |
Correct |
748 ms |
851588 KB |
Output is correct |
5 |
Correct |
749 ms |
851412 KB |
Output is correct |
6 |
Correct |
749 ms |
851468 KB |
Output is correct |
7 |
Correct |
800 ms |
851460 KB |
Output is correct |
8 |
Correct |
756 ms |
851540 KB |
Output is correct |
9 |
Correct |
755 ms |
851508 KB |
Output is correct |
10 |
Correct |
799 ms |
851576 KB |
Output is correct |
11 |
Correct |
757 ms |
851576 KB |
Output is correct |
12 |
Correct |
745 ms |
851460 KB |
Output is correct |
13 |
Correct |
752 ms |
851436 KB |
Output is correct |
14 |
Correct |
749 ms |
851448 KB |
Output is correct |
15 |
Correct |
752 ms |
851448 KB |
Output is correct |
16 |
Correct |
753 ms |
851448 KB |
Output is correct |
17 |
Correct |
756 ms |
852216 KB |
Output is correct |
18 |
Correct |
751 ms |
852216 KB |
Output is correct |
19 |
Correct |
748 ms |
852216 KB |
Output is correct |
20 |
Correct |
749 ms |
852044 KB |
Output is correct |
21 |
Correct |
749 ms |
852312 KB |
Output is correct |
22 |
Correct |
749 ms |
852352 KB |
Output is correct |
23 |
Correct |
757 ms |
852344 KB |
Output is correct |
24 |
Correct |
752 ms |
851700 KB |
Output is correct |
25 |
Correct |
764 ms |
856236 KB |
Output is correct |
26 |
Correct |
767 ms |
856188 KB |
Output is correct |
27 |
Correct |
816 ms |
856216 KB |
Output is correct |
28 |
Correct |
771 ms |
855416 KB |
Output is correct |
29 |
Correct |
785 ms |
856952 KB |
Output is correct |
30 |
Correct |
786 ms |
856952 KB |
Output is correct |
31 |
Correct |
815 ms |
856668 KB |
Output is correct |
32 |
Correct |
777 ms |
856568 KB |
Output is correct |
33 |
Correct |
1033 ms |
895568 KB |
Output is correct |
34 |
Correct |
996 ms |
900380 KB |
Output is correct |
35 |
Correct |
996 ms |
900240 KB |
Output is correct |
36 |
Correct |
1045 ms |
907384 KB |
Output is correct |
37 |
Correct |
999 ms |
912504 KB |
Output is correct |
38 |
Correct |
997 ms |
912376 KB |
Output is correct |
39 |
Correct |
1000 ms |
912504 KB |
Output is correct |
40 |
Correct |
997 ms |
908828 KB |
Output is correct |
41 |
Correct |
1040 ms |
892920 KB |
Output is correct |
42 |
Correct |
1090 ms |
898532 KB |
Output is correct |
43 |
Correct |
1314 ms |
919536 KB |
Output is correct |
44 |
Correct |
1366 ms |
920024 KB |
Output is correct |
45 |
Correct |
1038 ms |
885752 KB |
Output is correct |
46 |
Correct |
1034 ms |
885496 KB |
Output is correct |
47 |
Correct |
1295 ms |
916600 KB |
Output is correct |
48 |
Correct |
1313 ms |
916704 KB |
Output is correct |
49 |
Correct |
745 ms |
851448 KB |
Output is correct |
50 |
Correct |
747 ms |
851376 KB |
Output is correct |
51 |
Correct |
844 ms |
851708 KB |
Output is correct |
52 |
Correct |
750 ms |
851576 KB |
Output is correct |
53 |
Correct |
749 ms |
851448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
784 ms |
852476 KB |
Output is correct |
2 |
Correct |
798 ms |
852288 KB |
Output is correct |
3 |
Correct |
793 ms |
852068 KB |
Output is correct |
4 |
Correct |
757 ms |
851352 KB |
Output is correct |
5 |
Correct |
779 ms |
852328 KB |
Output is correct |
6 |
Correct |
854 ms |
852336 KB |
Output is correct |
7 |
Correct |
786 ms |
852288 KB |
Output is correct |
8 |
Correct |
782 ms |
852412 KB |
Output is correct |
9 |
Correct |
850 ms |
852488 KB |
Output is correct |
10 |
Correct |
792 ms |
851704 KB |
Output is correct |
11 |
Correct |
783 ms |
852092 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
760 ms |
851320 KB |
Output is correct |
2 |
Runtime error |
1066 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
803 ms |
851672 KB |
Output is correct |
2 |
Correct |
757 ms |
851560 KB |
Output is correct |
3 |
Correct |
769 ms |
851548 KB |
Output is correct |
4 |
Correct |
748 ms |
851588 KB |
Output is correct |
5 |
Correct |
749 ms |
851412 KB |
Output is correct |
6 |
Correct |
749 ms |
851468 KB |
Output is correct |
7 |
Correct |
800 ms |
851460 KB |
Output is correct |
8 |
Correct |
756 ms |
851540 KB |
Output is correct |
9 |
Correct |
755 ms |
851508 KB |
Output is correct |
10 |
Correct |
799 ms |
851576 KB |
Output is correct |
11 |
Correct |
757 ms |
851576 KB |
Output is correct |
12 |
Correct |
745 ms |
851460 KB |
Output is correct |
13 |
Correct |
752 ms |
851436 KB |
Output is correct |
14 |
Correct |
749 ms |
851448 KB |
Output is correct |
15 |
Correct |
752 ms |
851448 KB |
Output is correct |
16 |
Correct |
753 ms |
851448 KB |
Output is correct |
17 |
Correct |
756 ms |
852216 KB |
Output is correct |
18 |
Correct |
751 ms |
852216 KB |
Output is correct |
19 |
Correct |
748 ms |
852216 KB |
Output is correct |
20 |
Correct |
749 ms |
852044 KB |
Output is correct |
21 |
Correct |
749 ms |
852312 KB |
Output is correct |
22 |
Correct |
749 ms |
852352 KB |
Output is correct |
23 |
Correct |
757 ms |
852344 KB |
Output is correct |
24 |
Correct |
752 ms |
851700 KB |
Output is correct |
25 |
Correct |
764 ms |
856236 KB |
Output is correct |
26 |
Correct |
767 ms |
856188 KB |
Output is correct |
27 |
Correct |
816 ms |
856216 KB |
Output is correct |
28 |
Correct |
771 ms |
855416 KB |
Output is correct |
29 |
Correct |
785 ms |
856952 KB |
Output is correct |
30 |
Correct |
786 ms |
856952 KB |
Output is correct |
31 |
Correct |
815 ms |
856668 KB |
Output is correct |
32 |
Correct |
777 ms |
856568 KB |
Output is correct |
33 |
Correct |
1033 ms |
895568 KB |
Output is correct |
34 |
Correct |
996 ms |
900380 KB |
Output is correct |
35 |
Correct |
996 ms |
900240 KB |
Output is correct |
36 |
Correct |
1045 ms |
907384 KB |
Output is correct |
37 |
Correct |
999 ms |
912504 KB |
Output is correct |
38 |
Correct |
997 ms |
912376 KB |
Output is correct |
39 |
Correct |
1000 ms |
912504 KB |
Output is correct |
40 |
Correct |
997 ms |
908828 KB |
Output is correct |
41 |
Correct |
1040 ms |
892920 KB |
Output is correct |
42 |
Correct |
1090 ms |
898532 KB |
Output is correct |
43 |
Correct |
1314 ms |
919536 KB |
Output is correct |
44 |
Correct |
1366 ms |
920024 KB |
Output is correct |
45 |
Correct |
1038 ms |
885752 KB |
Output is correct |
46 |
Correct |
1034 ms |
885496 KB |
Output is correct |
47 |
Correct |
1295 ms |
916600 KB |
Output is correct |
48 |
Correct |
1313 ms |
916704 KB |
Output is correct |
49 |
Correct |
784 ms |
852476 KB |
Output is correct |
50 |
Correct |
798 ms |
852288 KB |
Output is correct |
51 |
Correct |
793 ms |
852068 KB |
Output is correct |
52 |
Correct |
757 ms |
851352 KB |
Output is correct |
53 |
Correct |
779 ms |
852328 KB |
Output is correct |
54 |
Correct |
854 ms |
852336 KB |
Output is correct |
55 |
Correct |
786 ms |
852288 KB |
Output is correct |
56 |
Correct |
782 ms |
852412 KB |
Output is correct |
57 |
Correct |
850 ms |
852488 KB |
Output is correct |
58 |
Correct |
792 ms |
851704 KB |
Output is correct |
59 |
Correct |
783 ms |
852092 KB |
Output is correct |
60 |
Correct |
760 ms |
851320 KB |
Output is correct |
61 |
Runtime error |
1066 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
62 |
Halted |
0 ms |
0 KB |
- |