#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=705;
const int INF=1e9+9;
vector<vector<int> > v;
int borda[4][MAXN][MAXN]; // xl, xr, yl, yr
int seg[4][MAXN*4][MAXN*4];
int n, m, respf;
struct cara {
int i, j;
bool operator<(cara _) const {
return v[i][j]<v[_.i][_.j];
}
};
vector<cara> lista;
void histogrami() {
stack<pair<int, int> > st;
for(int i=0; i<n; i++) {
while(st.size()) st.pop(); st.push({INF, -1});
for(int j=0; j<m; j++) {
while(st.top().first<=v[i][j]) st.pop();
borda[0][i+1][j+1]=st.top().second+1;
st.push({v[i][j], j});
}
while(st.size()) st.pop(); st.push({INF, m});
for(int j=m-1; j>=0; j--) {
while(st.top().first<=v[i][j]) st.pop();
borda[1][i+1][j+1]=st.top().second-1;
st.push({v[i][j], j});
}
}
}
void histogramj() {
stack<pair<int, int> > st;
for(int j=0; j<m; j++) {
while(st.size()) st.pop(); st.push({INF, -1});
for(int i=0; i<n; i++) {
while(st.top().first<=v[i][j]) st.pop();
borda[2][i+1][j+1]=st.top().second+1;
st.push({v[i][j], i});
}
while(st.size()) st.pop(); st.push({INF, n});
for(int i=n-1; i>=0; i--) {
while(st.top().first<=v[i][j]) st.pop();
borda[3][i+1][j+1]=st.top().second-1;
st.push({v[i][j], i});
}
}
}
void remergej(int ssind, int sind) {
for(int i=0; i<4; i++) {
if(i&1) seg[i][ssind][sind]=max(seg[i][ssind][sind*2], seg[i][ssind][sind*2+1]);
else seg[i][ssind][sind]=min(seg[i][ssind][sind*2], seg[i][ssind][sind*2+1]);
}
}
void remergei(int ssind, int sind, int ini, int fim, int xind) {
for(int i=0; i<4; i++) {
if(i&1) seg[i][ssind][sind]=max(seg[i][ssind*2][sind], seg[i][ssind*2+1][sind]);
else seg[i][ssind][sind]=min(seg[i][ssind*2][sind], seg[i][ssind*2+1][sind]);
}
if(ini==fim) return;
int mid=(ini+fim)/2;
if(xind<=mid) remergei(ssind, sind*2, ini, mid, xind);
else remergei(ssind, sind*2+1, mid+1, fim, xind);
}
void updj(int ssind, int yind, int sind, int ini, int fim, int xind) {
if(ini==fim) {
for(int i=0; i<4; i++) seg[i][ssind][sind]=borda[i][yind][xind];
return;
}
int mid=(ini+fim)/2;
if(xind<=mid) updj(ssind, yind, sind*2, ini, mid, xind);
else updj(ssind, yind, sind*2+1, mid+1, fim, xind);
remergej(ssind, sind);
}
void updi(int sind, int ini, int fim, int yind, int xind) {
if(ini==fim) {
updj(sind, yind, 1, 1, m, xind);
return;
}
int mid=(ini+fim)/2;
if(yind<=mid) updi(sind*2, ini, mid, yind, xind);
else updi(sind*2+1, mid+1, fim, yind, xind);
remergei(sind, 1, 1, m, xind);
}
int quj(int ssind, int sind, int ini, int fim, int xl, int xr, int k) {
if(xl<=ini&&xr>=fim) return seg[k][ssind][sind];
int mid=(ini+fim)/2;
int resp= k&1 ? -1 : INF;
if(xl<=mid) {
if(k&1) resp=max(resp, quj(ssind, sind*2, ini, mid, xl, xr, k));
else resp=min(resp, quj(ssind, sind*2, ini, mid, xl, xr, k));
}
if(xr>mid) {
if(k&1) resp=max(resp, quj(ssind, sind*2+1, mid+1, fim, xl, xr, k));
else resp=min(resp, quj(ssind, sind*2+1, mid+1, fim, xl, xr, k));
}
return resp;
}
int qui(int sind, int ini, int fim, int xl, int xr, int yl, int yr, int k) {
if(yl<=ini&&yr>=fim) return quj(sind, 1, 1, m, xl, xr, k);
int mid=(ini+fim)/2;
int resp= k&1 ? -1 : INF;
if(yl<=mid) {
if(k&1) resp=max(resp, qui(sind*2, ini, mid, xl, xr, yl, yr, k));
else resp=min(resp, qui(sind*2, ini, mid, xl, xr, yl, yr, k));
}
if(yr>mid) {
if(k&1) resp=max(resp, qui(sind*2+1, mid+1, fim, xl, xr, yl, yr, k));
else resp=min(resp, qui(sind*2+1, mid+1, fim, xl, xr, yl, yr, k));
}
return resp;
}
ll count_rectangles(vector< vector<int> > A) {
v=A; n=A.size(); m=A[0].size();
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
cara cur;
cur.i=i; cur.j=j;
lista.push_back(cur);
}
}
histogrami();
histogramj();
for(int k=0; k<4; k++) for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) borda[k][i][j]++;
//1-indexed now
// for(auto cur : lista) printf("(%d, %d): %d %d // %d %d\n", cur.i, cur.j, cur.xl, cur.xr, cur.yl, cur.yr);
for(int i=0; i<4*MAXN; i++) {
for(int j=0; j<4*MAXN; j++) {
seg[0][i][j]=seg[2][i][j]=INF;
seg[1][i][j]=seg[3][i][j]=-1;
}
}
sort(lista.begin(), lista.end());
for(auto cur : lista) {
int i=cur.i+1; int j=cur.j+1;
updi(1, 1, n, i, j);
if(borda[0][i][j]<=1||borda[1][i][j]>=m||borda[2][i][j]<=1||borda[3][i][j]>=n) continue;
bool ok=1;
for(int k=0; k<4&&ok; k++) {
int val=qui(1, 1, n, borda[0][i][j], borda[1][i][j], borda[2][i][j], borda[3][i][j], k);
// printf("%d %d >> %d ? >> %d\n", i, j, k, val);
if((k&1)&&val>borda[k][i][j]) ok=0;
if((~k&1)&&val<borda[k][i][j]) ok=0;
}
if(ok) respf++;
}
return respf;
}
Compilation message
rect.cpp: In function 'void histogrami()':
rect.cpp:24:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
while(st.size()) st.pop(); st.push({INF, -1});
^~~~~
rect.cpp:24:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
while(st.size()) st.pop(); st.push({INF, -1});
^~
rect.cpp:30:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
while(st.size()) st.pop(); st.push({INF, m});
^~~~~
rect.cpp:30:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
while(st.size()) st.pop(); st.push({INF, m});
^~
rect.cpp: In function 'void histogramj()':
rect.cpp:41:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
while(st.size()) st.pop(); st.push({INF, -1});
^~~~~
rect.cpp:41:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
while(st.size()) st.pop(); st.push({INF, -1});
^~
rect.cpp:47:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
while(st.size()) st.pop(); st.push({INF, n});
^~~~~
rect.cpp:47:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
while(st.size()) st.pop(); st.push({INF, n});
^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
119 ms |
124920 KB |
Output is correct |
| 2 |
Correct |
119 ms |
125148 KB |
Output is correct |
| 3 |
Correct |
119 ms |
125176 KB |
Output is correct |
| 4 |
Correct |
119 ms |
125176 KB |
Output is correct |
| 5 |
Correct |
136 ms |
125176 KB |
Output is correct |
| 6 |
Incorrect |
119 ms |
125176 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
119 ms |
124920 KB |
Output is correct |
| 2 |
Correct |
119 ms |
125148 KB |
Output is correct |
| 3 |
Correct |
119 ms |
125176 KB |
Output is correct |
| 4 |
Correct |
119 ms |
125176 KB |
Output is correct |
| 5 |
Correct |
136 ms |
125176 KB |
Output is correct |
| 6 |
Incorrect |
119 ms |
125176 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
119 ms |
124920 KB |
Output is correct |
| 2 |
Correct |
119 ms |
125148 KB |
Output is correct |
| 3 |
Correct |
119 ms |
125176 KB |
Output is correct |
| 4 |
Correct |
119 ms |
125176 KB |
Output is correct |
| 5 |
Correct |
136 ms |
125176 KB |
Output is correct |
| 6 |
Incorrect |
119 ms |
125176 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
119 ms |
124920 KB |
Output is correct |
| 2 |
Correct |
119 ms |
125148 KB |
Output is correct |
| 3 |
Correct |
119 ms |
125176 KB |
Output is correct |
| 4 |
Correct |
119 ms |
125176 KB |
Output is correct |
| 5 |
Correct |
136 ms |
125176 KB |
Output is correct |
| 6 |
Incorrect |
119 ms |
125176 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
124 ms |
125324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
117 ms |
124932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
119 ms |
124920 KB |
Output is correct |
| 2 |
Correct |
119 ms |
125148 KB |
Output is correct |
| 3 |
Correct |
119 ms |
125176 KB |
Output is correct |
| 4 |
Correct |
119 ms |
125176 KB |
Output is correct |
| 5 |
Correct |
136 ms |
125176 KB |
Output is correct |
| 6 |
Incorrect |
119 ms |
125176 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
