Submission #570484

#	Time	Username	Problem	Language	Result	Execution time	Memory
570484		Virv	Ideal city (IOI12_city)	C++17	100 / 100	65 ms	8096 KiB

city

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <tuple>
#include <vector>

using u32 = uint32_t;
using u64 = uint64_t;

using pii  = std::pair<u32, u32>;
using tiii = std::tuple<u32, u32, u32>;

constexpr u32 mod = 1e9;

static int foo(int n, int x[], int y[]) {
	std::vector<pii> p(n);
	for (int i = 0; i < n; ++i) p[i] = {x[i], y[i]};
	sort(p.begin(), p.end());

	std::vector<char> f(n, false);

	std::function<tiii(u32)> const rec = [&](u32 i) -> tiii {
		// std::cerr << "OPEN\t" << p[i].first << ' ' << p[i].second << '\n';

		u32 j = i + 1;
		while (i > 0 && p[i - 1].first == p[i].first && p[i - 1].second + 1 == p[i].second) --i;
		while (j < n && p[j - 1].first == p[j].first && p[j - 1].second + 1 == p[j].second) ++j;
		for (u32 k = i; k < j; ++k) {
			assert(f[k] == false);
			f[k] = true;
		}

		std::vector<tiii> v;
		for (auto it =
				 lower_bound(p.begin(), p.end(), pii{p[i].first - 1, p[i].second}) - p.begin();
			 it < n && p[it] <= pii{p[j - 1].first - 1, p[j - 1].second}; ++it) {
			if (f[it]) continue;
			v.push_back(rec(it));
		}

		for (auto it =
				 lower_bound(p.begin(), p.end(), pii{p[i].first + 1, p[i].second}) - p.begin();
			 it < n && p[it] <= pii{p[j - 1].first + 1, p[j - 1].second}; ++it) {
			if (f[it]) continue;
			v.push_back(rec(it));
		}

		u32 close = 0;
		u32 open  = 0;
		u32 m	  = j - i;

		for (auto [b, o, c] : v) {
			o += b;
			close = (close + c + (u64)b * open + (u64)m * o) % mod;
			open  = (open + o) % mod;
			m += b;
			// std::cerr << "INT\t" << m << ' ' << open << ' ' << close << '\n';
		}

		// std::cerr << "CLOSE\t" << p[i].first << ' ' << p[i].second << '\t' << m << ' ' << open << ' ' << close << '\n';

		return {m, open, close};
	};

	return n == 0 ? 0 : std::get<2>(rec(0));
}

int DistanceSum(int n, int x[], int y[]) {
	return (foo(n, x, y) + foo(n, y, x)) % mod;
}

Compilation message (stderr)

city.cpp: In lambda function:
city.cpp:28:12: warning: comparison of integer expressions of different signedness: 'u32' {aka 'unsigned int'} and 'int' [-Wsign-compare]
   28 |   while (j < n && p[j - 1].first == p[j].first && p[j - 1].second + 1 == p[j].second) ++j;
      |          ~~^~~

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45