結果

問題 No.284 門松と魔法(2)
コンテスト
ユーザー rickytheta
提出日時 2016-12-23 11:43:40
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 826 ms / 5,000 ms
コード長 5,448 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,058 ms
コンパイル使用メモリ 186,032 KB
実行使用メモリ 20,724 KB
最終ジャッジ日時 2024-12-14 15:22:19
合計ジャッジ時間 8,432 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:121:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  121 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
main.cpp:122:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  122 |   REP(i,n)scanf("%d",a+i);
      |           ~~~~~^~~~~~~~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
typedef ll _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)
 
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()
 
#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))
 
// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD
 
// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

struct obj{
  int len,bef2,bef;
  obj(){
    len=0;
    bef2=bef=-1;
  }
  obj(int len,int bef2,int bef):len(len),bef2(bef2),bef(bef){}
  bool operator<(const obj &that) const{
    return len < that.len;
  }
  void debug(){
    printf("[%d,%d,%d]",len,bef2,bef);
  }
};
struct node{
  obj best[2];
  node(){}
  node merge(const node &that) const{
    node ret;
    ret.best[0] = max(best[0], that.best[0]);
    ret.best[1] = obj(-2521,-1,-1);
    if(ret.best[0].bef2 != best[0].bef2)CHMAX(ret.best[1],best[0]);
    if(ret.best[0].bef2 != best[1].bef2)CHMAX(ret.best[1],best[1]);
    if(ret.best[0].bef2 != that.best[0].bef2)CHMAX(ret.best[1],that.best[0]);
    if(ret.best[0].bef2 != that.best[1].bef2)CHMAX(ret.best[1],that.best[1]);
    return ret;
  }
  void debug(){
    best[0].debug();
    printf(", ");
    best[1].debug();
    printf("\n");
  }
};
struct segment{
  int n;
  vector<node> data;
  segment(int n_){
    n=1;
    while(n<n_)n<<=1;
    data.resize(2*n-1);
    REP(i,n){
      data[i+n-1]=node();
      data[i+n-1].best[0].bef = i;
      data[i+n-1].best[1].bef = i;
    }
    FORR(i,0,n-1)data[i]=data[2*i+1].merge(data[2*i+2]);
  }
  void set(int x,node v){
    x += n-1;
    data[x] = v;
    while(x>0){
      x = (x-1)/2;
      data[x] = data[2*x+1].merge(data[2*x+2]);
    }
  }
  node get(int x){
    return data[x+n-1];
  }
  node query(int l,int r,int a,int b,int k){
    if(r<=a || b<=l)return node();
    if(l<=a && b<=r){
      return data[k];
    }else{
      int m = (a+b)/2;
      node lef = query(l,r,a,m,2*k+1);
      node rig = query(l,r,m,b,2*k+2);
      return lef.merge(rig);
    }
  }
  node query(int l,int r){
    return query(l,r,0,n,0);
  }
};

obj succ(const obj &o,int v){
  if(o.bef2==v){
    return obj(-2521,-1,-1);
  }else{
    return obj(o.len+1, o.bef, v);
  }
}

int n;
int a[125252];

int main(){
  scanf("%d",&n);
  REP(i,n)scanf("%d",a+i);
  // kowai node zaatu
  {
    map<int,int> M;
    REP(i,n)M[a[i]]=0;
    int it = 1;
    for(pair<int,int> P:M){
      M[P.first] = it++;
    }
    REP(i,n)a[i]=M[a[i]];
  }
  segment up(n+10),down(n+10);
  int ans = 0;
  REP(i,n){
    int v = a[i];
    node nxtdown = down.get(v), nxtup = up.get(v);
    {
      vector<obj> yo;
      yo.push_back(nxtdown.best[0]); yo.push_back(nxtdown.best[1]);
      node q = up.query(v+1,n+5);
      yo.push_back(succ(q.best[0],v)); yo.push_back(succ(q.best[1],v));
      int split_a = q.best[0].bef;
      int split_b = q.best[1].bef;
      if(v<split_a){
        q = up.query(v+1,split_a);
        yo.push_back(succ(q.best[0],v)); yo.push_back(succ(q.best[1],v));
        q = up.query(split_a+1,n+5);
        yo.push_back(succ(q.best[0],v)); yo.push_back(succ(q.best[1],v));
      }
      if(v<split_b){
        q = up.query(v+1,split_b);
        yo.push_back(succ(q.best[0],v)); yo.push_back(succ(q.best[1],v));
        q = up.query(split_b+1,n+5);
        yo.push_back(succ(q.best[0],v)); yo.push_back(succ(q.best[1],v));
      }
      sort(ALL(yo));
      reverse(ALL(yo));

      int x=-2;
      REP(j,yo.size()){
        if(yo[j].bef2 != v){
          if(x==-2){
            nxtdown.best[0] = yo[j];
            x = yo[j].bef2;
          }else if(x != yo[j].bef2){
            nxtdown.best[1] = yo[j];
            break;
          }
        }
      }
    }
    {
      vector<obj> yo;
      yo.push_back(nxtup.best[0]); yo.push_back(nxtup.best[1]);
      node q = down.query(0,v);
      yo.push_back(succ(q.best[0],v)); yo.push_back(succ(q.best[1],v));
      int split_a = q.best[0].bef;
      int split_b = q.best[1].bef;
      if(split_a<v){
        q = down.query(0,split_a);
        yo.push_back(succ(q.best[0],v)); yo.push_back(succ(q.best[1],v));
        q = down.query(split_a+1,v);
        yo.push_back(succ(q.best[0],v)); yo.push_back(succ(q.best[1],v));
      }
      if(split_b<v){
        q = down.query(0,split_b);
        yo.push_back(succ(q.best[0],v)); yo.push_back(succ(q.best[1],v));
        q = down.query(split_b+1,v);
        yo.push_back(succ(q.best[0],v)); yo.push_back(succ(q.best[1],v));
      }
      sort(ALL(yo));
      reverse(ALL(yo));

      int x=-2;
      REP(j,yo.size()){
        if(yo[j].bef2 != v){
          if(x==-2){
            nxtup.best[0] = yo[j];
            x = yo[j].bef2;
          }else if(x != yo[j].bef2){
            nxtup.best[1] = yo[j];
            break;
          }
        }
      }
    }
    up.set(v,nxtup);
    down.set(v,nxtdown);
    // nxtup.debug();
    // nxtdown.debug();
    CHMAX(ans,nxtup.best[0].len);
    CHMAX(ans,nxtdown.best[0].len);
  }
  if(ans<3)ans=0;
  printf("%d\n",ans);
  return 0;
}
0