結果

問題 No.3392 Count 23578 Sequence
コンテスト
ユーザー GOTKAKO
提出日時 2025-11-29 05:31:24
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 179 ms / 2,000 ms
コード長 2,065 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,178 ms
コンパイル使用メモリ 201,588 KB
実行使用メモリ 26,732 KB
最終ジャッジ日時 2025-11-29 05:31:38
合計ジャッジ時間 13,620 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

template<typename T>
vector<int> Mana(const vector<T> &s){ //Manacher
    int n = s.size();
    vector<int> ret(n);
    for(int i=0,w=0; i<n;){
        while(i+w < n && i-w >= 0 && s.at(i-w) == s.at(i+w)) w++; //愚直に伸ばす.
        ret.at(i) = w;
        int k = 1; //i-kとi+kの回文範囲は iの回文範囲までは同じ.
        while(i-k >= 0 && k+ret.at(i-k) < w) ret.at(i+k) = ret.at(i-k),k++; //i-kが完全に含まれるならi+kも同じ.
        i += k; w -= k; //含まれなくてもw-kまでは同じ.
    }
    return ret;
}
template<typename T>
vector<int> Mana2(const vector<T> &s){ //偶数長検出用.
    if(s.size() == 0) return {};
    vector<T> t; t.reserve(s.size()<<1);
    T inf = numeric_limits<T>::max();
    for(auto &c : s) t.push_back(c),t.push_back(inf); //間にinfを挟むことで奇数長にする.
    t.pop_back();
    auto ret = Mana(t); //M[i%2 == 0]=偶数は-1,M[i%2 == 1]=奇数は-1.
    for(int i=0; i<(int)ret.size(); i++) if((i&1) == (ret.at(i)&1)) ret.at(i)--;
    return ret;
}
vector<int> Mana(const string &s){ 
    int n = s.size();
    vector<int> ret(n);
    for(int i=0,w=0; i<n;){
        while(i+w < n && i-w >= 0 && s.at(i-w) == s.at(i+w)) w++;
        ret.at(i) = w;
        int k = 1;
        while(i-k >= 0 && k+ret.at(i-k) < w) ret.at(i+k) = ret.at(i-k),k++;
        i += k; w -= k;
    }
    return ret;
}
vector<int> Mana2(const string &s){
    if(s.size() == 0) return {};
    string t; t.reserve(s.size()<<1);
    for(auto &c : s) t.push_back(c),t.push_back('$');
    t.pop_back();
    auto ret = Mana(t);
    for(int i=0; i<(int)ret.size(); i++) if((i&1) == (ret.at(i)&1)) ret.at(i)--;
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<int> A(N);
    for(auto &a : A) cin >> a;

    long long answer = N;
    vector<int> D(N-1);
    for(int i=0; i<N-1; i++) D.at(i) = A.at(i+1)-A.at(i);
    for(auto m : Mana2(D)) answer += (m+1)/2;
    cout << answer << endl;
}
0