Submission #1031017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031017		fv3	Rectangles (IOI19_rect)	C++14	37 / 100	5097 ms	184764 KiB

rect

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

using namespace std;
typedef long long ll;

int N, M;
vector<vector<int>> grid;

struct node
{
	int n = 0;
};
node merge(node a, node b)
{
	return {max(a.n, b.n)};
}
node emptyNode = {0};

vector<vector<node>> st_v, st_h;
int nt_v = 1, nt_h = 1;

node v_range(int l, int r, int k, int x, int y, int i)
{
	if (y < l || x > r) return emptyNode;
	if (x >= l && y <= r) return st_v[i][k];
	int c = (x + y) / 2;
	return merge(v_range(l, r, k*2, x, c, i), v_range(l, r, k*2|1, c+1, y, i));
}

node h_range(int l, int r, int k, int x, int y, int i)
{
	if (y < l || x > r) return emptyNode;
	if (x >= l && y <= r) return st_h[i][k];
	int c = (x + y) / 2;
	return merge(h_range(l, r, k*2, x, c, i), h_range(l, r, k*2|1, c+1, y, i));
}

ll count_rectangles(vector<vector<int>> a) 
{
	N = a.size();
	M = a[0].size();

	// Construct horizontal segment trees
	while (nt_h < M) nt_h <<= 1;
	for (int i = 0; i < N; i++)
	{
		st_h.push_back(vector<node>(2 * nt_h));
		for (int j = 0; j < M; j++)
			st_h[i][nt_h + j].n = a[i][j];

		for (int j = nt_h - 1; j >= 1; j--)
			st_h[i][j] = merge(st_h[i][j*2], st_h[i][j*2|1]); 
	}

	// Construct vertical segment trees
	while (nt_v < N) nt_v <<= 1;
	for (int i = 0; i < M; i++)
	{
		st_v.push_back(vector<node>(2 * nt_v));
		for (int j = 0; j < N; j++)
			st_v[i][nt_v + j].n = a[j][i];

		for (int j = nt_v - 1; j >= 1; j--)
			st_v[i][j] = merge(st_v[i][j*2], st_v[i][j*2|1]);
	}

	set<ll> sv, sh;

	for (int x1 = 1; x1 < M - 1; x1++)
	{
		for (int x2 = x1; x2 < M - 1; x2++)
		{
			for (int y1 = 1; y1 < N - 1; y1++)
			{
				for (int y2 = y1; y2 < N - 1; y2++)
				{
					if (h_range(x1, x2, 1, 0, nt_h - 1, y2).n >= min(a[y2][x1-1], a[y2][x2+1])) 
						break;

					sh.insert(x1*15625000000ll+x2*6250000ll+y1*2500+y2);
				}
			}
		}
	}

	ll res = 0;
	for (int y1 = 1; y1 < N - 1; y1++)
	{
		for (int y2 = y1; y2 < N - 1; y2++)
		{
			for (int x1 = 1; x1 < M - 1; x1++)
			{
				for (int x2 = x1; x2 < M - 1; x2++)
				{
					if (v_range(y1, y2, 1, 0, nt_v - 1, x2).n >= min(a[y1-1][x2], a[y2+1][x2])) 
						break;

					if (sh.count(x1*15625000000ll+x2*6250000ll+y1*2500+y2))
					{
						res++;
					}
				}
			}
		}
	}

	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