| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 379111 | Thistle | 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;
using ll=long long;
using H=pair<ll, ll>;
using vi=vector<ll>;
#define vec vector
#define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),(0),(n))
#define fs first
#define sc second
#define all(a) (a).begin(),(a).end()
#define siz(a) ll((a).size())
class sptable{
int n;
vi lgt;
vec<vi> dat;
public:
sptable(vec<int> v){
n=siz(v);
lgt.assign(n+1,0);
for(int i=2;i<=n;i++) lgt[i]=lgt[i>>1]+1;
dat.assign(lgt[n]+1,vi(n));
rep(i,n) dat[0][i]=v[i];
rng(i,0,lgt[n]){
for(int j=0;j+(1<<(i+1))<=n;j++){
dat[i+1][j]=max(dat[i][j],dat[i][j+(1<<i)]);
}
}
}
sptable(){}
ll get(int l,int r){
int k=lgt[r-l];
return max(dat[k][l],dat[k][r-(1<<k)]);
}
};
long long count_rectangles(std::vector<std::vector<int> > a) {
int h=siz(a),w=siz(a[0]);
vec<sptable>sph(h),spw(w);
rep(i,h) sph[i]=sptable(a[i]);
rep(j,w){
vec<int>v(h);
rep(i,h) v[i]=a[i][j];
spw[j]=sptable(v);
}
ll ans=0;
rep(i,h-2)rep(j,w-2){
vec<bool>could(w,1);
int ed=w;
rng(k,i+2,h){
for(int t=j+2;t<ed;t++){
if(!could[t]) continue;
if(sph[k-1].get(j+1,t)>=a[k-1][t]){
could[t]=0;
continue;
}
if(spw[t-1].get(i+1,k)>=a[k][t-1]||spw.get(i+1,k)>=a[i][t-1])
continue;
ans++;
}
}
}
return ans;
}