AIM Tech Round 5 : D. Order book

これで手間取ってレート微減。
http://codeforces.com/contest/1028/problem/D

問題

株の売買を考える。
市場に人がやってきて、株の売り注文または買い注文をすることを考える。
同じ金額で売る人および買う人は最大１人ずつである。

市場に売りたい人と買いたい人が残っている場合、売りたい人の最高値より、買いたい人の最安値の方が高くなければならない。

ここで、市場の売買履歴が与えられる。
履歴は時間順に下記のいずれかを示す。

• 売りか買いかわからないが、金額pを提示した人が市場に加わった
• 売りか買いかわからないが、金額pを提示した人がもう1人現れ、かつ売買が成立した

各人の売り買いの組み合わせのうち、状態に矛盾が生じないのは何通りか。

解法

ある時刻で金額pの人が加わり、あとで金額pの売買が成立したとする。
その場合、その間金額(p+1)以上の買い注文はなく、p未満の売り注文はない。
…という事実を用いて、履歴を順に見て、各金額について、売り・買のどちらの可能性があるかを絞り込んでいく。

売買成立時点で、その金額が売り・買いどちらが先行する可能性もあるなら、解を倍々していこう。
最後売買が成立せず終了した金額群のうち、売り買いどちらも可能がケースがn通りある場合、境目は(n+1)通り考えられるので、その分解に掛け算する。

int N;
string S[404040];
int P[404040];
ll mo=1000000007;
map<int,int> m;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>S[i]>>P[i];
		m[P[i]]=3;
	}
	
	set<int> C[2],L;
	ll ret=1;
	FOR(i,N) {
		if(S[i]=="ADD") {
			L.insert(P[i]);
			C[0].insert(P[i]);
			C[1].insert(P[i]);
		}
		else {
			while(C[0].size() && *C[0].begin()<P[i]) {
				x=*C[0].begin();
				m[x]&=1;
				C[0].erase(x);
			}
			while(C[1].size() && *C[1].rbegin()>P[i]) {
				x=*C[1].rbegin();
				m[x]&=2;
				C[1].erase(x);
			}
			if(m[P[i]]==0) ret=0;
			else if(m[P[i]]==3) ret=ret*2%mo;
			
			C[0].erase(P[i]);
			C[1].erase(P[i]);
			L.erase(P[i]);
			m.erase(P[i]);
		}
	}
	
	vector<int> V;
	FORR(a,m) V.push_back(a.second);
	for(i=1;i<V.size();i++) if((V[i-1]&1)==0) V[i]&=2;
	for(i=(int)V.size()-2;i>=0;i--) if((V[i+1]&2)==0) V[i]&=1;
	int num=0;
	FORR(v,V) {
		if(v==0) ret=0;
		if(v==3) num++;
	}
	
	ret=ret*(num+1)%mo;
	
	cout<<ret<<endl;
	
}

まとめ

Eよりずっと苦戦した…。