Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

Codeforces #79 Div.1 B - Buses

問題文 : Buses

解法 :
各バスの出発する地点をs[i], 到着する地点をt[i]とすると
バスをt[i]について昇順にソートし、その順に番号をつけます.

i番目のバスで乗れる地点は, s[i] ≦ x < t[i]を満たす地点が到着地点となるバスj達となります.
このjたちは明らかに連続しているので、これらの範囲を満たすjたちを二分探索で求め, 区間の総数の総和はBITで管理します.
もしもn番目の地点に到着するバスがあれば、そこまでの総数を答えに含めます.

こうすることで, O(nlogn)時間でこの問題を解くことができます.


コード :

#include <cstdio>
#include <algorithm>

#define MOD (1000000007)
#define NMAX (100002)

int bit[NMAX + 1];

void add(int i, int x)
{
	while (i <= NMAX){
		bit[i] = (bit[i] + x) % MOD;
		i += (i & -i);
	}
}

int sum(int i)
{
	int r = 0;
	while (i > 0){
		r = (r + bit[i]) % MOD;
		i -= (i & -i);
	}
	return (r);
}

using namespace std;

int main(void)
{
	int n, m;
	static int s[NMAX], e[NMAX];
	static pair<int, int> pre[NMAX];
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < m; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		pre[i].first = b, pre[i].second = a;
	}
	pre[m].first = pre[m].second = 0;
	pre[m + 1].first = pre[m + 1].second = -1;
	
	sort(pre, pre + m + 2);
	
	for (int i = 0; i < m + 2; i++){
		s[i] = pre[i].second; e[i] = pre[i].first;
	}
	
	add(1, 0); add(2, 1);
	
	int ans = 0;
	for (int i = 2; i < m + 2; i++){
		add(i + 1, (sum(lower_bound(e, e + i + 1, e[i]) - e) - sum(lower_bound(e, e + i + 1, s[i]) - e) + MOD) % MOD);
		if (e[i] == n) ans = (ans + (sum(i + 1) - sum(i) + MOD) % MOD) % MOD;
	}
	
	printf("%d\n", ans);
	
	return (0);
}