#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
struct segment{
vector<int> tr;
int sz;
segment(vector<int> &v){
sz = 1;
while(sz <= v.size()) sz *= 2;
tr.resize(2*sz);
for(int i=0; i<v.size(); i++) tr[i+sz] = v[i];
for(int i=sz; --i;) tr[i] = max(tr[2*i], tr[2*i+1]);
}
segment() {}
int query(int l, int r){
int ans = 0;
for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){
if(l & 1) ans = max(ans, tr[l++]);
if(r & 1) ans = max(ans, tr[--r]);
}
return ans;
}
};
struct segment2d{
vector<segment> tr;
int sz;
segment2d(vector<vector<int>> &v){
sz = 1;
while(sz <= v.size()) sz *= 2;
tr.resize(2*sz);
int sz2 = 1;
while(sz2 <= v[0].size()) sz2 *= 2;
vector<int> ilvuoto(sz2);
for(int i=0; i<v.size(); i++) tr[i+sz] = segment(v[i]);
for(int i=v.size(); i<sz; i++) tr[i+sz] = segment(ilvuoto);
for(int i=sz; --i;){
vector<int> treesus(sz2);
for(int j=0; j<sz2; j++) treesus[j] = max(tr[2*i].tr[j+sz2], tr[2*i+1].tr[j+sz2]);
tr[i] = segment(treesus);
}
}
int query(int l, int r, int ql, int qr){
int ans = 0;
for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){
if(l & 1) ans = max(ans, tr[l++].query(ql, qr));
if(r & 1) ans = max(ans, tr[--r].query(ql, qr));
}
return ans;
}
};
struct segment2{
vector<int> tr;
int sz;
segment2(vector<int> &v){
sz = 1;
while(sz <= v.size()) sz *= 2;
tr.resize(2*sz);
for(int i=0; i<v.size(); i++) tr[i+sz] = v[i];
for(int i=v.size(); i<sz; i++) tr[i+sz] = v.size();
for(int i=sz; --i;) tr[i] = min(tr[2*i], tr[2*i+1]);
}
segment2() {}
int query(int l, int r){
int ans = 1e9;
for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){
if(l & 1) ans = min(ans, tr[l++]);
if(r & 1) ans = min(ans, tr[--r]);
}
return ans;
}
};
struct segment22d{
vector<segment2> tr;
int sz;
segment22d(vector<vector<int>> &v){
sz = 1;
while(sz <= v.size()) sz *= 2;
tr.resize(2*sz);
int sz2 = 1;
while(sz2 <= v[0].size()) sz2 *= 2;
vector<int> ilgrosso(sz2, v[0].size());
for(int i=0; i<v.size(); i++) tr[i+sz] = segment2(v[i]);
for(int i=v.size(); i<sz; i++) tr[i+sz] = segment2(ilgrosso);
for(int i=sz; --i;){
vector<int> treesus(sz2);
for(int j=0; j<sz2; j++) treesus[j] = min(tr[2*i].tr[j+sz2], tr[2*i+1].tr[j+sz2]);
tr[i] = segment2(treesus);
}
}
int query(int l, int r, int ql, int qr){
int ans = 1e9;
for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){
if(l & 1) ans = min(ans, tr[l++].query(ql, qr));
if(r & 1) ans = min(ans, tr[--r].query(ql, qr));
}
return ans;
}
};
long long count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m = a[0].size();
vector<vector<int>> up(n, vector<int>(m, -1)), down(n, vector<int>(m, n)), left(n, vector<int>(m, -1)), right(n, vector<int>(m, m));
//right
for(int i=0; i<n; i++){
stack<int> s;
for(int j=0; j<m; j++){
while(s.size() and a[i][s.top()] < a[i][j]){
right[i][s.top()] = j;
s.pop();
}
s.push(j);
}
}
//left
for(int i=0; i<n; i++){
stack<int> s;
for(int j=m-1; j>=0; j--){
while(s.size() and a[i][s.top()] < a[i][j]){
left[i][s.top()] = j;
s.pop();
}
s.push(j);
}
}
//up
for(int j=0; j<m; j++){
stack<int> s;
for(int i=n-1; i>=0; i--){
while(s.size() and a[s.top()][j] < a[i][j]){
up[s.top()][j] = i;
s.pop();
}
s.push(i);
}
}
//down
for(int j=0; j<m; j++){
stack<int> s;
for(int i=0; i<n; i++){
while(s.size() and a[s.top()][j] < a[i][j]){
down[s.top()][j] = i;
s.pop();
}
s.push(i);
}
}
int ans = 0;
segment2d stright(right), stdown(down);
segment22d stleft(left), stup(up);
for(int i=1; i<n-1; i++){
for(int j=1; j<m-1; j++){
int l = left[i][j], r = right[i][j], u = up[i][j], d = down[i][j];
if(l == -1 or r == m or u == -1 or d == n) continue;
if(
l == stleft.query(u+1, d, l+1, r) and
r == stright.query(u+1, d, l+1, r) and
u == stup.query(u+1, d, l+1, r) and
d == stdown.query(u+1, d, l+1, r)
) ans++;
// cerr << i << " " << j << endl;
// cerr << l << " " << r << " " << u << " " << d << endl;
// cerr << stleft.query(u+1, d, l+1, r) << " " << stright.query(u+1, d, l+1, r) << " " << stup.query(u+1, d, l+1, r) << " " << stdown.query(u+1, d, l+1, r) << endl;
}
}
// for(int i=0; i<n; i++){
// for(int j=0; j<m; j++){
// cout << up[i][j] << " ";
// }
// cout << endl;
// }
return ans;
}
Compilation message
rect.cpp: In constructor 'segment::segment(std::vector<int>&)':
rect.cpp:11:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | while(sz <= v.size()) sz *= 2;
| ~~~^~~~~~~~~~~
rect.cpp:14:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for(int i=0; i<v.size(); i++) tr[i+sz] = v[i];
| ~^~~~~~~~~
rect.cpp: In constructor 'segment2d::segment2d(std::vector<std::vector<int> >&)':
rect.cpp:35:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | while(sz <= v.size()) sz *= 2;
| ~~~^~~~~~~~~~~
rect.cpp:39:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | while(sz2 <= v[0].size()) sz2 *= 2;
| ~~~~^~~~~~~~~~~~~~
rect.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=0; i<v.size(); i++) tr[i+sz] = segment(v[i]);
| ~^~~~~~~~~
rect.cpp: In constructor 'segment2::segment2(std::vector<int>&)':
rect.cpp:68:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | while(sz <= v.size()) sz *= 2;
| ~~~^~~~~~~~~~~
rect.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i=0; i<v.size(); i++) tr[i+sz] = v[i];
| ~^~~~~~~~~
rect.cpp: In constructor 'segment22d::segment22d(std::vector<std::vector<int> >&)':
rect.cpp:93:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | while(sz <= v.size()) sz *= 2;
| ~~~^~~~~~~~~~~
rect.cpp:97:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | while(sz2 <= v[0].size()) sz2 *= 2;
| ~~~~^~~~~~~~~~~~~~
rect.cpp:101:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i=0; i<v.size(); i++) tr[i+sz] = segment2(v[i]);
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1884 KB |
Output is correct |
2 |
Correct |
2 ms |
1884 KB |
Output is correct |
3 |
Correct |
1 ms |
1884 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
2 ms |
1884 KB |
Output is correct |
6 |
Correct |
2 ms |
1884 KB |
Output is correct |
7 |
Correct |
3 ms |
1884 KB |
Output is correct |
8 |
Correct |
2 ms |
1880 KB |
Output is correct |
9 |
Correct |
2 ms |
1904 KB |
Output is correct |
10 |
Correct |
1 ms |
1116 KB |
Output is correct |
11 |
Correct |
2 ms |
1884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
743 ms |
960780 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |