結果

問題 No.921 ずんだアロー
ユーザー ateate
提出日時 2019-11-18 14:37:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,495 bytes
コンパイル時間 2,402 ms
コンパイル使用メモリ 222,428 KB
実行使用メモリ 8,540 KB
最終ジャッジ日時 2024-10-01 14:55:49
合計ジャッジ時間 3,725 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 45 ms
8,340 KB
testcase_11 AC 49 ms
8,392 KB
testcase_12 AC 12 ms
5,248 KB
testcase_13 AC 38 ms
7,536 KB
testcase_14 AC 42 ms
7,868 KB
testcase_15 AC 25 ms
5,820 KB
testcase_16 AC 5 ms
5,248 KB
testcase_17 AC 43 ms
8,008 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 50 ms
8,540 KB
testcase_24 AC 27 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = long long;
using pll = pair<ll,ll>;
constexpr ll INF = (1LL<<60);
constexpr ll MOD = (1e9+7);
//constexpr ll MOD = (998244353);
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;}
void dump(){cout<<endl;}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){cout<<h<<", ";dump(forward<Ts>(t)...);}
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}

void solve1();void solve2();void solve3();
int main(){
  solve2();
  return 0;
}

void solve3(){
  ll n;cin>>n;
  vector<ll> a(n);
  cin>>a;
  vector<ll> dp(2*n);
  rep(i,n-1){
    ll t=0;
    if(i>0&&a[i]==a[i+1])chmax(t,dp[i]);
    if(i-1>=0)chmax(t,dp[i-1]);
    if(i-2>=0)chmax(t,dp[i-2]);
    dp[i+1]=t+1;
  }
  dp[n]=max(dp[n-1],dp[n-2])+1;
  cout<<(*max_element(dp.begin(),dp.end()))<<endl;

}

template<class T>
class segtree {
private:
  ll n=1;
  T unit;
  std::vector<T> dat;
  std::function<T(T,T)> func;
public:
  segtree(){}
  segtree(std::vector<T> a,T v,std::function<T(T,T)> f){
    build(a,v,f);
  }
  void build(std::vector<T>& a,T v,std::function<T(T,T)> f){
    ll sz=a.size();
    unit=v;
    func=f;
    while(n<sz)n<<=1LL;
    dat.resize(2*n-1,unit);
    for(int i=0;i<sz;++i)dat[i+n-1]=a[i];
    for(int i=n-2;i>=0;--i){
      dat[i]=func(dat[i*2+1],dat[i*2+2]);
    }
  }
  void update(ll idx,T val){
    idx+=n-1;
    dat[idx]=val;
    while(idx){
      idx--;idx>>=1LL;
      dat[idx]=func(dat[idx*2+1],dat[idx*2+2]);
    }
  }
  T query(ll a,ll b,ll k=0,ll l=0,ll r=-1){
    if(r<0)r=n;
    if( b<=l || r<=a )return unit;
    if( a<=l && r<=b )return dat[k];
    else{
      auto left=query(a,b,2*k+1,l,(l+r)/2);
      auto right=query(a,b,2*k+2,(l+r)/2,r);
      return func(left,right);
    }
  }
};

void solve2(){

  ll n;
  cin>>n;
  vector<ll> a(n);
  cin>>a;

  vector<ll> b;
  ll cnt=1;
  rep(i,n-1){
    if(a[i]!=a[i+1]){
      b.emplace_back(cnt);
      cnt=1;
    }else{
      cnt++;
    }
  }
  b.emplace_back(cnt);

  ll m = b.size();
  vector<ll> dp(m+1);
  segtree<ll> seg(vector<ll>(m+1),0,[](auto a,auto b){return max(a,b);});
  dp[1]=b[0];
  seg.update(1,b[0]);
  for(ll i=2;i<=m;++i){
    dp[i]=max(dp[i-2],seg.query(0,i-1)+b[i-1]);
    seg.update(i,dp[i]);
  }

  cout<<(seg.query(0,m+1))<<endl;

}

void solve1(){

  ll n;
  cin>>n;
  vector<ll> a(n);
  cin>>a;

  vector<ll> b;
  ll cnt = 1;
  rep(i,n-1){
    if(a[i]!=a[i+1]){
      b.emplace_back(cnt);
      cnt=1;
    }else{
      cnt++;
    }
  }
  b.emplace_back(cnt);
  
  auto indexed = [](vector<ll>const& v){
    vector<pll> a(v.size());
    rep(i,v.size())a[i]={v[i],i};
    return a;
  };

  segtree<pll> seg(indexed(b),pll(0ll,0ll),[](auto a,auto b){return max(a,b);});
  ll ans = 0;
  ll m = b.size();
  while(1){
    ll val,idx;
    tie(val,idx)=seg.query(0,m);
    if(val==0)break;
    ans += val;
    seg.update(idx,pll(0ll,0ll));
    if(idx>0)seg.update(idx-1,pll(0ll,0ll));
    if(idx+1<m)seg.update(idx+1,pll(0ll,0ll));
  }
  cout<<(ans)<<endl;

}
0