| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 156310 |
2019-10-05T02:25:53 Z |
wilwxk |
Rectangles (IOI19_rect) |
C++14 |
|
0 ms |
0 KB |
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2503;
int v[MAXN][MAXN];
short limite[MAXN][MAXN][4];
short qv[MAXN][MAXN][4];
short seg[4][MAXN][4*MAXN];
set<tuple<int, int, int, int> > respf;
int n, m;
void histoi() {
for(int i=0; i<n; i++) {
stack<pair<int, int> > st;
for(int j=0; j<m; j++) {
while(st.size()&&st.top().first<v[i][j]) {
qv[i][st.top().second][0]=j;
st.pop();
}
limite[i][j][2]= st.size() ? st.top().second : -1;
st.push({v[i][j], j});
}
while(st.size()) st.pop();
for(int j=m-1; j>=0; j--) {
while(st.size()&&st.top().first<v[i][j]) {
qv[i][st.top().second][2]=j;
st.pop();
}
limite[i][j][0]= st.size() ? st.top().second : m;
st.push({v[i][j], j});
}
}
}
void histoj() {
for(int j=0; j<m; j++) {
stack<pair<int, int> > st;
for(int i=0; i<n; i++) {
while(st.size()&&st.top().first<v[i][j]) {
qv[st.top().second][j][3]=i;
st.pop();
}
limite[i][j][1]= st.size() ? st.top().second : -1;
st.push({v[i][j], i});
}
while(st.size()) st.pop();
for(int i=n-1; i>=0; i--) {
while(st.size()&&st.top().first<v[i][j]) {
qv[st.top().second][j][1]=i;
st.pop();
}
limite[i][j][3]= st.size() ? st.top().second : n;
st.push({v[i][j], i});
}
}
}
void junta(int sind, int e, int d, int k, int k2) {
if(k==0||k==3) seg[k][k2][sind]=min(seg[k][k2][e], seg[k][k2][d]);
else seg[k][k2][sind]=max(seg[k][k2][e], seg[k][k2][d]);
}
void build(int sind, int ini, int fim, int k, int k2) {
if(ini==fim) {
if(k==0||k==2) seg[k][k2][sind]=limite[ini][k2][k];
else seg[k][k2][sind]=limite[k2][ini][k];
return;
}
int mid=(ini+fim)/2;
int e=sind*2; int d=e+1;
build(e, ini, mid, k, k2); build(d, mid+1, fim, k, k2);
junta(sind, e, d, k, k2);
}
void query(int sind, int ini, int fim, int qini, int qfim, int k, int k2) {
if(sind==1) {
if(k==0||k==3) seg[k][k2][0]=MAXN;
else seg[k][k2][0]=-1;
}
if(qini<=ini&&qfim>=fim) {
junta(0, 0, sind, k, k2);
return;
}
int mid=(ini+fim)/2;
int e=sind*2; int d=e+1;
if(qini<=mid) query(e, ini, mid, qini, qfim, k, k2);
if(qfim>mid) query(d, mid+1, fim, qini, qfim, k, k2);
}
bool checa(int a, int b, int c, int d) {
int i, j, i2, j2;
i=min(a, c); i2=max(a, c);
j=min(b, d); j2=max(b, d);
if(i<0||j<0||i2>n-1||j2>m-1) return 0;
// printf("checa %d %d %d %d\n", i, j, i2, j2);
query(1, 0, m-1, j+1, j2-1, 3, i);
int aa=seg[3][i][0];
if(aa<i2) return 0;
query(1, 0, m-1, j+1, j2-1, 1, i2);
int bb=seg[1][i2][0];
if(bb>i) return 0;
query(1, 0, n-1, i+1, i2-1, 0, j);
int cc=seg[0][j][0];
if(cc<j2) return 0;
query(1, 0, n-1, i+1, i2-1, 2, j2);
int dd=seg[2][j2][0];
if(dd>j) return 0;
// printf("ok %d %d %d %d\n", aa, bb, cc, dd);
return 1;
}
ll count_rectangles(vector< vector<int> > A) {
n=A.size(); m=A[0].size();
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
v[i][j]=A[i][j];
qv[i][j][0]=m;
qv[i][j][1]=-1;
qv[i][j][2]=-1;
qv[i][j][3]=n;
}
}
histoi(); histoj();
// for(int i=0; i<n; i++) {
// for(int j=0; j<m; j++) printf("%d ", qv[i][j][0]);
// printf("\n");
// }
for(int i=0; i<n; i++) build(1, 0, m-1, 1, i), build(1, 0, m-1, 3, i);
for(int j=0; j<m; j++) build(1, 0, n-1, 0, j), build(1, 0, n-1, 2, j);
for(int ii=1; ii<n-1; ii++) {
for(int jj=1; jj<m-1; jj++) {
// printf("%d %d\n", ii, jj);
int i=qv[ii][jj][1];
int j=qv[ii][jj][2];
int i2=qv[ii][jj][3];
int j2=qv[ii][jj][0];
if(respf.find({i, j, i2, j2})!=resp.end()) continue;
if(checa(i, j, i2, j2)) respf.insert({i, j, i2, j2});
}
}
return respf.size();
}
Compilation message
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:147:35: error: 'resp' was not declared in this scope
if(respf.find({i, j, i2, j2})!=resp.end()) continue;
^~~~
rect.cpp:147:35: note: suggested alternative: 'respf'
if(respf.find({i, j, i2, j2})!=resp.end()) continue;
^~~~
respf
