Submission #1078135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078135		Boas	Rectangles (IOI19_rect)	C++17	37 / 100	1347 ms	1048576 KiB

rect

#include "rect.h"

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sz(x) (int)x.size()
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define rev(x, i) for (int i = (int)x - 1; i >= 0; i--)
#define ALL(x) begin(x), end(x)
typedef signed i32;
typedef pair<int, int> ii;
typedef vector<i32> vi32;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vi32> vvi32;
typedef vector<vii> vvii;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;

long long count_rectangles(vvi a)
{
	int n = sz(a);	  // h
	int m = sz(a[0]); // w
	vvvi validUp(n, vvi(m, vi(m)));
	vvvi validDown(n, vvi(m, vi(m)));
	vvvi validL(m, vvi(n, vi(n)));
	vvvi validR(m, vvi(n, vi(n))); // omwisselen voor cache friendlyness?
	vvi minL(n, vi(m, 1e9)), minU(n, vi(m, 1e9)), maxR(n, vi(m, -1)), maxD(n, vi(m, -1));
	for (int c = 1; c < m - 1; c++)
	{
		for (int r = 1; r < n - 1; r++)
		{
			for (int c1 = c; c1 > 0; c1--)
			{
				if (a[r][c1] >= a[r][c + 1])
					break;
				minL[r][c] = c1;
			}
			for (int c2 = c; c2 < m - 1; c2++)
			{
				if (a[r][c2] >= a[r][c - 1])
					break;
				maxR[r][c] = c2;
			}
			for (int r1 = r; r1 > 0; r1--)
			{
				if (a[r1][c] >= a[r + 1][c])
					break;
				minU[r][c] = r1;
			}
			for (int r2 = r; r2 < n - 1; r2++)
			{
				if (a[r2][c] >= a[r - 1][c])
					break;
				maxD[r][c] = r2;
			}
		}
	}
	for (int c = 1; c < m - 1; c++)
	{
		for (int r1 = 1; r1 < n - 1; r1++)
		{
			int mnL = 0;
			int mxR = m;
			for (int r2 = r1; r2 < n - 1; r2++)
			{
				mnL = max(mnL, minL[r2][c]);
				mxR = min(mxR, maxR[r2][c]);
				validL[c][r1][r2] = mxR;
				validR[c][r1][r2] = mnL;
			}
		}
	}
	for (int r = 1; r < n - 1; r++)
	{
		for (int c1 = 1; c1 < m - 1; c1++)
		{
			int mnU = 0;
			int mxD = n;
			for (int c2 = c1; c2 < m - 1; c2++)
			{
				mnU = max(mnU, minU[r][c2]);
				mxD = min(mxD, maxD[r][c2]);
				validUp[r][c1][c2] = mxD;
				validDown[r][c1][c2] = mnU;
			}
		}
	}
	int treeM = 1;
	while (treeM < m)
		treeM *= 2;
	vector<vector<vvi>> tree(n, vvvi(n, vvi(treeM * 2)));
	// validR is geen voolean meer. het hangt af van l.
	// merge sort tree bouwen op validR, return count <= l
	for (int r1 = 1; r1 < n - 1; r1++)
	{
		for (int r2 = r1; r2 < n - 1; r2++)
		{
			for (int c = 1; c < m - 1; c++)
			{
				tree[r1][r2][treeM + c] = {validR[c][r1][r2]};
			}
			rev(treeM, i)
			{
				merge(ALL(tree[r1][r2][2 * i]),
					  ALL(tree[r1][r2][2 * i + 1]),
					  back_inserter(tree[r1][r2][i]));
			}
		}
	}
	auto query = [&](auto &&self, int r1, int r2, int i, int l, int r, int ql, int qr, int v) -> int
	{
		int mid = (l + r) / 2;
		if (qr < l || r < ql)
			return 0;
		if (ql <= l && r <= qr)
		{
			long int res = upper_bound(ALL(tree[r1][r2][i]), v) - tree[r1][r2][i].begin();
			return (int)res;
		}
		return self(self, r1, r2, 2 * i, l, mid, ql, qr, v) +
			   self(self, r1, r2, 2 * i + 1, mid + 1, r, ql, qr, v);
	};
	long long res = 0;
	for (int c = 1; c < m - 1; c++)
	{
		for (int r1 = 1; r1 < n - 1; r1++)
		{
			for (int r2 = r1; r2 < n - 1; r2++)
			{
				int mxR = validL[c][r1][r2];
				if (mxR == -1)
					break;
				int lo = c, hi = mxR;
				int ans = -1;
				while (hi >= lo)
				{
					int c2 = (lo + hi) / 2;
					if (validUp[r1][c][c2] >= r2 && validDown[r2][c][c2] <= r1)
					{
						ans = c2;
						lo = c2 + 1;
					}
					else
					{
						hi = c2 - 1;
					}
				}
				if (ans == -1)
					continue;
				res += query(query, r1, r2, 1, 0, treeM - 1, c, ans, c);
			}
		}
	}
	return res;
}

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