| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 154201 | wilwxk | Rectangles (IOI19_rect) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
}
void quj(int ssind, int sind, int ini, int fim, int xl, int xr) {
if(xl<=ini&&xr>=fim) {
for(int k=0; k<4; k++) {
if(k&1) seg[k][0][0]=max(seg[k][0][0], seg[k][ssind][sind]);
else seg[k][0][0]=min(seg[k][0][0], seg[k][ssind][sind]);
}
return;
}
int mid=(ini+fim)/2;
if(xl<=mid) quj(ssind, sind*2, ini, mid, xl, xr);
if(xr>mid) quj(ssind, sind*2+1, mid+1, fim, xl, xr);
}
int qui(int sind, int ini, int fim, int xl, int xr, int yl, int yr) {
if(yl<=ini&&yr>=fim) {
quj(sind, 1, 1, m, xl, xr, k);
return;
}
int mid=(ini+fim)/2;
if(yl<=mid) qui(sind*2, ini, mid, xl, xr, yl, yr);
if(yr>mid) qui(sind*2+1, mid+1, fim, xl, xr, yl, yr);
}
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*n; i++) {
for(int j=0; j<4*m; j++) {
seg[0][i][j]=seg[2][i][j]=-1;
seg[1][i][j]=seg[3][i][j]=MAXN;
}
}
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;
}