結果
問題 | No.1294 マウンテン数列 |
ユーザー | milanis48663220 |
提出日時 | 2020-11-20 23:19:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,560 bytes |
コンパイル時間 | 1,147 ms |
コンパイル使用メモリ | 95,308 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-23 13:52:54 |
合計ジャッジ時間 | 15,933 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,812 KB |
testcase_01 | AC | 3 ms
6,940 KB |
testcase_02 | AC | 3 ms
6,940 KB |
testcase_03 | AC | 3 ms
6,940 KB |
testcase_04 | AC | 3 ms
6,940 KB |
testcase_05 | AC | 183 ms
6,944 KB |
testcase_06 | AC | 259 ms
6,940 KB |
testcase_07 | AC | 3 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | AC | 1,591 ms
6,940 KB |
testcase_15 | TLE | - |
testcase_16 | AC | 1,601 ms
6,944 KB |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;const ll MOD = 998244353;class ModInt{public:ll v;ModInt(ll _v = 0){v = _v;}ModInt operator+(ll n){ll m = v+n;if(v > MOD) m %= MOD;return ModInt(m);}ModInt operator-(ll n){ll m = v-n;if(v < 0) m = (m+MOD)%MOD;return ModInt(m);}ModInt operator*(ll n){return ModInt((v*n)%MOD);}ModInt operator/(ll n){return ModInt((ModInt(n).inv()*v).v%MOD);}void operator+=(ll n){ll m = v+n;if(v > MOD) m %= MOD;v = m;}void operator-=(ll n){ll m = v-n;if(v < 0) m = (m+MOD)%MOD;v = m;}void operator*=(ll n){v = (v*n)%MOD;}ModInt operator+(ModInt n){return ModInt((v+n.v)%MOD);}ModInt operator-(ModInt n){return ModInt((v-n.v+MOD)%MOD);}ModInt operator*(ModInt n){return ModInt((v*n.v)%MOD);}ModInt operator/(ModInt n){return ModInt((n.inv()*v).v%MOD);}void operator+=(ModInt n){v = (v+n.v)%MOD;}void operator-=(ModInt n){v = (v-n.v+MOD)%MOD;}void operator*=(ModInt n){v = (v*n.v)%MOD;}void operator=(ModInt n){v = n.v;}void operator=(ll n){v = n;}ModInt inv(){if(v == 1) return ModInt(1);else return ModInt(MOD-ModInt(MOD%v).inv().v*(MOD/v)%MOD);}};ostream& operator<<(ostream& os, const ModInt& m){os << m.v;return os;}istream & operator >> (istream &in, ModInt &m){in >> m.v;return in;}template <typename T>struct segtree{int n;T UNIT;vector<T> dat;T (*calc)(T, T);segtree(int n_, T unit, T (*_calc)(T, T)){UNIT = unit;calc = _calc;n = 1;while(n < n_) n *= 2;dat = vector<T>(2*n);for(int i = 0; i < 2*n; i++) dat[i] = UNIT;}void insert(int k, T a){dat[k+n-1] = a;}void update_all(){for(int i = n-2; i >= 0; i--){dat[i] = calc(dat[i*2+1], dat[i*2+2]);}}//k番目の値(0-indexed)をaに変更void update(int k, T a){k += n-1;dat[k] = a;while(k > 0){k = (k-1)/2;dat[k] = calc(dat[k*2+1], dat[k*2+2]);}}//[a, b)//区間[a, b]へのクエリに対してはquery(a, b+1)と呼ぶT query(int a, int b, int k=0, int l=0, int r=-1){if(r < 0) r = n;if(r <= a || b <= l) return UNIT;if(a <= l && r <= b) return dat[k];else{T vl = query(a, b, k*2+1, l, (l+r)/2);T vr = query(a, b, k*2+2, (l+r)/2, r);return calc(vl, vr);}}};ModInt add(ModInt x, ModInt y){ return x+y; }int n;vector<int> a;// 差がm以下のマウンテン配列の個数ModInt count(int m){vector<ModInt> dp(n+1, ModInt(0));segtree<ModInt> sgt(n, ModInt(0), add);set<int> rem;for(int i = 0; i < n; i++){rem.insert(i);}if(a[0]-a[1] > m) return ModInt(0);dp[0] = 2;dp[1] = 2;sgt.update(0, ModInt(2));// sgt.update(1, ModInt(2));for(int i = 2; i < n; i++){if(a[i-1]-a[i] > m) return ModInt(0);if(a[0]-a[i] <= m){dp[i] = sgt.query(0, i)+dp[i-1];}else{int l = 0, r = i-1;while(r-l > 1){int c = (l+r)/2;if(a[c]-a[i] > m) l = c;else r = c;}dp[i] = sgt.query(r, i)+dp[i-1];}sgt.update(i-1, dp[i]-dp[i-1]);}// if(m == 2 || m == 3){// for(int i = 0; i < n; i++) cout << dp[i] << ' ';// cout << endl;// }return dp[n-1];}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;cin >> n;a.assign(n, 0);for(int i = 0; i < n; i++){cin >> a[i];}reverse(a.begin(), a.end());vector<ModInt> cnt(2501, ModInt(0));for(int i = 1; i <= 2500; i++){cnt[i] = count(i);}ModInt ans = 0;for(int i = 1; i <= 2500; i++){ans += (cnt[i]-cnt[i-1])*i;// if((cnt[i]-cnt[i-1]).v != 0) cout << i << ':' << cnt[i] << '-' << cnt[i-1] << endl;}cout << ans << endl;}