| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 169812 | arthur_nascimento | 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;
#define pb push_back
#define debug
#define ll long long
#define maxn 2525
int lg[maxn];
struct rmq {
int len;
int arr[maxn];
int mx[13][maxn];
int id[13][maxn];
void build(){
lg[1] = 0;
for(int i=2;i<=len;i++)
lg[i] = lg[i-1] + (i == (i&-i));
for(int i=0;i<len;i++){
mx[0][i] = arr[i];
id[0][i] = i;
}
for(int i=1;i<13;i++)
for(int j=0;j<len;j++){
int ot = min(len-1, j + ( 1 << (i-1)));
int A = mx[i-1][j], B = mx[i-1][ot];
if(A > B){
mx[i][j] = A;
id[i][j] = id[i-1][j];
}
else {
mx[i][j] = B;
id[i][j] = id[i-1][ot];
}
}
}
int pos(int x,int y){
int l = lg[y-x+1];
int A = mx[l][x], B = mx[l][y-(1<<l)+1];
if(A > B) return id[l][x];
else return id[l][y-(1<<l)+1];
}
int val(int x,int y){
int l = lg[y-x+1];
int A = mx[l][x], B = mx[l][y-(1<<l)+1];
return max(A,B);
}
}
RMQ[2][maxn];
int M[maxn][maxn];
int n,m;
int line(int i,int yi,int yf){
int r = 1;
for(int j=yi;j<=yf;j++)
if(M[i][j] >= M[i][yi-1] || M[i][j] >= M[i][yf+1]) r = 0;
return r;
}
int column(int j,int xi,int xf){
int r = 1;
for(int i=xi;i<=xf;i++)
if(M[i][j] >= M[xi-1][j] || M[i][j] >= M[xf+1][j]) r = 0;
return r;
}
int check(int xi,int xf,int yi,int yf){
for(int i=xi;i<=xf;i++)
if( RMQ[0][i].val(yi,yf) >= min( M[i][yi-1],M[i][yf+1])) return 0;
for(int j=yi;j<=yf;j++)
if( RMQ[1][j].val(xi,xj) >= min( M[xi-1][j],M[xf+1][j])) return 0;
return 1;
//return 1;
int r = 1;
assert(xi >= 1 && xf <= n-2 && yi >= 1 && yf <= m-2);
//for(int i=xi;i<=xf;i++)
// r *= line(i,yi,yf);
for(int j=yi;j<=yf;j++)
r *= column(j,xi,xf);
if(r)
debug("achou x:%d~%d y: %d~%d\n",xi,xf,yi,yf);
return r;
}
ll go4(int xi,int xf,int yi,int yf,int ym){
if(xi > xf || yi > yf) return 0;
if(yi > ym || yf < ym) return 0;
debug("oi4\n");
ll ans = check(xi,xf,yi,yf);
int mx = -1, id = -1;
/*for(int i=yi;i<=yf;i++)
if(M[xi][i] > mx){
mx = M[xi][i];
id = i;
}*/
id = RMQ[0][xi].pos(yi,yf);
ans += go4(xi,xf,yi,id-1,ym) + go4(xi,xf,id+1,yf,ym);
debug("tchau 4\n");
return ans;
}
ll go3(int xi,int xf,int yi,int yf,int ym){
if(xi == 0 || xf == n-1) return 0;
if(xi > xf) return 0;
int A = ym, B = ym;
debug("oi x: %d~%d y: %d~%d quebra A ? B ?\n",xi,xf,yi,yf);
while(1){
A--;
if(A == 0 || A < yi) break;
debug("A %d\n",A);
int ok = 1;
//for(int i=xi;i<=xf;i++)
// if(M[i][A] >= M[xi-1][A] || M[i][A] >= M[xf+1][A]) ok = 0;
if(RMQ[1][A].val(xi,xf) >= min(M[xi-1][A],M[xf+1][A])) ok = 0;
if(ok == 0) break;
}
A++;
while(1){
B++;
if(B == m-1 || B > yf) break;
int ok = 1;
for(int i=xi;i<=xf;i++)
if(M[i][B] >= M[xi-1][B] || M[i][B] >= M[xf+1][B]) ok = 0;
if(ok == 0) break;
}
B--;
debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B);
return go4(xi,xf,A,B,ym);
}
ll go2(int xi,int xf,int yi,int yf,int ym){
if(xi > xf) return 0;
if(yi > yf) return 0;
if(ym == 0 || ym == m-1) return 0;
debug("go2 x %d~%d y %d~%d\n",xi,xf,yi,yf);
int mx = -1, id = -1;
/*for(int i=xi;i<=xf;i++)
if(M[i][ym] > mx){
mx = M[i][ym];
id = i;
}*/
id = RMQ[1][ym].pos(xi,xf);
ll ans = go3(xi,id-1,yi,yf,ym) + go3(id+1,xf,yi,yf,ym) + go2(xi,id-1,yi,yf,ym) + go2(id+1,xf,yi,yf,ym);
return ans;
}
ll go(int yi,int yf){
if(yi > yf) return 0;
int ym = (yi+yf)/2;
debug("oi\n");
ll ans = go(yi,ym-1) + go(ym+1,yf) + go2(0,n-1,yi,yf,ym);
return ans;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n = a.size();
m = a[0].size();
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
M[i][j] = a[i][j];
for(int i=0;i<n;i++){
RMQ[0][i].len = m;
for(int j=0;j<m;j++)
RMQ[0][i].arr[j] = M[i][j];
RMQ[0][i].build();
}
for(int j=0;j<m;j++){
RMQ[1][j].len = n;
for(int i=0;i<n;i++)
RMQ[1][j].arr[i] = M[i][j];
RMQ[1][j].build();
}
return go(0,m-1);
}