Submission #1066194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066194		Tsovak	Rectangles (IOI19_rect)	C++17	100 / 100	1985 ms	906116 KiB

rect

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include "rect.h"
using namespace std;

// -------------------- Typedefs -------------------- //

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;

// -------------------- Defines -------------------- //

#define pr pair
#define mpr make_pair
#define ff first
#define ss second

#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue

#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define clr(x) (x).clear()

#define ft front
#define bk back
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back

#define lb lower_bound
#define ub upper_bound
#define bs binary_search

// -------------------- Constants -------------------- //

const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);

// -------------------- Solution -------------------- //

const int N = 2505, M = 2505, LG = 13;
int a[N][M];
short ul[N][M], ur[N][M], uu[N][M], ud[N][M];
short hl[N][M], hr[N][M], hu[N][M], hd[N][M];
int n, m, lgn, lgm;

pr<short, short> h[N];
pr<short, short> th[N][M][LG], tv[M][N][LG];

ll e[N * M];
int ind;

void bld()
{
	int i, j, k;
	int g;

	h[1] = mpr(0, 1);
	for (i = 2; i <= 2503; i++) {
		h[i] = h[i - 1];
		if (h[i].ss * 2 <= i) {
			h[i].ff++;
			h[i].ss *= 2;
		}
	}

	while ((1 << lgn) <= n) lgn++;
	lgn--;
	while ((1 << lgm) <= m) lgm++;
	lgm--;


	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) th[i][j][0] = mpr(hu[i][j], hd[i][j]);

		g = 1;
		for (k = 1; k <= lgm; k++) {
			for (j = 1; j <= m - 2 * g + 1; j++) {
				th[i][j][k].ff = max(th[i][j][k - 1].ff, th[i][j + g][k - 1].ff);
				th[i][j][k].ss = min(th[i][j][k - 1].ss, th[i][j + g][k - 1].ss);
			}
			g *= 2;
		}
	}

	for (j = 1; j <= m; j++) {
		for (i = 1; i <= n; i++) tv[j][i][0] = mpr(hl[i][j], hr[i][j]);

		g = 1;
		for (k = 1; k <= lgn; k++) {
			for (i = 1; i <= n - 2 * g + 1; i++) {
				tv[j][i][k].ff = max(tv[j][i][k - 1].ff, tv[j][i + g][k - 1].ff);
				tv[j][i][k].ss = min(tv[j][i][k - 1].ss, tv[j][i + g][k - 1].ss);
			}
			g *= 2;
		}
	}

	return;
}

pr<int, int> qryh(int i, int l, int r)
{
	int len = r - l + 1;

	pr<int, int> res;

	res.ff = max(th[i][l][h[len].ff].ff, th[i][r - h[len].ss + 1][h[len].ff].ff);
	res.ss = min(th[i][l][h[len].ff].ss, th[i][r - h[len].ss + 1][h[len].ff].ss);

	return res;
}

pr<int, int> qryv(int j, int l, int r)
{
	int len = r - l + 1;

	pr<int, int> res;

	res.ff = max(tv[j][l][h[len].ff].ff, tv[j][r - h[len].ss + 1][h[len].ff].ff);
	res.ss = min(tv[j][l][h[len].ff].ss, tv[j][r - h[len].ss + 1][h[len].ff].ss);

	return res;
}

ll count_rectangles(vector<vector<int>> a0)
{
	int i, j;

	n = sz(a0); m = sz(a0[0]);

	for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) a[i][j] = ++a0[i - 1][j - 1];

	if (n < 3 || m < 3) return 0;

	// closest biggers

	stack<pr<int, int>> st;

	for (i = 1; i <= n; i++) {
		while (!st.empty()) st.pop();

		for (j = 1; j <= m; j++) {
			while (!st.empty() && st.top().ff <= a[i][j]) st.pop();

			if (!st.empty()) ul[i][j] = st.top().ss;

			st.push(mpr(a[i][j], j));
		}

		while (!st.empty()) st.pop();

		for (j = m; j >= 1; j--) {
			while (!st.empty() && st.top().ff <= a[i][j]) st.pop();

			if (!st.empty()) ur[i][j] = st.top().ss;
			else ur[i][j] = m + 1;

			st.push(mpr(a[i][j], j));
		}
	}

	for (j = 1; j <= m; j++) {
		while (!st.empty()) st.pop();

		for (i = 1; i <= n; i++) {
			while (!st.empty() && st.top().ff <= a[i][j]) st.pop();

			if (!st.empty()) uu[i][j] = st.top().ss;

			st.push(mpr(a[i][j], i));
		}

		while (!st.empty()) st.pop();

		for (i = n; i >= 1; i--) {
			while (!st.empty() && st.top().ff <= a[i][j]) st.pop();

			if (!st.empty()) ud[i][j] = st.top().ss;
			else ud[i][j] = n + 1;

			st.push(mpr(a[i][j], i));
		}
	}

	// closest overlappings

	for (i = 1; i <= n; i++) {
		while (!st.empty()) st.pop();

		for (j = 3; j <= m; j++) {
			st.push(mpr(j - 1, ur[i][j - 1]));

			while (!st.empty() && st.top().ss <= j) st.pop();

			if (st.empty()) hl[i][j] = 0;
			else hl[i][j] = st.top().ff;
		}

		while (!st.empty()) st.pop();

		for (j = m - 2; j >= 1; j--) {
			st.push(mpr(ul[i][j + 1], j + 1));

			while (!st.empty() && st.top().ff >= j) st.pop();

			if (st.empty()) hr[i][j] = m + 1;
			else hr[i][j] = st.top().ss;
		}
	}

	for (j = 1; j <= m; j++) {
		while (!st.empty()) st.pop();

		for (i = 3; i <= n; i++) {
			st.push(mpr(i - 1, ud[i - 1][j]));

			while (!st.empty() && st.top().ss <= i) st.pop();

			if (st.empty()) hu[i][j] = 0;
			else hu[i][j] = st.top().ff;
		}

		while (!st.empty()) st.pop();

		for (i = n - 2; i >= 1; i--) {
			st.push(mpr(uu[i + 1][j], i + 1));

			while (!st.empty() && st.top().ff >= i) st.pop();

			if (st.empty()) hd[i][j] = n + 1;
			else hd[i][j] = st.top().ss;
		}
	}

	bld();

	int li, ri, lj, rj;

	for (i = 2; i < n; i++) {
		for (j = 2; j < m; j++) {
			li = uu[i][j]; ri = ud[i][j];
			lj = ul[i][j]; rj = ur[i][j];

			if (li <= 0 || ri >= n + 1 || lj <= 0 || rj >= m + 1) continue;

			if (qryh(li, lj + 1, rj - 1).ss < ri) continue;
			if (qryh(ri, lj + 1, rj - 1).ff > li) continue;

			if (qryv(lj, li + 1, ri - 1).ss < rj) continue;
			if (qryv(rj, li + 1, ri - 1).ff > lj) continue;

			e[++ind] = 1LL + (1LL * li) + (2500LL * ri) + (2500LL * 2500LL * lj) + (2500LL * 2500LL * 2500LL * rj);
		}
	}

	int ans = 0;

	sort(e + 1, e + ind + 1);
	for (i = 1; i <= ind; i++) ans += (e[i - 1] != e[i]);

	return ans;
}

/*
	# # # #   # # # #   # # # #   #       #    #       #     #
	   #      #         #     #    #     #    # #      #   #
	   #      # # # #   #     #     #   #    #   #     # #
	   #            #   #     #      # #    # # # #    #   #
	   #      # # # #   # # # #       #    #       #   #     #
*/

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