Submission #589550

#	Time	Username	Problem	Language	Result	Execution time	Memory
589550		Soumya1	Rectangles (IOI19_rect)	C++17	37 / 100	1169 ms	1048576 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
	#include <debug_local.h>
#endif
using namespace std;
const int mxN = 7e6 + 5;
int bit[mxN];
void upd(int i, int v) {
	for (; i < mxN; i += i & (-i)) bit[i] += v;
}
int sum(int i) {
	int ret = 0;
	for (; i > 0; i -= i & (-i)) ret += bit[i];
	return ret;
}
long long count_rectangles(vector<vector<int>> a) {
	int n = a.size();
	int m = a[0].size();
	if (n <= 2 || m <= 2) return 0;
	long long ans = 0;
	bool good[n][n][m];
	memset(good, 0, sizeof good);
	for (int i = 1; i < n - 1; i++) {
		for (int j = 1; j < m - 1; j++) {
			int mx = 0;
			for (int ii = i; ii < n - 1; ii++) {
				mx = (i == ii ? a[i][j] : max(a[ii][j], mx));
				good[i][ii][j] = (mx < min(a[i - 1][j], a[ii + 1][j]));
			}
		}
	}
	bool gg[m][m][n];
	memset(gg, 0, sizeof gg);
	for (int i = 1; i < m - 1; i++) {
		for (int j = 1; j < n - 1; j++) {
			int mx = 0;
			for (int ii = i; ii < m - 1; ii++) {
				mx = (i == ii ? a[j][i] : max(a[j][ii], mx));
				gg[i][ii][j] = (mx < min(a[j][i - 1], a[j][ii + 1]));
			}
		}
	}
	int tor[n][n][m];
	memset(tor, -1, sizeof tor);
	for (int i = 1; i < n - 1; i++) {
		for (int ii = i; ii < n - 1; ii++) {
			for (int j = m - 2; j >= 1; j--) {
				if (good[i][ii][j]) tor[i][ii][j] = j;
				if (good[i][ii][j]) tor[i][ii][j] = max(tor[i][ii][j], tor[i][ii][j + 1]);
			}
		}
	}
	int toc[m][m][n];
	memset(toc, -1, sizeof toc);
	for (int i = 1; i < m - 1; i++) {
		for (int ii = i; ii < m - 1; ii++) {
			for (int j = n - 2; j >= 1; j--) {
				if (gg[i][ii][j]) toc[i][ii][j] = j;
				if (gg[i][ii][j]) toc[i][ii][j] = max(toc[i][ii][j], toc[i][ii][j + 1]);
			}
		}
	}
	int total = 0;
	for (int i = 1; i < n - 1; i++) {
		for (int j = 1; j < m - 1; j++) {
			vector<pair<int, int>> a, b;
			for (int ii = i; ii < n - 1; ii++) {
				if (tor[i][ii][j] != -1) a.push_back({ii, tor[i][ii][j]});
			}
			for (int ii = j; ii < m - 1; ii++) {
				if (toc[j][ii][i] != -1) b.push_back({toc[j][ii][i], ii});
			}
			sort(a.begin(), a.end());
			sort(b.begin(), b.end());
			int p1 = 0;
			int sa = a.size(), sb = b.size();
			total = 0;
			for (int cur = 0; cur < sb; cur++) {
				while (p1 < sa && a[p1].first <= b[cur].first) {
					upd(a[p1++].second, 1);
					total++;
				}
				ans += total - sum(b[cur].second - 1);
			}
			for (int cur = 0; cur < p1; cur++) upd(a[cur].second, -1);
		}
	}
	return ans;
}

• 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