Submission #420734

#	Time	Username	Problem	Language	Result	Execution time	Memory
420734		QCFium	Rectangles (IOI19_rect)	C++14	0 / 100	1 ms	460 KiB

rect

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>

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

struct BIT {
	int n;
	std::vector<int> data;
	int all_sum = 0;
	BIT (int n) : n(n), data(n + 1) {}
	void add(int i, int val) {
		for (i++; i <= n; i += i & -i) data[i] += val;
		all_sum += val;
	}
	int sum_left(int r) {
		int res = 0;
		for (; r; r -= r & -r) res += data[r];
		return res;
	}
	int sum_right(int l) { return all_sum - sum_left(l); }
};
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_rectangles2(std::vector<std::vector<int> > a) {
	int n = a.size();
	int m = a[0].size();
	
	int64_t res = 0;
	if (n == 3) {
		auto solve_sub = [&] (std::vector<int> a) {
			for (auto i : a) std::cerr << i << " ";
			std::cerr << std::endl;
			int n = a.size();
			std::deque<int> all;
			for (int i = n - 1; i >= 0; i--) {
				if (i <= n - 3) {
					int tmp = std::lower_bound(all.begin(), all.end(), a[i]) - all.begin();
					tmp = std::min(tmp, (int) all.size() - 1);
					res += std::max(0, tmp);
				}
				while (all.size() && all.front() <= a[i]) all.pop_front();
				all.push_front(a[i]);
			}
		};
		std::vector<int> all{a[1][0]};
		for (int i = 1; i < m; i++) {
			bool ok = i != m - 1 && a[1][i] < a[0][i] && a[1][i] < a[2][i];
			if (!ok) {
				if (all.size() > 1) {
					all.push_back(a[1][i]);
					solve_sub(all);
				}
				all = {a[1][i]};
			} else all.push_back(a[1][i]);
		}
	} else assert(0);
	return res;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size();
	int m = a[0].size();
	
	int64_t res = 0;
	if (n == 3) {
		auto solve_sub = [&] (std::vector<int> a) {
			int n = a.size();
			std::deque<int> all;
			for (int i = n - 1; i >= 0; i--) {
				if (i <= n - 3) {
					int tmp = std::lower_bound(all.begin(), all.end(), a[i]) - all.begin();
					tmp = std::min(tmp, (int) all.size() - 1);
					res += std::max(0, tmp);
				}
				while (all.size() && all.front() <= a[i]) all.pop_front();
				all.push_front(a[i]);
			}
		};
		std::vector<int> all{a[1][0]};
		for (int i = 1; i < m; i++) {
			bool ok = i != m - 1 && a[1][i] < a[0][i] && a[1][i] < a[2][i];
			if (!ok) {
				if (all.size() > 1) {
					all.push_back(a[1][i]);
					solve_sub(all);
				}
				all = {a[1][i]};
			} else all.push_back(a[1][i]);
		}
	} else if (n <= 700 && m <= 700) {
		assert(0);
		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++) {
			std::vector<int> cur(m - i, 0);
			for (int k = n - 2; k >= 1; k--) {
				int max = -1;
				for (int j = i + 1; j < m; j++) {
					max = std::max(max, a[k][j - 1]);
					if (max < a[k][j] && max < a[k][i - 1]) cur[j - i]++;
					else cur[j - i] = 0;
				}
				r1[k][i] = cur;
			}
		}
		
		auto calc = [&] (const std::vector<int> &r0, const std::vector<int> &r1) {
			std::vector<int> all[r0.size()];
			for (int k = 1; k < (int) r1.size(); k++) if (r1[k]) all[r1[k]].push_back(k);
			BIT tree(r1.size());
			for (int k = 1; k < (int) r0.size(); k++) {
				tree.add(r0[k], 1);
				for (auto l : all[k]) res += tree.sum_right(l);
			}
		};
		
		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 - i, 0);
			for (int j = m - 2; j >= 1; j--) {
				for (int k = i + 1; k < n; k++) {
					if (ok[k][j]) cur[k - i]++;
					else cur[k - i] = 0;
				}
				calc(cur, r1[i][j]);
			}
		}
	} else assert(0);
	return res;
}

std::random_device rnd_dev;
std::mt19937 rnd(rnd_dev() ^ clock());
int rnd_int(int l, int r) { return std::uniform_int_distribution<>(l, r)(rnd); }

bool check() {
	int n = 3;
	int m = rnd_int(1, 5);
	std::vector<std::vector<int> > a(n, std::vector<int>(m));
	for (auto &i : a) for (auto &j : i) j = rnd_int(1, 20);
	
	auto r0 = count_rectangles2(a);
	auto r1 = count_rectangles(a);
	if (r0 != r1) {
		std::cerr << n << " " << m << std::endl;
		for (auto i : a) {
			for (auto j : i) std::cerr << j << " ";
			std::cerr << std::endl;
		}
		std::cerr << "r0/r1 : " << r0 << "/" << r1 << std::endl;
		return false;
	}
	return true;
}

#ifdef LOCAL
int main() {
	for (int i = 0; i < 10000; i++) if (!check()) {
		std::cerr << "failed at " << i << std::endl;
		return 0;
	}
	return 0;
	
	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_rectangles2(a));
	
	{
		int n, m;
		n = m = 700;
		std::vector<std::vector<int> > a(n, std::vector<int>(m));
		for (auto &i : a) for (auto &j : i) j = rnd_int(1, 1000000);
		
		clock_t r0 = clock();
		int res = count_rectangles(a);
		clock_t r1 = clock();
		printf("%d\n", res);
		printf("took %f ms\n", (double) (r1 - r0) * 1000 / CLOCKS_PER_SEC);
	}
	
	return 0;
}
#endif

Compilation message (stderr)

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

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