제출 #297486

#제출 시각아이디문제언어결과실행 시간메모리
297486infinite_iqRectangles (IOI19_rect)C++14
13 / 100
392 ms98556 KiB
#include <bits/stdc++.h> using namespace std ; #define mid (l+r)/2 #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 [2509][2509] ; int pre [2509][2509] ; int Sum ( int i , int j , int k , int l ) { int sum = 0 ; sum += pre [j][l] ; sum -= ( i ? pre [i-1][l] : 0 ) ; sum -= ( k ? pre [j][k-1] : 0 ) ; sum += ( i && k ? pre [i-1][k-1] : 0 ) ; return sum ; } 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 ++ ) { pre [i][j] = a [i][j] ; pre [i][j] += ( i ? pre [i-1][j] : 0 ) ; pre [i][j] += ( j ? pre [i][j-1] : 0 ) ; pre [i][j] -= ( i && j ? pre [i-1][j-1] : 0 ) ; } } ll ans = 0 ; for ( int i = 1 ; i < n - 1 ; i ++ ) { for ( int k = 1 ; k < m - 1 ; k ++ ) { if ( a [i][k] == 1 ) C ; int l = i , r = n - 1 ; while ( r - l > 1 ) { if ( Sum ( i , mid , k , k ) == 0 ) l = mid ; else r = mid ; } int j = l ; l = k , r = m - 1 ; while ( r - l > 1 ) { if ( Sum ( i , i , k , mid ) == 0 ) l = mid ; else r = mid ; } if ( Sum ( i , j , k , l ) ) C ; if ( Sum ( i , j , k - 1 , k - 1 ) != j - i + 1 ) C ; if ( Sum ( i , j , l + 1 , l + 1 ) != j - i + 1 ) C ; if ( Sum ( i - 1 , i - 1 , k , l ) != l - k + 1 ) C ; if ( Sum ( j + 1 , j + 1 , k , l ) != l - k + 1 ) C ; ans ++ ; } } return ans ; }
#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...