結果

問題 No.3392 Count 23578 Sequence
コンテスト
ユーザー GhostMFC
提出日時 2025-12-01 18:54:08
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 145 ms / 2,000 ms
コード長 1,603 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,310 ms
コンパイル使用メモリ 194,992 KB
実行使用メモリ 23,220 KB
最終ジャッジ日時 2025-12-01 18:54:32
合計ジャッジ時間 23,549 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define inf 0x7fffffff
#define llinf 0x7fffffffffffffff
#define F(a,b,c,d) for(int b=c;b<=d;b+=a)
#define F2(a,b,c,d) for(int b=c;b>=d;b-=a)
#define PRC(b,a) fixed<<setprecision(a)<<b
#define pb push_back
#define All(x) x.begin(),x.end()
#define Next(a,b) for(int a=head[b];a;a=edge[a].nxt)
#define IOS ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
inline ll q_2(ll xx){return xx*xx;}
inline ll Gcd(ll xx,ll yy){return yy?Gcd(yy,xx%yy):xx;}
inline ll q_Pow(ll xx,ll yy,ll pp){ll oo=1;for(;yy;yy>>=1,xx=xx*xx%pp)yy&1?oo=oo*xx%pp:0;return oo;}
inline void Cout(){cout<<endl;}
template <class T1,class...T2>
inline void Cout(T1 x,T2 ...y){cout<<x<<' ';Cout(y...);}
template <typename T> inline void sMin(T &xx,T yy){xx=(xx<yy)?xx:yy;}
template <typename T> inline void sMax(T &xx,T yy){xx=(xx>yy)?xx:yy;}

const int N=1000010;

ll ans;
int n,a[N],s[N<<1],d[N<<1];

inline void solve(){
  int r=0,c=1;
  for(int i=1;i<=n;++i){
    d[i]=(i<r)?min(d[c*2-i],r-i):0;
    while(i-d[i]>1&&i+d[i]<n&&s[i-d[i]-1]==s[i+d[i]+1])
      ++d[i];
    if(i+d[i]>r) c=i,r=i+d[i];
  }
  // for(int i=1;i<=n;++i)
  //   cout<<d[i]<<' ';
  // cout<<'\n';
  for(int i=1;i<=n;++i)
    if(i&1) ans+=1+d[i]/2;
    else ans+=(1+d[i])/2;
  cout<<ans<<'\n';
}

signed main(){
  IOS
  cin>>n;
  for(int i=1;i<=n;++i)
    cin>>a[i];
  ans=n; --n;
  for(int i=1;i<=n;++i)
    a[i]=a[i+1]-a[i],s[(i<<1)-1]=a[i];
  n=2*n-1;
  // for(int i=1;i<=n;++i)
  //   cout<<s[i]<<' ';
  solve();
  return 0;
}
0