Submission #256054

#	Time	Username	Problem	Language	Result	Execution time	Memory
256054		b00n0rp	Rectangles (IOI19_rect)	C++17	50 / 100	610 ms	386528 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define pii pair<int,int>
#define F first
#define S second

const int MX = 205;

int n,m;
bitset<MX> hor[MX][MX],ver[MX][MX];
bitset<MX> gg[MX];

bool vis[2505][2505];

vector<pii> cc;

vector<vi> A;

bool reach(int x,int y){
	if(x < 0 or y < 0 or x >= n or y >= m) return 0;
	if(vis[x][y]) return 0;
	return A[x][y] == 0;
}

void dfs(int x,int y){
	// cout << x << " " << y << endl;
	cc.pb({x,y});
	vis[x][y] = 1;
	if(reach(x+1,y)) dfs(x+1,y);
	if(reach(x-1,y)) dfs(x-1,y);
	if(reach(x,y+1)) dfs(x,y+1);
	if(reach(x,y-1)) dfs(x,y-1);
}

ll count_rectangles(vector<vi> a) {
	n = a.size();
	m = a[0].size();
	A = a;
	if(n <= 2) return 0;
	ll ans = 0;
	if(n == 3){
		FOR(i,1,m-1){
			int mx = -1;
			FOR(j,i,m-1){
				if(a[1][j] >= min(a[0][j],a[2][j])) break;
				mx = max(mx,a[1][j]);
				ans += (mx < min(a[1][i-1],a[1][j+1])); 
			}
		}
		return ans;
	}
	if(n <= 200 and m <= 200){
		REP(i,n){
			REP(j,m){
				int mx = -1;
				FOR(k,j,m){
					mx = max(mx,a[i][k]);
					hor[j][k][i] = (j and k < m-1 and mx < min(a[i][j-1],a[i][k+1]));
				}
			}
		}
		REP(j,m){
			REP(i,n){
				int mx = -1;
				FOR(k,i,n){
					mx = max(mx,a[k][j]);
					ver[i][k][j] = (i and k < n-1 and mx < min(a[i-1][j],a[k+1][j]));
				}
			}
		}
		REP(i1,n){
			REP(j1,m){
				FOR(i2,i1,n){
					gg[i2].reset();
				}
				FOR(i2,i1,n){
					FOR(j2,j1,m){
						if(!ver[i1][i2][j2]) break;
						gg[i2][j2] = 1;
					}
				}
				FOR(j2,j1,m){
					FOR(i2,i1,n){
						if(!hor[j1][j2][i2]) break;
						ans += gg[i2][j2];
					}
				}
			}
		}
		return ans;
	}
	REP(i,n) REP(j,m) vis[i][j] = 0;
	REP(i,n){
		REP(j,m){
			if(!reach(i,j)) continue;
			cc.clear();
			dfs(i,j);
			int mnx = cc[0].F,mxx = cc[0].F,mny = cc[0].S,mxy = cc[0].S;
			for(auto bruh:cc){
				mnx = min(mnx,bruh.F);
				mny = min(mny,bruh.S);
				mxx = max(mxx,bruh.F);
				mxy = max(mxy,bruh.S);
			}
			// cout << mnx << " " << mxx << " " << mny << " " << mxy << endl;
			if(mnx == 0 or mny == 0) continue;
			if(mxx == n-1 or mxy == m-1) continue;
			ans += ((mxx-mnx+1)*(mxy-mny+1) == (int)cc.size());
		}
	}
	return ans;
}

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