Submission #420580

#	Time	Username	Problem	Language	Result	Execution time	Memory
420580		QCFium	Rectangles (IOI19_rect)	C++14	27 / 100	5061 ms	694392 KiB

rect

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

struct SegTree {
	int n;
	std::vector<int> data;
	SegTree (int n_) {
		for (n = 1; n < n_; n <<= 1);
		data.resize(n << 1);
	}
	void add(int i, int val) {
		for (i += n; i; i >>= 1) data[i] += val;
	}
	int sum(int l, int r) {
		int res = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (r & 1) res += data[--r];
			if (l & 1) res += data[l++];
		}
		return res;
	}
};

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size();
	int m = a[0].size();
	assert(n <= 700 && m <= 700);
	
	std::vector<std::vector<std::vector<int> > > r1(n, std::vector<std::vector<int> > (m));
	for (int i = 1; i + 1 < m; i++) {
		bool ok[n][m];
		std::vector<int> max(n, -1);
		for (int j = i + 1; j < m; j++) {
			for (int k = 1; k + 1 < n; k++) {
				max[k] = std::max(max[k], a[k][j - 1]);
				ok[k][j] = max[k] < a[k][j] && max[k] < a[k][i - 1];
			}
		}
		std::vector<int> cur(m, 0);
		for (int j = n - 2; j >= 1; j--) {
			for (int k = i + 1; k < m; k++) {
				if (ok[j][k]) cur[k]++;
				else cur[k] = 0;
			}
			r1[j][i] = std::vector<int>(cur.begin() + i, cur.end());
			/*
			std::cerr << "r1 " << j << " " << i << " : ";
			for (auto k : r1[j][i]) std::cerr << k << " ";
			std::cerr << std::endl;*/
		}
	}
	
	
	int64_t res = 0;
	auto calc = [&] (std::vector<int> r0, std::vector<int> r1) {
		std::vector<int> all[m];
		for (int k = 1; k < (int) r0.size(); k++) all[r0[k]].push_back(k);
		
		SegTree tree(n);
		for (int k = 1; k < m; k++) {
			if (k < (int) r1.size()) tree.add(r1[k], 1);
			for (auto l : all[k]) {
				res += tree.sum(l, tree.n);
				
				/*
				int t = tree.sum(l, tree.n);
				if (t) std::cerr << i << " " << j << " " << k << " " << l << " " << t << std::endl;*/
			}
		}
	};
	
	for (int i = 1; i + 1 < n; i++) {
		bool ok[n][m];
		std::vector<int> max(m, -1);
		for (int j = i + 1; j < n; j++) {
			for (int k = 1; k + 1 < m; k++) {
				max[k] = std::max(max[k], a[j - 1][k]);
				ok[j][k] = max[k] < a[j][k] && max[k] < a[i - 1][k];
			}
		}
		std::vector<int> cur(n, 0);
		for (int j = m - 2; j >= 1; j--) {
			for (int k = i + 1; k < n; k++) {
				if (ok[k][j]) cur[k]++;
				else cur[k] = 0;
			}
			calc(std::vector<int>(cur.begin() + i, cur.end()), r1[i][j]);
		}
	}
	
	return res;
}

#ifdef LOCAL
int main() {
	int n = ri();
	int m = ri();
	std::vector<std::vector<int> > a(n, std::vector<int>(m));
	for (auto &i : a) for (auto &j : i) j = ri();
	
	printf("%lld\n", count_rectangles(a));
	
	return 0;
}
#endif

Compilation message (stderr)

rect.cpp: In function 'int ri()':
rect.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~

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