Submission #1078059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078059		Boas	Rectangles (IOI19_rect)	C++17	0 / 100	903 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
	vvvb validUp(n, vvb(m, vb(m)));
	vvvb validDown(n, vvb(m, vb(m)));
	vvvb validL(m, vvb(n, vb(n)));
	vvvb validR(m, vvb(n, vb(n))); // omwisselen voor cache friendlyness?
	vvvi pSumValR(n, vvi(n, vi(m)));
	for (int c = 1; c < m - 1; c++)
	{
		for (int r1 = 1; r1 < n - 1; r1++)
		{
			bool valL = 1;
			bool valR = 1;
			for (int r2 = r1; r2 < n - 1; r2++)
			{
				valL &= (a[r2][c] < a[r2][c - 1]);
				valR &= (a[r2][c] < a[r2][c + 1]);
				validL[c][r1][r2] = valL;
				validR[c][r1][r2] = valR;
			}
		}
	}
	for (int r = 1; r < n - 1; r++)
	{
		for (int c1 = 1; c1 < m - 1; c1++)
		{
			bool valUp = 1;
			bool valDown = 1;
			for (int c2 = c1; c2 < m - 1; c2++)
			{
				valUp &= (a[r][c2] < a[r - 1][c2]);
				valDown &= (a[r][c2] < a[r + 1][c2]);
				validUp[r][c1][c2] = valUp;
				validDown[r][c1][c2] = valDown;
			}
		}
	}
	for (int r1 = 1; r1 < n - 1; r1++)
	{
		for (int r2 = r1; r2 < n - 1; r2++)
		{
			for (int c = 1; c < m - 1; c++)
			{
				pSumValR[r1][r2][c] = pSumValR[r1][r2][c - 1] + (validR[c][r1][r2]);
			}
		}
	}
	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++)
			{
				if (!validL[c][r1][r2])
					break;
				int lo = c, hi = m - 2;
				int ans = -1;
				while (hi >= lo)
				{
					int c2 = (lo + hi) / 2;
					if (validUp[r1][c][c2] && validDown[r2][c][c2])
					{
						ans = c2;
						lo = c2 + 1;
					}
					else
					{
						hi = c2 - 1;
					}
				}
				if (ans == -1)
					continue;
				res += pSumValR[r1][r2][ans] - pSumValR[r1][r2][c - 1];
			}
		}
	}
	return res;
}

• 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