Codeforces #679 Div1 B. Shurikens

なんで手裏剣なんだろ。
http://codeforces.com/contest/1434/problem/B

問題

店で1～N両の価格の手裏剣を1つずつ売る。
初期状態で店頭には何も並んでいない。

ここで、以下の記録が2N回分与えられる。

• 店頭に、いずれかの価格の手裏剣が1つ追加された
• 客が店頭にある最安値の手裏剣を買ったところ、x両だった

記録と矛盾しない手裏剣の追加順があれば、それを求めよ。

解法

SegTreeを使い、各手裏剣が売られたタイミングの最大値を高速に求められるようにしよう。
あるタイミングtで価格xの手裏剣が売られたとする。
もしt以前に価格x+1以上の手裏剣が売られており、その時刻の最大値がt'であるならば、(t',t)の間にその手裏剣が入荷しなければならない。

これにより、各手裏剣の入荷可能なタイミングが区間で求められる。
あとは区間スケジューリングの要領で、「入荷上限が近いものを優先的に入荷」としていくとよい。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=-1;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]); //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;


int N;
int E[202020];

int L[202020],R[202020];
int did[202020];
vector<int> add[202020];
vector<int> ret;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,2*N) {
		cin>>s;
		if(s=="-") {
			cin>>E[i];
			R[E[i]]=i;
			x=st.getval(E[i]+1,N+1);
			L[E[i]]=x+1;
			st.update(E[i],i);
			add[L[E[i]]].push_back(E[i]);
		}
	}
	
	set<pair<int,int>> S;
	FOR(i,2*N) {
		FORR(e,add[i]) S.insert({R[e],e});
		if(E[i]==0) {
			if(S.empty()) return _P("NO\n");
			auto it=S.begin();
			if(it->first<i) return _P("NO\n");
			ret.push_back(it->second);
			S.erase(S.begin());
		}
	}
	
	cout<<"YES"<<endl;
	FORR(r,ret) cout<<r<<" ";
	cout<<endl;
	
	
}

まとめ

ここら辺印象にないのか全然記憶にないな…。