#746178 (C++17) No.1864 Shortest Paths Counting

• 問題: No.1864 Shortest Paths Counting
• ユーザー: yudedako
• 提出日時: 2022-03-15 23:16:55
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 3,354 bytes
• コンパイル時間: 1,966 ms
• コンパイル使用メモリ: 147,704 KB
• 実行使用メモリ: 9,736 KB
• 最終ジャッジ日時: 2024-09-22 15:39:38
• 合計ジャッジ時間: 9,131 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	1 ms; 6,940 KB
testcase_02	AC	2 ms; 6,944 KB
testcase_03	AC	2 ms; 6,944 KB
testcase_04	AC	2 ms; 6,940 KB
testcase_05	AC	2 ms; 6,944 KB
testcase_06	AC	2 ms; 6,940 KB
testcase_07	AC	2 ms; 6,940 KB
testcase_08	AC	2 ms; 6,944 KB
testcase_09	AC	271 ms; 9,608 KB
testcase_10	AC	270 ms; 9,608 KB
testcase_11	AC	273 ms; 9,608 KB
testcase_12	AC	267 ms; 9,604 KB
testcase_13	AC	269 ms; 9,604 KB
testcase_14	AC	274 ms; 9,732 KB
testcase_15	AC	266 ms; 9,608 KB
testcase_16	AC	271 ms; 9,732 KB
testcase_17	AC	269 ms; 9,736 KB
testcase_18	AC	271 ms; 9,604 KB
testcase_19	AC	271 ms; 9,732 KB
testcase_20	WA	-
testcase_21	AC	271 ms; 9,596 KB
testcase_22	AC	268 ms; 9,604 KB
testcase_23	AC	270 ms; 9,600 KB
testcase_24	WA	-
testcase_25	AC	248 ms; 9,608 KB
testcase_26	AC	171 ms; 9,604 KB

ソースコード

#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);
		}
	}
};
std::vector<std::pair<int, int>> normalize(const std::vector<std::pair<int, int>>& points) {
	std::vector<std::pair<int, int>> 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<std::pair<int, int>> points(n);
	for (auto& [x, y] : points) {
		std::cin >> x >> y;
	}
	const auto normalized = normalize(points);
	std::vector<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';
}