Submission #297364

#	Time	Username	Problem	Language	Result	Execution time	Memory
297364		infinite_iq	Rectangles (IOI19_rect)	C++14	0 / 100	85 ms	78588 KiB

rect

#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   [3][2509] ;
vi ok   [3][3][2509] ;
int mx0 [3][2509][2509] ;
int mx1 [2509][3][3] ;
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] ) ;
                                mx0 [i][j][k] = 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] ) ;
                                mx1 [k][i][j] = 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] ) <= mx1 [l][i][j] ) {
                                                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] ) <= mx0 [j][k][l] ) {
                                                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 ;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:63:49: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                                         if ( it == ok [i][j][k] .size () ) C ;
      |                                              ~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28