WUPC2nd H - ダイヤグラム

問題

日本語なので本文参照（http://wupc2nd.contest.atcoder.jp/tasks/wupc_08）

制約条件

駅の数≦100000
電車の台数≦200

方針

実質的に考える必要がある駅は電車の両端の駅だけなので、最大でも400個。
なので座標圧縮する。

ひとつの電車でのみカバーされている駅の右端をx
二つ以上の電車でカバーされている駅の右端をyとしたとき、（y≦x）
dp[y][x]:=その区間がカバーされている場合の数
を更新していくようなdpをすれば、O(n^3)で答えが求まる。

dpの更新順序に気をつける必要がある。
（同じ電車を二度使わないように、電車→区間1（右から）→区間2（左から）の順でループをまわす）

ソースコード

const int mod = (int)1e9 + 7;
int n, m;
pi in[200];
ll dp[410][410];
 
int main(){
	cin >> n >> m;
	vi vs;
	vs.pb(1);
	vs.pb(n + 1);
	rep(i, m){
		cin >> in[i].first >> in[i].second;
		vs.pb(in[i].first);
		vs.pb(in[i].second + 1);
	}
	sort(in, in + m);
	sort(all(vs));
	vs.erase(unique(all(vs)), vs.end());
	rep(i, m){
		in[i].first = lower_bound(all(vs), in[i].first) - vs.begin();
		in[i].second = lower_bound(all(vs), in[i].second + 1) - vs.begin();
	}
	
	
	dp[0][0] = 1;
	rep(i, m) for(int p1 = vs.size() - 1; p1 >= 0; p1--)
	for(int p2 = p1; p2 >= 0; p2--) if(dp[p1][p2]){
		if(in[i].first > p2) continue;
		int np2 = max(p2, min(p1, in[i].second));
		int np1 = max(p1, in[i].second);
		
		(dp[np1][np2] += dp[p1][p2]) %= mod;
	}
	cout << dp[vs.size() - 1][vs.size() - 1] << endl;
	
	return 0;
}