| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 379111 | Thistle | Rectangles (IOI19_rect) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}