| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 823138 | vjudge1 | 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>
#include "rect.h"
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 2500, M = 2500 ;
ll pref[N + 1][M + 1], mt[N + 1][M + 1] ;
bool us[N + 1][M + 1] ;
ll get_sum(ll x1, ll y1, ll x2, ll y2)
{
return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1] ;
}
ll count_rectangles(vector<vector<ll>> v)
{
bool flag1 = 0 ;
ll ans = 0 ;
ll n = v.size(), m = v[0].size() ;
for(ll i = 0 ; i < n ; i++)
for(ll j = 0 ; j < m ; j++)
if(v[i][j] > 1)flag1 = 1 ;
if(n <= 80 && m <= 80 || n <= 3)
{
ll mx_str[n][m][m] = {}, mx_stl[m][n][n] = {} ;
for(ll i = 0 ; i < n ; i++)
for(ll j = 0 ; j < m ; j++)
{
ll now = 0 ;
for(ll q = j ; q < m ; q++)
now = max(now, v[i][q]), mx_str[i][j][q] = now ;
}
for(ll i = 0 ; i < m ; i++)
for(ll j = 0 ; j < n ; j++)
{
ll now = 0 ;
for(ll q = j ; q < n ; q++)
now = max(now, v[q][i]), mx_stl[i][j][q] = now ;
}
for(ll x1 = 1 ; x1 < n - 1 ; x1++)
for(ll y1 = 1 ; y1 < m - 1 ; y1++)
for(ll x2 = x1 ; x2 < n - 1 ; x2++)
for(ll y2 = y1 ; y2 < m - 1 ; y2++)
{
bool flag = 1 ;
for(ll i = x1 ; i <= x2 ; i++)
if(mx_str[i][y1][y2] >= min(v[i][y1 - 1], v[i][y2 + 1]))
flag &= 0 ;
for(ll i = y1 ; i <= y2 ; i++)
if(mx_stl[i][x1][x2] >= min(v[x1 - 1][i], v[x2 + 1][i]))
flag &= 0 ;
if(flag)
ans += flag ;
}
return ans ;
}
if(!flag1)
{
for(ll i = 1 ; i <= n ; i++)
for(ll j = 1 ; j <= m ; j++)
mt[i][j] = v[i - 1][j - 1] ;
for(ll i = 1 ; i <= n ; i++)
{
ll now = 0 ;
for(ll j = 1 ; j <= m ; j++)
{
now += mt[i][j] ;
pref[i][j] = pref[i - 1][j] + now ;
}
}
for(ll i = 1 ; i <= n ; i++)
for(ll j = 1 ; j <= m ; j++)
{
if(mt[i][j])
continue ;
ll l = 0, r = j, x1 = i, y1 = j, x2 = i, y2 = j ;
while(l + 1 < r)
{
ll mid = (l + r) / 2 ;
if(get_sum(i, mid, i, j))
l = mid ;
else
r = mid ;
}
y1 = r ;
l = j, r = m + 1 ;
while(l + 1 < r)
{
ll mid = (l + r) / 2 ;
if(get_sum(i, j, i, mid))
r = mid ;
else
l = mid ;
}
y2 = l ;
l = 0, r = i ;
while(l + 1 < r)
{
ll mid = (l + r) / 2 ;
if(get_sum(mid, j, i, j))
l = mid ;
else
r = mid ;
}
x1 = r ;
l = i, r = n + 1 ;
while(l + 1 < r)
{
ll mid = (l + r) / 2 ;
if(get_sum(i, j, mid, j))
r = mid ;
else
l = mid ;
}
x2 = l ;
if(x1 > 1 && x1 < n && x2 > 1 && x2 < n && y1 > 1 && y1 < m && y2 > 1 && y2 < m && !get_sum(x1, y1, x2, y2) && get_sum(x1 - 1, y1, x2 + 1, y2) == (y2 - y1 + 1) * 2 && get_sum(x1, y1 - 1, x2, y2 + 1) == (x2 - x1 + 1) * 2 && !us[x1][y1])
{
us[x1][y1] = 1 ;
ans++ ;
}
}
return ans ;
}
if(n <= 200 && m <= 200)
{
return ans ;
}
return ans ;
}
//signed main()
//{
// ios_base::sync_with_stdio( 0 ) ;
// cin.tie( 0 ) ;
// cout.tie( 0 ) ;
// ll n, m ;
// cin >> n >> m ;
// vector<vector<ll>> v ;
// for(ll i = 0 ; i < n ; i++)
// {
// vector<ll> abu ;
// for(ll j = 0 ; j < m ; j++)
// {
// ll num ;
// cin >> num ;
// abu.push_back(num) ;
// }
// v.push_back(abu) ;
// }
// cout << count_rectangles(v) ;
// return 0 ;
//}