#140947 (C++11) No.284 門松と魔法(2)

提出ソース

結果

問題	No.284 門松と魔法(2)
ユーザー	rickytheta
提出日時	2016-12-23 11:43:40
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	765 ms / 5,000 ms
コード長	5,448 bytes
コンパイル時間	1,782 ms
コンパイル使用メモリ	184,252 KB
実行使用メモリ	20,756 KB
最終ジャッジ日時	2024-05-08 11:38:31
合計ジャッジ時間	7,495 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	1 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	1 ms 6,944 KB
testcase_06	AC	1 ms 6,944 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	1 ms 6,944 KB
testcase_09	AC	1 ms 6,944 KB
testcase_10	AC	3 ms 6,944 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,944 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	1 ms 6,944 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,940 KB
testcase_22	AC	3 ms 6,940 KB
testcase_23	AC	33 ms 6,940 KB
testcase_24	AC	483 ms 15,800 KB
testcase_25	AC	188 ms 9,800 KB
testcase_26	AC	2 ms 6,944 KB
testcase_27	AC	1 ms 6,940 KB
testcase_28	AC	2 ms 6,944 KB
testcase_29	AC	708 ms 18,056 KB
testcase_30	AC	563 ms 17,568 KB
testcase_31	AC	379 ms 16,000 KB
testcase_32	AC	765 ms 20,304 KB
testcase_33	AC	286 ms 20,652 KB
testcase_34	AC	464 ms 20,756 KB
testcase_35	AC	2 ms 6,944 KB
testcase_36	AC	1 ms 6,940 KB
testcase_37	AC	413 ms 16,184 KB
testcase_38	AC	283 ms 15,896 KB
testcase_39	AC	6 ms 6,940 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

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);
      |           ~~~~~^~~~~~~~~~

ソースコード

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;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード