Submission #297353

#TimeUsernameProblemLanguageResultExecution timeMemory
297353infinite_iqRectangles (IOI19_rect)C++14
27 / 100
488 ms480684 KiB
#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 [209][209] ; vi ok [209][209][209] ; int mx [209][209][209][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 ; }

Compilation message (stderr)

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