제출 #826905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
826905		vjudge1	Rectangles (IOI19_rect)	C++17	13 / 100	320 ms	202188 KiB

rect

#include <bits/stdc++.h>
#define ll long long
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

using namespace std;

#define pii pair <int, int>
const int maxn=2e5+10;

int kx[] = {1, -1, 0, 0};
int ky[] = {0, 0, -1, 1};

long long count_rectangles(vector<vector<int> > A)
{
	int n = A.size();
	int m = A[0].size();
	vector <vector <int> > a(n+2), L(n+2), R(n+2), up(n+2), down(n+2), used(n+2);
	forn(0, i, n+1) 
	{
		used[i].assign(m+2, 0);
		a[i].assign(m+2, 0);
		up[i].assign(m+2, 0);
		down[i].assign(m+2, 0);
		L[i].assign(m+2, 0);
		R[i].assign(m+2, 0);
	}
	forn(1, i, n)
	{
		forn(1, j, m) a[i][j] = A[i-1][j-1];
	}
	forn(0, i, n+1)
	{
		a[i][0] = 1;
		a[i][m+1] = 1;
	}
	forn(0, j, m+1)
	{
		a[0][j] = 1;
		a[n+1][j] = 1;
	}
	ll ans = 0;
	forn(1, i, n)
	{
		forn(1, j, m)
		{
			if(used[i][j] || a[i][j] == 1) continue;
			queue <pii> q;
			q.push({i, j});
			used[i][j] = 1;
			int mxx = 0;
			int mxy = 0;
			int mny = m+1;
			int mnx = n+1;
			int cnt = 0;
			while(q.size())
			{
				int x = q.front().f;
				int y = q.front().s;
				q.pop();
				mnx = min(mnx, x);
				mxx = max(mxx, x);
				mny = min(mny, y);
				mxy = max(mxy, y);
				cnt++;
				forn(0, k, 3)
				{
					int tox = kx[k] + x;
					int toy = ky[k] + y;
					if(!used[tox][toy] && a[tox][toy] == 0)
					{
						used[tox][toy] = 1;
						q.push({tox, toy});
					}
				}
			}
//			cout << mnx << " " << mny << " " << mxx << " " << mxy << endl;
			if(mnx != 1 && mxx != n && mny != 1 && mxy != m && 
			(mxx-mnx+1)*(mxy-mny+1) == cnt)
			{
				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