結果
問題 |
No.2336 Do you like typical problems?
|
ユーザー |
|
提出日時 | 2023-06-03 00:31:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,998 ms / 2,000 ms |
コード長 | 2,112 bytes |
コンパイル時間 | 4,254 ms |
コンパイル使用メモリ | 243,716 KB |
実行使用メモリ | 50,396 KB |
最終ジャッジ日時 | 2024-12-29 01:40:28 |
合計ジャッジ時間 | 17,434 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; using S = array<mint, 3>; using F = array<mint, 3>; S op(S lhs, S rhs){ lhs[0] += rhs[0]; lhs[1] += rhs[1]; lhs[2] += rhs[2]; return lhs; } S e(){ S a{}; return a; } S mapping(F f, S x){ x[0] += f[0] * x[1] + f[1] * x[1] - f[2] * x[2]; return x; } F composition(F f, F g){ f[0] += g[0]; f[1] += g[1]; f[2] += g[2]; return f; } array<mint, 3> ida = {0, 0, 0}, idb = {1, 0, 0}; F id(){return ida;} int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<pair<int,int>> a(n), b(n); vector<int> ca(2 * n); vector<mint> div(n); for(int i = 0; i < n; i++){ int l, r; cin >> l >> r; a[i] = make_pair(l, r); ca[2 * i] = l; ca[2 * i + 1] = r + 1; } sort(ca.begin(), ca.end()); ca.erase(unique(ca.begin(), ca.end()), ca.end()); vector<S> tmp(ca.size()); mint div2 = mint(1) / 2; for(int i = 0; i + 1 < ca.size(); i++){ tmp[i][1] = ca[i + 1] - ca[i]; tmp[i][2] = ((ll)(ca[i + 1]) * (ca[i + 1] - 1) - (ll)(ca[i]) * (ca[i] - 1)) / 2; } lazy_segtree<S, op, e, F, mapping, composition, id> seg(tmp); mint ans; for(int i = 0; i < n; i++){ int l, r; tie(l, r) = a[i]; div[i] = mint(1) / (r - l + 1); l = lower_bound(ca.begin(), ca.end(), l) - ca.begin(); r = upper_bound(ca.begin(), ca.end(), r) - ca.begin(); ans += seg.prod(l, r)[0] * div[i]; seg.apply(l, r, {0, div[i] * a[i].second, div[i]}); seg.apply(0, l, idb); b[i] = make_pair(l, r); } seg = lazy_segtree<S, op, e, F, mapping, composition, id>(tmp); for(int i = n - 1; i >= 0; i--){ int l, r; tie(l, r) = b[i]; ans += seg.prod(l, r)[0] * div[i]; seg.apply(l, r, {0, div[i] * a[i].second, div[i]}); seg.apply(0, l, idb); } for(int i = 3; i <= n; i++) ans *= i; cout << ans.val() << '\n'; }