| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 297356 | infinite_iq | Rectangles (IOI19_rect) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std ;
#define pb push_back
#define C continue
#define lb lower_bound
typedef long long ll ;
typedef vector < int > vi ;
#include "rect.h"
int n , m ;
int a [709][709] ;
vi ok [709][709][709] ;
int mx [709][709][709][2] ;
long long count_rectangles ( vector <vi> A ) {
n = A .size () ;
m = A [0] .size () ;
for ( int i = 0 ; i < n ; i ++ ) {
for ( int j = 0 ; j < m ; j ++ ) {
a [i][j] = A [i][j] ;
}
}
for ( int i = 0 ; i < n ; i ++ ) {
for ( int j = 0 ; j < m ; j ++ ) {
int Mx = 0 ;
for ( int k = j ; k < m ; k ++ ) {
Mx = max ( Mx , a [i][k] ) ;
mx [i][j][k][0] = Mx ;
}
}
}
for ( int k = 0 ; k < m ; k ++ ) {
for ( int i = 0 ; i < n ; i ++ ) {
int Mx = 0 ;
for ( int j = i ; j < n ; j ++ ) {
Mx = max ( Mx , a [j][k] ) ;
mx [k][i][j][1] = Mx ;
}
}
}
for ( int i = 1 ; i < n-1 ; i ++ ) {
for ( int j = i ; j < n-1 ; j ++ ) {
for ( int k = 1 ; k < m-1 ; k ++ ) {
for ( int l = k ; l < m-1 ; l ++ ) {
if ( min ( a [i-1][l] , a [j+1][l] ) <= mx [l][i][j][1] ) {
// k = l ;
break ;
}
ok [i][j][k] .pb ( l ) ;
}
}
}
}
ll ans = 0 ;
for ( int k = 1 ; k < m -1 ; k ++ ) {
for ( int l = k ; l < m -1 ; l ++ ) {
for ( int i = 1 ; i < n -1 ; i ++ ) {
for ( int j = i ; j < n -1 ; j ++ ) {
if ( min ( a [j][k-1] , a [j][l+1] ) <= mx [j][k][l][0] ) {
// i = j ;
break ;
}
auto it = lb ( ok [i][j][k] .begin () , ok [i][j][k] .end () , l ) - ok [i][j][k] .begin () ;
if ( it == ok [i][j][k] .size () ) C ;
ans += ( ok [i][j][k][it] == l ) ;
}
}
}
}
return ans ;
}