Submission #170110

#	Time	Username	Problem	Language	Result	Execution time	Memory
170110		socho	Rectangles (IOI19_rect)	C++14	13 / 100	1086 ms	258332 KiB

rect

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

int n, m;
vector<vector<pair<int, int> > > par;
vector<vector<int> > lowi, lowj, highi, highj;
vector<vector<int> > grid;
vector<vector<int> > pf;

void setup(int n, int m) {
	for (int i=0; i<n; i++) {
		par.push_back(vector<pair<int, int> >(m));
		lowi.push_back(vector<int>(m));
		lowj.push_back(vector<int>(m));
		highi.push_back(vector<int>(m));
		highj.push_back(vector<int>(m));
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			par[i][j] = make_pair(i, j);
			lowi[i][j] = i;
			lowj[i][j] = j;
			highi[i][j] = i;
			highj[i][j] = j;
		}
	}
}

pair<int, int> parent(pair<int, int> where) {
	if (par[where.first][where.second] == where) return where;
	return par[where.first][where.second] = parent(par[where.first][where.second]);
}

bool arc(pair<int, int> a, pair<int, int> b) {
	return parent(a) == parent(b);
}

void connect(pair<int, int> a, pair<int, int> b) {
	if (arc(a, b)) return;
	pair<int, int> ax = parent(a);
	pair<int, int> bx = parent(b);
	par[bx.first][bx.second] = ax;
	lowi[ax.first][ax.second] = min(lowi[ax.first][ax.second], lowi[bx.first][bx.second]);
	lowj[ax.first][ax.second] = min(lowj[ax.first][ax.second], lowj[bx.first][bx.second]);
	highi[ax.first][ax.second] = max(highi[ax.first][ax.second], highi[bx.first][bx.second]);
	highj[ax.first][ax.second] = max(highj[ax.first][ax.second], highj[bx.first][bx.second]);
}

int getlowi(pair<int, int> a) {
	a = parent(a);
	return lowi[a.first][a.second];
}

int getlowj(pair<int, int> a) {
	a = parent(a);
	return lowj[a.first][a.second];
}

int gethighi(pair<int, int> a) {
	a = parent(a);
	return highi[a.first][a.second];
}

int gethighj(pair<int, int> a) {
	a = parent(a);
	return highj[a.first][a.second];
}

void dopf() {
	for (int i=1; i<n; i++) {
		pf[i][0] = pf[i-1][0] + grid[i][0];
	}
	for (int i=1; i<m; i++) {
		pf[0][i] = pf[0][i-1] + grid[0][i];
	}
	for (int i=1; i<n; i++) {
		for (int j=1; j<m; j++) {
			pf[i][j] = pf[i-1][j] + pf[i][j-1] - pf[i-1][j-1] + grid[i][j];
		}
	}
}

int pfq(int a, int b) {
	if (a < 0) return 0;
	if (b < 0) return 0;
	return pf[min(n-1, a)][min(m-1, b)];
}

int qpf(int a, int b, int c, int d) {
	return pfq(c, d) + pfq(a-1, b-1) - pfq(c, b-1) - pfq(a-1, d);
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	
	n = a.size();
	m = a[0].size();
	grid = a;
	pf = a;
	dopf();
	
	setup(n, m);
	for (int i=0; i<n-1; i++) {
		for (int j=0; j<m; j++) {
			if (a[i][j] == 0 && a[i+1][j] == 0) {
				// cout << i << ' ' << j << ' ' << i + 1 << ' ' << j << endl;
				connect(make_pair(i, j), make_pair(i+1, j));
			}
		}
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<m-1; j++) {
			if (a[i][j] == 0 && a[i][j+1] == 0) {
				// cout << i << ' ' << j << ' ' << i << ' ' << j + 1 << endl;
				connect(make_pair(i, j), make_pair(i, j+1));
			}
		}
	}
	
	int res = 0;
	
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			pair<int, int> f = make_pair(i, j);
			// cout << i << ':' << j << " par: " << parent(f).first << ':' << parent(f).second << " val: " << a[i][j] << endl;
			if (parent(f) == f && a[i][j] == 0) {
				// cout << "SEARCH" << endl;
				int li = getlowi(f);
				int hi = gethighi(f);
				int lj = getlowj(f);
				int hj = gethighj(f);
				if (li == 0) continue;
				if (lj == 0) continue;
				if (hi == n-1) continue;
				if (hj == m-1) continue;
				// cout << li << ' ' << lj << ' ' << hi << ' ' << hj << endl;
				// cout << " > " << i << ' ' << j << endl;
				if (qpf(li, lj, hi, hj) == 0) {
					// cout << " USE " << endl;
					res++;
				}
			}
		}
	}
	
	return res;
	
}

• 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