結果

問題 No.1294 マウンテン数列
ユーザー milanis48663220milanis48663220
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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