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); }