제출 #589517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589517		farhan132	Rectangles (IOI19_rect)	C++17	13 / 100	703 ms	194712 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll N = 2505;

ll Left[N][N];
ll Down[N][N];
vector < ll > Row[N], Col[N];

ll sum[N][N];

ll req(ll x1, ll y1, ll x2, ll y2){
	return sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
}

long long count_rectangles(std::vector<std::vector<int> > a) {

	ll n = a.size();
	ll m = a[0].size();
	if(min(n, m) < 3) return 0;

	n -= 2; m -= 2; ll ans = 0;
	
	for(ll i = 1; i <= n; i++){
		ll last = m;
		for(ll j = m; j >= 1; j--){
			if(a[i][j] == 0){
				Left[i][j] = last;
				continue;
			}
			last = j - 1;
		}
	}
	for(ll j = 1; j <= m; j++){
		ll last = n;
		for(ll i = n; i >= 1; i--){
			if(a[i][j] == 0){
				Down[i][j] = last;
				continue;
			}
			last = i - 1;
		}
	}
	for(ll i = 0; i <= n + 1; i++){
		for(ll j = 0; j <= m + 1; j++){
			if(a[i][j] == 0){
				Row[i].pb(j);
				Col[j].pb(i);
			}
			sum[i][j] = a[i][j];
			if(j) sum[i][j] += sum[i][j - 1]; 
		}
	}
	for(ll j = 0; j <= m + 1; j++){
		for(ll i = 0; i <= n + 1; i++){
			if(i) sum[i][j] += sum[i - 1][j];
		}
	}

	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= m; j++){
			if(a[i][j]) continue;
			ll x = Down[i][j], y = Left[i][j];
			// (i, j) -- (x, y)
			auto it1 = lower_bound(Row[i-1].begin(), Row[i-1].end(), j);
			if(it1 != Row[i-1].end() && *it1 <= y) continue;
			auto it2 = lower_bound(Row[x+1].begin(), Row[x+1].end(), j);
			if(it2 != Row[x+1].end() && *it2 <= y) continue;

			auto it3 = lower_bound(Col[j-1].begin(), Col[j-1].end(), i);
			if(it3 != Col[j-1].end() && *it3 <= x) continue;
			auto it4 = lower_bound(Col[y+1].begin(), Col[y+1].end(), i);
			if(it4 != Col[y+1].end() && *it4 <= x) continue;
			if(req(i, j, x, y) == 0) ans++;
		}
	}


	return ans;
}

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