結果

問題 No.1864 Shortest Paths Counting
ユーザー yudedakoyudedako
提出日時 2022-03-15 23:19:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 273 ms / 2,000 ms
コード長 3,363 bytes
コンパイル時間 1,679 ms
コンパイル使用メモリ 148,536 KB
実行使用メモリ 13,572 KB
最終ジャッジ日時 2023-10-23 22:24:42
合計ジャッジ時間 7,794 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 271 ms
13,572 KB
testcase_10 AC 271 ms
13,572 KB
testcase_11 AC 269 ms
13,572 KB
testcase_12 AC 271 ms
13,572 KB
testcase_13 AC 271 ms
13,572 KB
testcase_14 AC 270 ms
13,572 KB
testcase_15 AC 271 ms
13,572 KB
testcase_16 AC 270 ms
13,572 KB
testcase_17 AC 271 ms
13,572 KB
testcase_18 AC 270 ms
13,572 KB
testcase_19 AC 273 ms
13,572 KB
testcase_20 AC 270 ms
13,572 KB
testcase_21 AC 271 ms
13,572 KB
testcase_22 AC 271 ms
13,572 KB
testcase_23 AC 270 ms
13,572 KB
testcase_24 AC 2 ms
4,348 KB
testcase_25 AC 248 ms
13,572 KB
testcase_26 AC 175 ms
13,572 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <queue>
#include <string>
#include <random>
#include <array>
#include <climits>
#include <map>
#include <cassert>
#include <stack>
#include <iomanip>
#include <cfloat>
#include <bitset>
#include <fstream>
#include <chrono>

constexpr int MOD = 998244353;

class Mint {
	long long int value;
	long long int inverse() const {
		long long int x = value, y = MOD, a = 1, b = 0, c = 0, d = 1;
		while (y != 0) {
			const auto q = x / y;
			const auto e = a - c * q;
			const auto f = b - d * q;
			a = c;
			b = d;
			c = e;
			d = f;
			x = y;
			y = c * value + d * MOD;
		}
		return (x == 1) ? a % MOD : -a % MOD;
	}
public:
	Mint() : value{0} {};
	Mint(const int value) : value{ value } {};
	Mint(const long long int value) :value{ value % MOD } {};
	Mint operator+(const Mint right) const {
		return (value + right.value);
	}
	Mint operator+=(const Mint right) {
		return *this = (*this + right);
	}
	Mint operator-(const Mint right) const {
		return (value - right.value);
	}
	Mint operator*(const Mint right) const {
		return (value * right.value);
	}
	Mint operator/(const Mint right) const {
		return (value * right.inverse());
	}
	long long int val() const {
		return (value % MOD + MOD) % MOD;
	}
};

class Bit {
	std::vector<Mint> vec;
public:
	explicit Bit(const int size) : vec(size) {};
	Mint operator[](int position) const {
		Mint result;
		while (0 <= position) {
			result += vec[position];
			position -= ~position & (position + 1);
		}
		return result;
	}
	void add(int position, const Mint value) {
		while (position < vec.size()) {
			vec[position] += value;
			position += ~position & (position + 1);
		}
	}
};
using Point = std::pair<long long int, long long int>;
std::vector<Point> normalize(const std::vector<Point>& points) {
	std::vector<Point> result; result.reserve(points.size());
	const auto [sx, sy] = points.front();
	const auto [gx, gy] = points.back();
	const auto dx = (sx + sy <= gx + gy) ? 1 : -1;
	const auto dy = (sy - sx <= gy - gx) ? 1 : -1;
	for (auto i = 0; i < points.size(); ++i) {
		const auto [x, y] = points[i];
		result.emplace_back((x + y - sx - sy) * dx, (y - x - sy + sx) * dy);
	}
	return result;
}

int main() {
	int n; std::cin >> n;
	std::vector<Point> points(n);
	for (auto& [x, y] : points) {
		std::cin >> x >> y;
	}
	const auto normalized = normalize(points);
	std::vector<long long int> all_y;
	for (const auto [_, y] : normalized) {
		all_y.push_back(y);
	}
	std::sort(all_y.begin(), all_y.end());
	all_y.erase(std::unique(all_y.begin(), all_y.end()), all_y.end());
	Bit bit(all_y.size());
	std::vector<int> indices(n); std::iota(indices.begin(), indices.end(), 0);
	std::sort(indices.begin(), indices.end(), [&normalized](const int i, const int j) {return normalized[i].first == normalized[j].first ? normalized[i].second < normalized[j].second : normalized[i].first < normalized[j].first; });

	Mint result; 
	for (const auto i : indices) {
		const auto y = std::distance(all_y.begin(), std::lower_bound(all_y.begin(), all_y.end(), normalized[i].second));
		if (i == 0) {
			bit.add(y, 1);
		}
		else if (i == n - 1) {
			result = bit[y];
		}
		else {
			const auto count = bit[y];
			bit.add(y, count);
		}
	}
	std::cout << result.val() << '\n';
}
0