Submission #1304882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304882		madamadam3	Rectangles (IOI19_rect)	C++20	25 / 100	5099 ms	247032 KiB

rect

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

using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;

struct SegTree {
	int n; vector<int> arr, st;
	SegTree() {};
	SegTree(int N, vector<int> &Arr) {
		n = N; arr = Arr; st.assign(4*n, INT_MIN);
		build(0, 0, n);
	}

	int build(int i, int l, int r) {
		if (l+1 == r) return st[i] = arr[l];
		int m = l + (r - l) / 2;
		return st[i] = max(build(2*i+1, l, m), build(2*i+2, m, r));
	}

	int query(int i, int l, int r, int ql, int qr) {
		if (qr <= l || r <= ql) return INT_MIN;
		if (ql <= l && r <= qr) return st[i];

		int m = l + (r - l) / 2;
		return max(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr));
	}
};

using pc = pair<pair<int, int>, pair<int, int>>;
ll count_rectangles(vvi a) {
	int n = a.size(), m = a[0].size();
	vvi b(m, vi(n, INT_MIN)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) b[j][i] = a[i][j];

	vector<SegTree> rows(n), cols(m);
	for (int i = 0; i < n; i++) rows[i] = SegTree(m, a[i]);
	for (int i = 0; i < m; i++) cols[i] = SegTree(n, b[i]);

	ll ans = 0;
	vvi gr(m, vi(m, 0)), gc(n, vi(n, 0));
	set<pc> coords;

	for (int x = 1; x < n-1; x++) {
		vvi ng(m, vi(m, 0));

		for (int y1 = 1; y1 < m-1; y1++) {
			for (int y2 = y1; y2 < m-1; y2++) {
				if (rows[x].query(0, 0, m, y1, y2+1) >= min(a[x][y1-1], a[x][y2+1])) continue;
				ng[y1][y2] = gr[y1][y2] + 1;
				for (int i = x - ng[y1][y2] + 1; i <= x; i++) {
					coords.insert({{i, y1}, {x, y2}});
					// cout << "The rectangle (" << i << ", " << y1 << "), (" << x << ", " << y2 << ") is good.\n";
				}
			}
		}

		swap(gr, ng);
	}

	for (int y = 1; y < m-1; y++) {
		vvi ng(n, vi(n, 0));

		for (int x1 = 1; x1 < n-1; x1++) {
			for (int x2 = x1; x2 < n-1; x2++) {
				if (cols[y].query(0, 0, n, x1, x2+1) >= min(a[x1-1][y], a[x2+1][y])) continue;
				ng[x1][x2] = gc[x1][x2] + 1;
				for (int i = y - ng[x1][x2] + 1; i <= y; i++) {
					if (coords.count({{x1, i}, {x2, y}})) {
						// cout << "The rectangle (" << x1 << ", " << i << "), (" << x2 << ", " << y << ") is good.\n";
						ans++;
					}
				}
			}
		}

		swap(gc, ng);
	}
	
	return ans;
}

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