| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 297356 | infinite_iq | 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 <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 ;
}