제출 #1304876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304876		madamadam3	Rectangles (IOI19_rect)	C++20	25 / 100	5100 ms	146484 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));
	}
};

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;
	for (int x1 = 1; x1 < n-1; x1++) {
		for (int x2 = x1; x2 < n-1; x2++) {
			for (int y1 = 1; y1 < m-1; y1++) {
				for (int y2 = y1; y2 < m-1; y2++) {
					bool good = true;
					for (int x3 = x1; x3 <= x2; x3++) {
						for (int y3 = y1; y3 <= y2; y3++) {
							good = good && a[x3][y3] < min({a[x3][y1-1], a[x3][y2+1], a[x1-1][y3], a[x2+1][y3]});
						}
					}
					if (good) ans++;
				}
			}
		}
	}

	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