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

提出ソース

結果

問題	No.284 門松と魔法(2)
ユーザー	btk
提出日時	2016-03-18 12:11:14
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	3,978 ms / 5,000 ms
コード長	7,090 bytes
コンパイル時間	1,813 ms
コンパイル使用メモリ	177,988 KB
実行使用メモリ	98,320 KB
最終ジャッジ日時	2024-10-01 09:05:40
合計ジャッジ時間	32,035 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	78 ms 94,096 KB
testcase_01	AC	77 ms 94,220 KB
testcase_02	AC	78 ms 94,096 KB
testcase_03	AC	77 ms 94,096 KB
testcase_04	AC	78 ms 94,096 KB
testcase_05	AC	77 ms 94,096 KB
testcase_06	AC	76 ms 94,100 KB
testcase_07	AC	76 ms 94,096 KB
testcase_08	AC	77 ms 94,092 KB
testcase_09	AC	77 ms 94,096 KB
testcase_10	AC	82 ms 94,092 KB
testcase_11	AC	77 ms 94,096 KB
testcase_12	AC	79 ms 94,096 KB
testcase_13	AC	77 ms 94,096 KB
testcase_14	AC	80 ms 94,096 KB
testcase_15	AC	79 ms 94,096 KB
testcase_16	AC	81 ms 94,092 KB
testcase_17	AC	78 ms 94,096 KB
testcase_18	AC	82 ms 94,092 KB
testcase_19	AC	79 ms 94,092 KB
testcase_20	AC	80 ms 94,100 KB
testcase_21	AC	81 ms 94,096 KB
testcase_22	AC	85 ms 94,096 KB
testcase_23	AC	276 ms 94,092 KB
testcase_24	AC	2,588 ms 94,100 KB
testcase_25	AC	1,092 ms 94,100 KB
testcase_26	AC	77 ms 94,092 KB
testcase_27	AC	79 ms 93,964 KB
testcase_28	AC	78 ms 94,096 KB
testcase_29	AC	3,814 ms 95,500 KB
testcase_30	AC	3,052 ms 94,868 KB
testcase_31	AC	2,294 ms 94,224 KB
testcase_32	AC	3,978 ms 98,068 KB
testcase_33	AC	2,721 ms 98,320 KB
testcase_34	AC	2,765 ms 98,188 KB
testcase_35	AC	77 ms 93,968 KB
testcase_36	AC	77 ms 94,092 KB
testcase_37	AC	2,270 ms 94,352 KB
testcase_38	AC	1,643 ms 94,096 KB
testcase_39	AC	105 ms 94,096 KB

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

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;
#define SEG_TREE_SIZE 500000
#define NONE -1
#define DEBUG if(0)
typedef long long LL;
#define cp(x) x=o.x
#define INF 100010

struct INIT{INIT(){ios::sync_with_stdio(false);cin.tie(0);}}init;
vector<bool> used(SEG_TREE_SIZE,true);

struct V{
	int id,v,prev;
	V(int id,int v,int prev):id(id),v(v),prev(prev){}
	void print(){printf("(id=%d,v=%d,prev=%d)\n",id,v,prev);}
};

class ND{
public:
	pair<V,V> fs;
	ND():fs(V(0,-1,INF),V(0,-1,INF+1)){};
	ND(int id):fs(V(id,0,INF),V(id,0,INF+1)){};
	ND& copy(const ND& o){cp(fs);return *this;}
	ND& operator=(const ND& o){return copy(o);}
	ND operator+(const ND& o){
		ND res;
		auto fupdate=[&](const V& v){
			if(res.fs.first.v<v.v){
				used[res.fs.first.prev]=true;
				res.fs.first=v;
				used[res.fs.first.prev]=false;
			}
		};
		auto supdate=[&](const V& v){
			if(used[v.prev]&&res.fs.second.v<v.v){
				res.fs.second=v;
			}
		};
		fupdate(fs.first);fupdate(fs.second);
		fupdate(o.fs.first);fupdate(o.fs.second);
		supdate(fs.first);supdate(fs.second);
		supdate(o.fs.first);supdate(o.fs.second);
		used[res.fs.first.prev]=true;
		return res;
	}
};

template <typename T>
class node{
public:
	int bg,ed,L,R;
	T val,add_val,lazy_val;
	bool val_update,add_update;
	node():bg(NONE),ed(NONE),L(NONE),R(NONE),val(),add_val(),lazy_val(),val_update(false),add_update(false){}
	node(int bg,int ed,int L,int R):bg(bg),ed(ed),L(L),R(R),val(),add_val(),lazy_val(),val_update(false),add_update(false){}
	node(int bg,int ed,int L,int R,T val):bg(bg),ed(ed),L(L),R(R),val(val),add_val(),lazy_val(),val_update(false),add_update(false){}
	node(int bg,int ed,int L,int R,T val,T add_val):bg(bg),ed(ed),L(L),R(R),val(val),add_val(add_val),lazy_val(),val_update(false),add_update(false){}
	void set(T v){val_update=true,lazy_val=v;}
	void add(T v){add_update=true,add_val=add_val+v;}
	void update_clear(){val_update=add_update=false,add_val=lazy_val=T();}
	//T get(){return val+(add_val+lazy_val)*len();}
	T get(){return val+add_val+lazy_val;}
	int len(){return ed-bg+1;}
	node& copy(const node& o){cp(bg),cp(ed),cp(L),cp(R),cp(val),cp(add_val),cp(lazy_val),cp(val_update),cp(add_update);return *this;}
	node& operator=(const node& o){return copy(o);}
	bool isleaf(){return bg>=ed;}
	bool iscontain(int l,int r){return bg<=l&&r<=ed;}
	bool isequal(int l,int r){return l==bg&&r==ed;}
	void print(){
		printf("[%d-%d]updates(%d,%d)\n",bg,ed,(int)val_update,(int)add_update);
		get().print();
	}
};
node<LL> _seg_prepared_table[1];
/**/
template <typename T>
inline T merge(node<T> &l,node<T> &r){return l.get()+r.get();}
template <typename T>
inline T merge(T &l,node<T> &r){return l+r.get();}

template <typename T>
class segtree{
private:
using NODE=node<T>;
	int begin,end;
	stack<int> st1,stL,stR,rollback;
	NODE *t;
	inline void lazy_update(NODE& now){
		if(now.isleaf())return;
		if(now.val_update){t[now.L].set(now.lazy_val);t[now.R].set(now.lazy_val);}
		if(now.add_update){t[now.L].add(now.add_val);t[now.R].add(now.add_val);}
		now.update_clear();
	}
	void all_update(){
		while(rollback.empty()==false){
			auto& now=t[rollback.top()];rollback.pop();
			if(!now.isleaf())now.val=merge(t[now.L],t[now.R]);
		}
	}
public:
	segtree():begin(0),end(0),t(_seg_prepared_table){}
	segtree(int bg,int ed,NODE* t):begin(bg),end(ed),t(t){
		int sz=0;
		t[0]=NODE(bg,ed,sz+1,sz+2);sz+=2;
		st1.push(0);
		while(st1.empty()==false){
			int id=st1.top();st1.pop();rollback.push(id);
			auto& now=t[id];
			if(now.isleaf()){now.val=T(now.bg);continue;}
			int half=(now.bg+now.ed)/2;
			t[now.L]=NODE(now.bg,half,sz+1,sz+2);sz+=2;
			t[now.R]=NODE(half+1,now.ed,sz+1,sz+2);sz+=2;
			st1.push(now.L);st1.push(now.R);
		}
		all_update();
	}
	//遅延評価対応,値の書き換え
	void segment_set(int bg,int ed,T v){
		if(!t[0].iscontain(bg,ed)){printf("query=(segment_set,%d,%d) ERROR\n",bg,ed);exit(-1);}
		auto PUSH=[&](int id,int l,int r){st1.push(id),stL.push(l),stR.push(r);};
		auto POP=[&](int& id,int &l,int &r){id=st1.top(),l=stL.top(),r=stR.top();st1.pop(),stL.pop(),stR.pop();};
		PUSH(0,bg,ed);
		while(st1.empty()==false){
			int id,L,R;
			POP(id,L,R);rollback.push(id);
			auto &now=t[id];
			lazy_update(now);
			if(now.isequal(L,R)){now.set(v);continue;}
				 if(t[now.L].iscontain(L,R))PUSH(now.L,L,R);
			else if(t[now.R].iscontain(L,R))PUSH(now.R,L,R);
			else {PUSH(now.L,L,t[now.L].ed);PUSH(now.R,t[now.R].bg,R);}
		}
		all_update();
	}
	void set(int pos,T v){
		segment_set(pos,pos,v);
	}
	void segment_add(int bg,int ed,T v){
		if(!t[0].iscontain(bg,ed)){printf("query=(segment_add,%d,%d) ERROR\n",bg,ed);exit(-1);}
		auto PUSH=[&](int id,int l,int r){st1.push(id),stL.push(l);stR.push(r);};
		auto POP=[&](int& id,int &l,int &r){id=st1.top(),l=stL.top(),r=stR.top();st1.pop(),stL.pop(),stR.pop();};
		PUSH(0,bg,ed);
		while(st1.empty()==false){
			int id,L,R;
			POP(id,L,R);rollback.push(id);
			auto &now=t[id];
			lazy_update(now);
			if(now.isequal(L,R)){now.add(v);continue;}
				 if(t[now.L].iscontain(L,R))PUSH(now.L,L,R);
			else if(t[now.R].iscontain(L,R))PUSH(now.R,L,R);
			else {PUSH(now.L,L,t[now.L].ed);PUSH(now.R,t[now.R].bg,R);}
		}
		all_update();
	}
	T get(int bg,int ed){
		T res=T();
		auto PUSH=[&](int id,int l,int r){st1.push(id),stL.push(l),stR.push(r);};
		auto POP=[&](int& id,int &l,int &r){id=st1.top(),l=stL.top(),r=stR.top(),st1.pop(),stL.pop(),stR.pop();};
		PUSH(0,bg,ed);
		while(st1.empty()==false){
			int id,L,R;
			POP(id,L,R);rollback.push(id);
			auto &now=t[id];
			if(now.isequal(L,R)){res=merge(res,now);continue;}
			lazy_update(now);
				 if(t[now.L].iscontain(L,R))PUSH(now.L,L,R);
			else if(t[now.R].iscontain(L,R))PUSH(now.R,L,R);
			else {PUSH(now.L,L,t[now.L].ed);PUSH(now.R,t[now.R].bg,R);}
		}
		all_update();
		return res;
	}
};


node<ND> _u[SEG_TREE_SIZE],_d[SEG_TREE_SIZE];
int main(){
	int res=0;
	segtree<ND> up(0,INF+1,_u);
	segtree<ND> down(0,INF+1,_d);
	int N;cin>>N;
	vector<int> Q(N);
	map<int,int> m;
	for(auto& it : Q){
		cin>>it;
		m[it]=0;
	}
	{int t=2;for(auto& it : m)it.second=t++;}

	for(auto& it : Q){
		int h=m[it];
		ND U,D;
		{
			auto u=up.get(h+1,INF-2);
			if(u.fs.first.prev!=h)U.fs.first=u.fs.first;
			else U.fs.first=u.fs.second;
			u=up.get(U.fs.first.id+1,INF-1);
			if(U.fs.first.id!=h+1)u=u+up.get(h+1,U.fs.first.id-1);
			if(u.fs.first.prev!=h)U.fs.second=u.fs.first;else U.fs.second=u.fs.second;
			U.fs.first.v++;U.fs.second.v++;
			U.fs.first.prev=U.fs.first.id;U.fs.second.prev=U.fs.second.id;
			U.fs.first.id=U.fs.second.id=h;
		}

		{
			auto d=down.get(1,h-1);
			if(d.fs.first.prev!=h)D.fs.first=d.fs.first;
			else D.fs.first=d.fs.second;
			d=down.get(0,D.fs.first.id-1);
			if(D.fs.first.id!=h-1)d=d+down.get(D.fs.first.id+1,h-1);
			if(d.fs.first.prev!=h)D.fs.second=d.fs.first;else D.fs.second=d.fs.second;
			D.fs.first.v++;D.fs.second.v++;
			D.fs.first.prev=D.fs.first.id;D.fs.second.prev=D.fs.second.id;
			D.fs.first.id=D.fs.second.id=h;
		}
		down.set(h,U);
		up.set(h,D);
		res=max(res,U.fs.first.v);
		res=max(res,D.fs.first.v);
	}
	if(res<3)cout<<0<<endl;
	else cout<<res<<endl;
}

yukicoder

結果

テストケース

ソースコード