結果
問題 |
No.1864 Shortest Paths Counting
|
ユーザー |
|
提出日時 | 2022-03-15 23:19:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 357 ms / 2,000 ms |
コード長 | 3,363 bytes |
コンパイル時間 | 2,082 ms |
コンパイル使用メモリ | 142,552 KB |
最終ジャッジ日時 | 2025-01-28 09:48:17 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#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'; }