Submission #1370287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370287		kawhiet	Rectangles (IOI19_rect)	C++20	Compilation error	0 ms	0 KiB

rect

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

struct SparseTable {
	int n;
	vector<vector<int>> t;
	vector<int> lg;

	void init(vector<int> a) {
		n = a.size();
		lg.resize(n + 1);
		t.resize(n, vector<int>(10));
		build(a);
	}

	void build(vector<int> a) {
		for (int i = 2; i <= n; i++) {
			lg[i] = lg[i / 2] + 1;
		}
		for (int i = 0; i < n; i++) {
			t[i][0] = a[i];
		}
		for (int j = 1; j < 10; j++) {
			for (int i = 0; i + (1 << j) <= n; i++) {
				t[i][j] = max(t[i][j - 1], t[i + (1 << (j - 1))][j - 1]);
			}
		}
	}

	int get(int l, int r) {
		int x = lg[r - l + 1];
		return max(t[l][x], t[r - (1 << x) + 1][x]);
	}
};

long long count_rectangles(vector<vector<int>> a) {
	int n = a.size();
	int m = a[0].size();
	vector<SparseTable> r(n), c(m);
	for (int i = 0; i < n; i++) {
		r[i].init(a[i]);
	}
	for (int i = 0; i < m; i++) {
		vector<int> x;
		for (int j = 0; j < n; j++) {
			x.push_back(a[j][i]);
		}
		c[i].init(x);
	}
	vector<array<int, 2>> top_left, bottom_right;
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			if (a[i][j] < max(a[i - 1][j], a[i][j - 1])) {
				top_left.push_back({i, j});
			}
		}
	}
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < m - 1; j++) {
			if (a[i][j] < max(a[i + 1][j], a[i][j + 1])) {
				bottom_right.push_back({i, j});
			}
		}
	}
	long long ans = 0;
	for (auto [r1, c1] : top_left) {
		for (auto [r2, c2] : bottom_right) {
			if (r2 < r1 || c2 < c1) continue;
			bool ok = true;
			for (int i = r1; i <= r2; i++) {
				if (r[i].get(c1, c2) >= min(a[i][c1 - 1], a[i][c2 + 1])) {
					ok = false;
					break;
				}
			}
			if (!ok) continue;
			for (int i = c1; i <= c2; i++) {
				if (c[i].get(r1, r2) >= min(a[r1 - 1][i], a[r2 + 1][i])) {
					ok = false;
					break;
				}
			}
			if (ok) {
				ans++;
			}
		}
	}
	return ans;
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	for (int i = 0; i < n; i++)	{
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	long long result = count_rectangles(a);
	printf("%lld\n", result);
	return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccA3HeiN.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccW0gqlm.o:rect.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status