結果

問題 No.1864 Shortest Paths Counting
ユーザー yudedako
提出日時 2022-03-15 23:16:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,354 bytes
コンパイル時間 1,636 ms
コンパイル使用メモリ 142,104 KB
最終ジャッジ日時 2025-01-28 09:48:06
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21 WA * 2
権限があれば一括ダウンロードができます

ソースコード

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);
        }
    }
};
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';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0