# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1021167 | nisanduu | Rectangles (IOI19_rect) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check(ll i,ll j,ll n,ll m,ll u,ll d,ll l,ll r,vector<vector<int>>&a){
if(i<=0||j<=0||i>=(n-1)||j>=(m-1)) return false;
if(a[i][j]<l&&a[i][j]<r&&a[i][j]<u&&a[i][j]<d) return true;
return false;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
ll n = a.size();
ll m = a[0].size();
ll cnt = 0;
map<ll,ll> hash;
queue<vector<ll>> pq;
// Row Col U D L R
for(ll i=1;i<n-1;i++){
for(ll j=1;j<m-1;j++){
if(a[i][j]<a[i+1][j]&&a[i][j]<a[i-1][j]&&a[i][j]<a[i][j+1]&&a[i][j]<a[i][j-1]){
vector<ll> vec = {i,j,a[i-1][j],a[i+1][j],a[i][j-1],a[i][j+1]};
pq.push(vec);
hash[i][j]=1;
}
}
}
vector<ll> dr = {-1,0,1,0};
vector<ll> dc = {0,-1,0,1};
ll ans = 0;
while(!pq.empty()){
vector<ll> v = pq.front();
pq.pop();
ans++;
for(ll i=0;i<4;i++){
ll nr = v[0]+dr[i];
ll nc = v[1]+dc[i];
if(check(nr,nc,n,m,v[2],v[3],v[4],v[5],a)){
if(!hash[nr][nc]){
hash[nr][nc]=1;
vector<ll> nv = v;
if(i==0){
nv[2] = a[nr-1][nc];
}else if(i==1){
nv[4] = a[nr][nc-1];
}else if(i==2){
nv[3] = a[nr+1][nc];
}else{
nv[5] = a[nr][nc+1];
}
nv[0]=nr;
nv[1]=nc;
pq.push(nv);
}
}
}
}
return ans;
}