oj.uz

Submission #570484

# Submission time Handle Problem Language Result Execution time Memory
570484 2022-05-30T07:36:59 Z Virv Ideal city (IOI12_city) C++17
100 / 100
 65 ms 8096 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 2 ms 316 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 312 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 3 ms 340 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 852 KB Output is correct
2 Correct 8 ms 948 KB Output is correct
3 Correct 19 ms 1620 KB Output is correct
4 Correct 20 ms 1620 KB Output is correct
5 Correct 38 ms 2896 KB Output is correct
6 Correct 40 ms 2984 KB Output is correct
7 Correct 40 ms 3344 KB Output is correct
8 Correct 39 ms 2776 KB Output is correct
9 Correct 39 ms 3236 KB Output is correct
10 Correct 42 ms 8096 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 948 KB Output is correct
2 Correct 11 ms 1108 KB Output is correct
3 Correct 36 ms 1732 KB Output is correct
4 Correct 31 ms 1876 KB Output is correct
5 Correct 62 ms 3232 KB Output is correct
6 Correct 50 ms 3348 KB Output is correct
7 Correct 65 ms 3428 KB Output is correct
8 Correct 51 ms 3224 KB Output is correct
9 Correct 49 ms 2828 KB Output is correct
10 Correct 42 ms 2896 KB Output is correct