Submission #299224

#	Time	Username	Problem	Language	Result	Execution time	Memory
299224		antimirage	Rectangles (IOI19_rect)	C++14	0 / 100	457 ms	311276 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

const int N = (int)7e6 + 7;

struct DSU {
	int par[N], sz[N];
	int mnx[N], mxx[N], mny[N], mxy[N];
	int sum[N];
	DSU() {
		fill(sz, sz + N, 1);
		iota(par, par + N, 0);
	}
	int getpar(int a) {
		return (par[a] == a) ? a : par[a] = getpar(par[a]);
	}
	void connect(int a, int b) {
		a = getpar(a);
		b = getpar(b);
		if (a != b) {
			if (sz[a] > sz[b]) swap(a, b);
			sz[b] += sz[a];
			par[a] = b;
			mnx[b] = min(mnx[b], mnx[a]);
			mxx[b] = max(mxx[b], mxx[a]);
			mny[b] = min(mny[b], mny[a]);
			mxy[b] = max(mxy[b], mxy[a]);
			sum[b] += sum[a];
		}
	}
}dsu;

int n, m;

int getpos(int x, int y) {
	return x * m + y;
}

vector <int> vec[N];

long long count_rectangles(std::vector<std::vector<int> > a) {
	n = a.size();
	m = a[0].size();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			dsu.mnx[getpos(i, j)] = dsu.mxx[getpos(i, j)] = i;
			dsu.mny[getpos(i, j)] = dsu.mxy[getpos(i, j)] = j;
			dsu.sum[getpos(i, j)] = 4;
			if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
				dsu.sum[getpos(i, j)] = 1e5;
			}
			vec[a[i][j]].push_back(getpos(i, j));
		}
	}
	long long ans = 0;
	for (int i = 0; i < N; i++) {
		if (vec[i].empty()) continue;
		int res = 0;
		for (int to : vec[i]) {
			if (to % m != 0) { // y - 1
				if (a[to / m][to % m - 1] < i) {
					dsu.connect(to, to - 1);
					res++;
				} else {
					dsu.sum[to - 1]--;
				}
			} 
			if (to % m != m - 1) { // y + 1
				if (a[to / m][to % m + 1] < i) {
					dsu.connect(to, to + 1);
					res++;
				} else {
					dsu.sum[to + 1]--;
				}
			}
			if (to / m > 0) { // x - m
				if (a[to / m - 1][to % m] < i) {
					dsu.connect(to, to - m);
					res++;
				} else {
					dsu.sum[to - m]--;
				}
			}	
			if (to / m < n - 1) { // x + m
				if (a[to / m + 1][to % m] < i) {
					dsu.connect(to, to + m);
					res++;
				} else {
					dsu.sum[to + m]--;
				}
			}
			dsu.sum[dsu.getpar(to)] -= res;
		}
		for (int to : vec[i]) {
			int par = dsu.getpar(to);
			int sum = dsu.sum[par];
			int need = ((dsu.mxx[par] - dsu.mnx[par] + 1) + (dsu.mxy[par] - dsu.mny[par] + 1)) * 2;
			int area = (dsu.mxx[par] - dsu.mnx[par] + 1) * (dsu.mxy[par] - dsu.mny[par] + 1);
			if (sum == need && dsu.sz[par] == area) {
				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: 0 / 13
• Subtask 7: 0 / 28