結果

問題 No.2336 Do you like typical problems?
ユーザー merom686merom686
提出日時 2023-06-03 00:41:33
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 183 ms / 2,000 ms
コード長 2,657 bytes
コンパイル時間 2,570 ms
コンパイル使用メモリ 218,032 KB
実行使用メモリ 11,452 KB
最終ジャッジ日時 2023-08-28 07:08:00
合計ジャッジ時間 5,397 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 3 ms
4,376 KB
testcase_10 AC 3 ms
4,380 KB
testcase_11 AC 3 ms
4,380 KB
testcase_12 AC 3 ms
4,376 KB
testcase_13 AC 183 ms
11,452 KB
testcase_14 AC 183 ms
11,372 KB
testcase_15 AC 182 ms
11,364 KB
testcase_16 AC 180 ms
11,416 KB
testcase_17 AC 179 ms
11,444 KB
testcase_18 AC 98 ms
11,364 KB
testcase_19 AC 110 ms
11,364 KB
testcase_20 AC 126 ms
11,360 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using ll = long long;
using namespace std;

template <class T>
struct SegmentTree {
    SegmentTree(int n) : n(n) {
        for (m = 2; m < n; m *= 2);
        t = vector<T>(m + n + n % 2);
    }
    T &operator[](int i) {
        return t[m + i];
    }
    const T &root() const {
        return t[1];
    }
    void build() {
        for (int i = (n - 1 + m) / 2; i > 0; i--) t[i] = t[i * 2] * t[i * 2 + 1];
    }
    void update(int i, const T &o) {
        for (t[i += m] = o; i /= 2, i > 0;) t[i] = t[i * 2] * t[i * 2 + 1];
    }
    T query(int l, int r) {
        T o0, o1;
        for (l += m, r += m; l < r; l /= 2, r /= 2) {
            if (l & 1) o0 = o0 * t[l++];
            if (r & 1) o1 = t[--r] * o1;
        }
        return o0 * o1;
    }
    vector<T> t;
    int n, m;
};
struct Sum {
    Sum() : x(0), y(0) {}
    Sum(mint x, mint y) : x(x), y(y) {}
    Sum operator*(const Sum &o) const {
        return { x + o.x, y + o.y };
    }
    mint x, y;
};

struct P {
    bool operator<(const P &p) const {
        return b < p.b;
    }
    int b, c;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<P> p(n);
    for (int i = 0; i < n; i++) {
        int b, c;
        cin >> b >> c;
        b--;

        p[i] = { b, c };
    }
    sort(p.begin(), p.end());

    vector<mint> y(n);
    for (int i = 0; i < n; i++) {
        y[i] = mint(p[i].c - p[i].b).inv();
    }

    vector<int> u(n);
    for (int i = 0; i < n; i++) {
        u[i] = i;
    }
    sort(u.begin(), u.end(), [&](const int &i0, const int &i1) {
        return p[i0].c < p[i1].c;
    });
    SegmentTree<Sum> st(n);

    vector<mint> sb(n + 1, 0), sy(n + 1, 0);
    for (int i = 0; i < n; i++) {
        sb[i + 1] = sb[i] + y[i] * p[i].b;
    }
    for (int i = 0; i < n; i++) {
        sy[i + 1] = sy[i] + y[i];
    }

    mint x = 0;
    for (int j = 0; j < n; j++) {
        int i = u[j];
        int i0 = i + 1;
        int i1 = lower_bound(p.begin(), p.end(), P{ p[i].c, 0 }) - p.begin();
        auto o = st.query(i0, i1);
        mint t = 0;
        t += o.x;
        t += p[i].c * (sy[i1] - sy[i0] - o.y);
        t -= sb[i1] - sb[i0];
        st.update(i, { (mint)p[i].c * y[i], y[i] });
        //for (int j = i0; j < i1; j++) {
        //    int l = min(p[i].c, p[j].c) - p[j].b;
        //    t += (mint)l / (p[j].c - p[j].b);
        //}
        x += t * y[i];
    }

    x = (mint)n * (n - 1) / 2 - x;
    x /= 2;
    for (int i = 1; i <= n; i++) {
        x *= i;
    }
    cout << x.val() << endl;

    return 0;
}
0