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

提出ソース

結果

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

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	7 ms 15,700 KB
testcase_01	AC	6 ms 15,624 KB
testcase_02	AC	6 ms 15,584 KB
testcase_03	AC	7 ms 15,584 KB
testcase_04	AC	7 ms 15,720 KB
testcase_05	AC	6 ms 15,728 KB
testcase_06	AC	6 ms 15,788 KB
testcase_07	AC	6 ms 15,708 KB
testcase_08	AC	6 ms 15,716 KB
testcase_09	AC	6 ms 15,640 KB
testcase_10	AC	7 ms 15,712 KB
testcase_11	AC	6 ms 15,708 KB
testcase_12	AC	7 ms 15,640 KB
testcase_13	AC	7 ms 15,648 KB
testcase_14	AC	7 ms 15,644 KB
testcase_15	AC	6 ms 15,732 KB
testcase_16	AC	6 ms 15,632 KB
testcase_17	AC	5 ms 15,708 KB
testcase_18	AC	6 ms 15,744 KB
testcase_19	AC	6 ms 15,724 KB
testcase_20	AC	6 ms 15,628 KB
testcase_21	AC	6 ms 15,584 KB
testcase_22	AC	6 ms 15,644 KB
testcase_23	AC	36 ms 15,796 KB
testcase_24	AC	412 ms 16,652 KB
testcase_25	AC	155 ms 16,308 KB
testcase_26	AC	7 ms 15,640 KB
testcase_27	AC	5 ms 15,640 KB
testcase_28	AC	5 ms 15,640 KB
testcase_29	AC	631 ms 16,600 KB
testcase_30	AC	506 ms 16,728 KB
testcase_31	AC	170 ms 16,604 KB
testcase_32	AC	689 ms 16,600 KB
testcase_33	AC	226 ms 16,724 KB
testcase_34	AC	211 ms 16,600 KB
testcase_35	AC	7 ms 15,648 KB
testcase_36	AC	6 ms 15,704 KB
testcase_37	AC	223 ms 16,604 KB
testcase_38	AC	146 ms 16,636 KB
testcase_39	AC	10 ms 15,644 KB

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

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:163:44: warning: 'arg2' may be used uninitialized [-Wmaybe-uninitialized]
  163 |                                 int mx2=-2,arg2;
      |                                            ^~~~
main.cpp:173:38: warning: 'arg' may be used uninitialized [-Wmaybe-uninitialized]
  173 |                                 uval = D(arg,X,mx,-1,-1,-1);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:153:35: note: 'arg' was declared here
  153 |                         int mx=-2,arg;
      |                                   ^~~
main.cpp:135:44: warning: 'arg2' may be used uninitialized [-Wmaybe-uninitialized]
  135 |                                 int mx2=-2,arg2;
      |                                            ^~~~
main.cpp:145:38: warning: 'arg' may be used uninitialized [-Wmaybe-uninitialized]
  145 |                                 dval = D(arg,X,mx,-1,-1,-1);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:125:35: note: 'arg' was declared here
  125 |                         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;
	}*/
	D operator+(const D& r) const {
		int tid[4],tsegid[4],tmx[4],K=0;
		rep(i,2) if(mx[i]>=0) tid[K]=id[i],tsegid[K]=segid[i],tmx[K]=mx[i],K++;
		rep(i,2) if(r.mx[i]>=0) tid[K]=r.id[i],tsegid[K]=r.segid[i],tmx[K]=r.mx[i],K++;
		rep(i,K-1) rep(j,K-1-i) if(tmx[j]<tmx[j+1]) swap(tmx[j],tmx[j+1]),swap(tsegid[j],tsegid[j+1]),swap(tid[j],tid[j+1]);

		int I=0;
		D ret;
		rep(i,K){
			bool ok=1;
			rep(j,i){
				if(tid[j]==tid[i]){
					ok=0;
					break;
				}
			}
			if(!ok) continue;
			ret.id[I]=tid[i],ret.segid[I]=tsegid[i],ret.mx[I]=tmx[i],I++;
			if(I==2) break;
		}
		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

結果

テストケース

コンパイルメッセージ

ソースコード