#119542 (C++14) No.284 門松と魔法(2)

提出ソース

結果

問題	No.284 門松と魔法(2)
ユーザー	sigma425
提出日時	2016-09-25 22:17:11
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	4,873 ms / 5,000 ms
コード長	3,589 bytes
コンパイル時間	2,647 ms
コンパイル使用メモリ	199,056 KB
実行使用メモリ	16,724 KB
最終ジャッジ日時	2024-11-18 13:07:56
合計ジャッジ時間	29,358 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	8 ms 15,636 KB
testcase_01	AC	7 ms 15,628 KB
testcase_02	AC	8 ms 15,696 KB
testcase_03	AC	8 ms 15,720 KB
testcase_04	AC	8 ms 15,644 KB
testcase_05	AC	8 ms 15,600 KB
testcase_06	AC	8 ms 15,736 KB
testcase_07	AC	8 ms 15,692 KB
testcase_08	AC	8 ms 15,788 KB
testcase_09	AC	8 ms 15,624 KB
testcase_10	AC	13 ms 15,704 KB
testcase_11	AC	10 ms 15,724 KB
testcase_12	AC	12 ms 15,640 KB
testcase_13	AC	8 ms 15,692 KB
testcase_14	AC	10 ms 15,676 KB
testcase_15	AC	9 ms 15,628 KB
testcase_16	AC	12 ms 15,732 KB
testcase_17	AC	8 ms 15,604 KB
testcase_18	AC	11 ms 15,684 KB
testcase_19	AC	9 ms 15,720 KB
testcase_20	AC	9 ms 15,640 KB
testcase_21	AC	10 ms 15,720 KB
testcase_22	AC	17 ms 15,580 KB
testcase_23	AC	250 ms 15,688 KB
testcase_24	AC	3,153 ms 16,528 KB
testcase_25	AC	1,155 ms 16,200 KB
testcase_26	AC	8 ms 15,616 KB
testcase_27	AC	8 ms 15,716 KB
testcase_28	AC	8 ms 15,636 KB
testcase_29	AC	4,781 ms 16,724 KB
testcase_30	AC	4,145 ms 16,468 KB
testcase_31	AC	1,218 ms 16,600 KB
testcase_32	AC	4,873 ms 16,472 KB
testcase_33	AC	989 ms 16,472 KB
testcase_34	AC	1,153 ms 16,476 KB
testcase_35	AC	7 ms 15,636 KB
testcase_36	AC	8 ms 15,664 KB
testcase_37	AC	1,614 ms 16,472 KB
testcase_38	AC	1,030 ms 16,704 KB
testcase_39	AC	26 ms 15,616 KB

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

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:141:44: warning: 'arg2' may be used uninitialized [-Wmaybe-uninitialized]
  141 |                                 int mx2=-2,arg2;
      |                                            ^~~~
main.cpp:151:38: warning: 'arg' may be used uninitialized [-Wmaybe-uninitialized]
  151 |                                 uval = D(arg,X,mx,-1,-1,-1);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:131:35: note: 'arg' was declared here
  131 |                         int mx=-2,arg;
      |                                   ^~~
main.cpp:113:44: warning: 'arg2' may be used uninitialized [-Wmaybe-uninitialized]
  113 |                                 int mx2=-2,arg2;
      |                                            ^~~~
main.cpp:123:38: warning: 'arg' may be used uninitialized [-Wmaybe-uninitialized]
  123 |                                 dval = D(arg,X,mx,-1,-1,-1);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:103:35: note: 'arg' was declared here
  103 |                         int mx=-2,arg;
      |                                   ^~~

ソースコード

raw source code

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

struct D{
	int segid[2],id[2],mx[2];			//id[i] -> segid[i] -> nxt
	D(){
		segid[0]=segid[1]=-1;
		id[0]=id[1]=-1;
		mx[0]=mx[1]=-1;
	}
	D(int x){
		segid[0]=x;
		segid[1]=-1;
		id[0]=-1;
		id[1]=-1;
		mx[0]=1;
		mx[1]=-1;
	}
	D(int a,int b,int c,int d,int e,int f){
		id[0]=a,segid[0]=b,mx[0]=c,id[1]=d,segid[1]=e,mx[1]=f;
	}
	const static D e;
	D operator+(const D& r) const {
		typedef pair<int,int> P;
		typedef pair<P,int> PP;
		map<int,P> mp;
		rep(i,2) if(mx[i]>=0) chmax(mp[id[i]],P(mx[i],segid[i]));
		rep(i,2) if(r.mx[i]>=0) chmax(mp[r.id[i]],P(r.mx[i],r.segid[i]));
		vector<PP> vp;
		for(auto it:mp) vp.pb(PP(it.sc,it.fs));
		sort(all(vp),greater<PP>());
		int K=vp.size();
		D ret;
		rep(i,min(2,K)) ret.id[i]=vp[i].sc,ret.mx[i]=vp[i].fs.fs,ret.segid[i]=vp[i].fs.sc;
		return ret;
	}
	void inc(){
		rep(i,2) if(mx[i]>=0) mx[i]++;
	}
	friend ostream& operator<<(ostream& o,const D& d){
		o<<"d=   mx="<<d.mx[0]<<" at ("<<d.id[0]<<","<<d.segid[0]<<")"<<endl;
		o<<"     mx="<<d.mx[1]<<" at ("<<d.id[1]<<","<<d.segid[1]<<")"<<endl;
		return o;
	}
};
const D D::e = D();

template<class D>
struct segtree{
	static const int N=1<<17;

	D e=D::e;
	vector<D> seg;
	segtree():seg(N*2,e){}
	void update(int k,D val){
		k+=N;
		seg[k]=val;
		k/=2;
		while(k){
			seg[k]=seg[k*2]+seg[k*2+1];
			k/=2;
		}
	}
	D calc(int a,int b,int l=0,int r=N,int k=1){
		if(b<=a||b<=l||r<=a) return e;
		if(a<=l&&r<=b) return seg[k];
		return calc(a,b,l,(l+r)/2,k*2)+calc(a,b,(l+r)/2,r,k*2+1);
	}
};
segtree<D> up,down;


int N;
int x[100000];
vector<int> xs;
int main(){
	cin>>N;
	rep(i,N){
		scanf("%d",x+i);
		xs.pb(x[i]);
	}
	sort(all(xs));
	xs.erase(unique(xs.begin(),xs.end()),xs.end());
	int K=xs.size();
	rep(i,N) x[i]=lower_bound(all(xs),x[i])-xs.begin();
	rep(i,N){
//		printf("i=%d\n",i);
		int X=x[i];
		D dval,uval;
		{//go up
			D dmx=down.calc(0,X);
			int mx=-2,arg;
			rep(j,2){
				if(dmx.id[j]!=X){
					mx=dmx.mx[j];
					arg=dmx.segid[j];
					break;
				}
			}
			if(mx>=0){
				D dmx2 = down.calc(0,arg) + down.calc(arg+1,X);
				int mx2=-2,arg2;
				rep(j,2){
					if(dmx2.id[j]!=X){
						mx2=dmx2.mx[j];
						arg2=dmx2.segid[j];
						break;
					}
				}
				dval = D(arg,X,mx,arg2,X,mx2);
			}else{
				dval = D(arg,X,mx,-1,-1,-1);
			}
			dval.inc();
			dval = dval + D(X);
		}

		{//go down
			D umx=up.calc(X+1,K);
			int mx=-2,arg;
			rep(j,2){
				if(umx.id[j]!=X){
					mx=umx.mx[j];
					arg=umx.segid[j];
					break;
				}
			}
			if(mx>=0){
				D umx2 = up.calc(X+1,arg) + up.calc(arg+1,K);
				int mx2=-2,arg2;
				rep(j,2){
					if(umx2.id[j]!=X){
						mx2=umx2.mx[j];
						arg2=umx2.segid[j];
						break;
					}
				}
				uval = D(arg,X,mx,arg2,X,mx2);
			}else{
				uval = D(arg,X,mx,-1,-1,-1);
			}
			uval.inc();
			uval = uval + D(X);
		}
		// cout<<"dval"<<endl<<dval<<endl;
		// cout<<"uval"<<endl<<uval<<endl;
		up.update(X,dval);
		down.update(X,uval);
	}
	int ans=max(up.calc(0,K).mx[0],down.calc(0,K).mx[0]);
	if(ans<=2) ans=0;
	cout<<ans<<endl;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード