結果
問題 | No.1294 マウンテン数列 |
ユーザー |
![]() |
提出日時 | 2020-11-20 23:03:27 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,974 ms / 2,000 ms |
コード長 | 4,242 bytes |
コンパイル時間 | 7,659 ms |
コンパイル使用メモリ | 268,560 KB |
最終ジャッジ日時 | 2025-01-16 03:05:13 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <bits/stdc++.h>using namespace std;// 0-indexedtemplate <class T>struct SegmentTree {// a,b,c: T, e:T(unit)// abc = (ab)c = a(bc)// ae = ea = atypedef function<T(T, T)> F;int n;F f;T unit;vector<T> dat;SegmentTree(){};SegmentTree(int newn, F f, T t) : f(f), unit(t) { init(newn); }SegmentTree(const vector<T> &v, F f, T t) : f(f), unit(t) {int _n = v.size();init(v.size());for (int i = 0; i < _n; ++i) dat[n + i] = v[i];for (int i = n - 1; i; --i) dat[i] = f(dat[i << 1], dat[(i << 1) | 1]);}void init(int newn) {n = 1;while (n < newn) n <<= 1;dat.assign(n << 1, unit);}// "go up" processvoid update(int k, T newdata) {dat[k += n] = newdata;while (k >>= 1) {dat[k] = f(dat[(k << 1) | 0], dat[(k << 1) | 1]);}}// [a,b)T query(int a, int b) {T vl = unit, vr = unit;for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {if (l & 1) vl = f(vl, dat[l++]);if (r & 1) vr = f(dat[--r], vr);}return f(vl, vr);}};template <int mod = (int)(998244353)>struct ModInt {int x;constexpr ModInt() : x(0) {}constexpr ModInt(int64_t y): x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}constexpr ModInt &operator+=(const ModInt &p) noexcept {if ((x += p.x) >= mod) x -= mod;return *this;}constexpr ModInt &operator-=(const ModInt &p) noexcept {if ((x += mod - p.x) >= mod) x -= mod;return *this;}constexpr ModInt &operator*=(const ModInt &p) noexcept {x = (int)(1LL * x * p.x % mod);return *this;}constexpr ModInt &operator/=(const ModInt &p) noexcept {*this *= p.inverse();return *this;}constexpr ModInt operator-() const { return ModInt(-x); }constexpr ModInt operator+(const ModInt &p) const noexcept {return ModInt(*this) += p;}constexpr ModInt operator-(const ModInt &p) const noexcept {return ModInt(*this) -= p;}constexpr ModInt operator*(const ModInt &p) const noexcept {return ModInt(*this) *= p;}constexpr ModInt operator/(const ModInt &p) const noexcept {return ModInt(*this) /= p;}constexpr bool operator==(const ModInt &p) const noexcept { return x == p.x; }constexpr bool operator!=(const ModInt &p) const noexcept { return x != p.x; }constexpr ModInt inverse() const noexcept {int a = x, b = mod, u = 1, v = 0, t = 0;while (b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return ModInt(u);}constexpr ModInt pow(int64_t n) const {ModInt res(1), mul(x);while (n) {if (n & 1) res *= mul;mul *= mul;n >>= 1;}return res;}friend constexpr ostream &operator<<(ostream &os, const ModInt &p) noexcept {return os << p.x;}friend constexpr istream &operator>>(istream &is, ModInt &a) noexcept {int64_t t = 0;is >> t;a = ModInt<mod>(t);return (is);}constexpr int get_mod() { return mod; }};using mint = ModInt<>;int n;vector<int> a;vector<mint> cnt;mint solve();int main() {cin >> n;a.resize(n);for (auto &p : a) cin >> p;cout << solve() << endl;return 0;}mint solve() {if (n == 2) return 2 * (a[1] - a[0]);mint res = 0;cnt.assign(2501, 0);a.push_back(a[n - 1]);for (int x = 1; x <= 2500; ++x) {vector<int> memo(n, 0);for (int i = 0; i < n; ++i) {int fi = i;memo[i] = i;while (i + 1 < n && a[i + 1] - a[i] <= x) memo[++i] = fi;}SegmentTree<mint> seg[2];auto f = [](mint l, mint r) { return l + r; };for (int i = 0; i < 2; ++i) seg[i] = SegmentTree<mint>(n + 1, f, 0);seg[0].update(0, 1);seg[1].update(0, 1);for (int i = 0; i < n; ++i)for (int j = 0; j < 2; ++j) {int l = memo[i],r = (int)(lower_bound(a.begin(), a.end(), a[i + 1] - x) -a.begin()) +1;l = max(l, r);mint now = memo[i] == 0;if (l < i + 1) now += seg[1 ^ j].query(l, i + 1);seg[j].update(i + 1, now);}cnt[x] = seg[0].query(n, n + 1) + seg[1].query(n, n + 1);res += (cnt[x] - cnt[x - 1]) * x;}return res / 2;}