제출 #589522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589522		farhan132	Rectangles (IOI19_rect)	C++17	27 / 100	5051 ms	219288 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 = 703;
 
ll R_mx[N][N][11], C_mx[N][N][11];
bitset < N > b[N][N];
 
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;
	memset(R_mx, 0, sizeof(R_mx));
	memset(C_mx, 0, sizeof(C_mx));
 
	for(ll R = 1; R <= n; R++){
		// len = 1
		for(ll i = 1; i <= m; i++){
			R_mx[R][i][0] = a[R][i];
		}
		for(ll i = m; i >= 1; i--){
			for(ll j = 1; j < 11; j++){
				R_mx[R][i][j] = R_mx[R][i][j - 1];
				if(i + (1 << (j - 1)) <= m){
					R_mx[R][i][j] = max(R_mx[R][i][j], R_mx[R][i + (1 << (j - 1))][j - 1]);
				} 
			}
		}
		for(ll i = 0; i < m; i++){
			ll mx = 0;
			for(ll j = i + 1; j <= m; j++){
				mx = max(mx, a[R][j]);
				if(mx < min(a[R][i], a[R][j + 1])) b[R][i][j] = 1;
			}
		}
	}
	for(ll C = 1; C <= m; C++){
		// len = 1
		for(ll i = 1; i <= n; i++){
			C_mx[C][i][0] = a[i][C];
		}
		for(ll i = n; i >= 1; i--){
			for(ll j = 1; j < 11; j++){
				C_mx[C][i][j] = C_mx[C][i][j - 1];
				if(i + (1 << (j - 1)) <= n){
					C_mx[C][i][j] = max(C_mx[C][i][j], C_mx[C][i + (1 << (j - 1))][j - 1]);
				} 
			}
		}
	}
/*	for(ll i = 1; i <= m; i++){
		for(ll j = 1; j <= n; j++){
				cout << j << ' ' << i << ' ' << 0 << ' ' << C_mx[j][i][0] << '\n';
		}
	}*/
	ll ans = 0;
	for(ll r1 = 1; r1 <= n; r1++){
		for(ll c1 = 1; c1 <= m; c1++){
			bitset < N > cur; cur.set();
			for(ll r2 = r1; r2 <= n; r2++){
				cur &= b[r2][c1-1];
				for(ll c2 = c1; c2 <= m; c2++){
					// (r1, c1) --- (r2, c2)
					
				    ll LG = 31 - __builtin_clz(r2 - r1 + 1);
				    if(min(a[r1-1][c2], a[r2+1][c2]) <= max(C_mx[c2][r1][LG], C_mx[c2][r2 - (1 << LG) + 1][LG])) break;
				    if(cur[c2]) ans++;
				}
			}
		}
	}
 
	return ans;
}

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