首页 > 代码库 > codeforces 101 B. Buses

codeforces 101 B. Buses

2024-08-03 01:54:09   218人阅读

这个题目不错，但是一开始算数的时候竟然少算了一种情况导致，思路上跑偏了啊。

题目大意：给你n，m。m代表的是你有m中bus，每种bus只能从si走到ti，问你从0点到达n点可以有多少种方案可以选择。注意人只能坐车不可以走。

对于点ti来说，所有的方案就是前面的si到ti-1方案的和。这样就很简单了啊，但是数据很大需要离散化之后用线段树去维护这个区间的更新，就是需要求前面的和。

对于线段树竟然如此的生疏了，我也是醉了啊，以后得多写啊。

B. Buses
time limit per test
2 seconds
memory limit per test
265 megabytes
input
standard input
output
standard output

Little boy Gerald studies at school which is quite far from his house. That‘s why he has to go there by bus every day. The way from home to school is represented by a segment of a straight line; the segment contains exactly n?+?1 bus stops. All of them are numbered with integers from 0 to n in the order in which they follow from Gerald‘s home. The bus stop by Gerald‘s home has number 0 and the bus stop by the school has number n.

There are m buses running between the house and the school: the i-th bus goes from stop si to ti (si?<?ti), visiting all the intermediate stops in the order in which they follow on the segment. Besides, Gerald‘s no idiot and he wouldn‘t get off the bus until it is still possible to ride on it closer to the school (obviously, getting off would be completely pointless). In other words, Gerald can get on the i-th bus on any stop numbered from si to ti?-?1 inclusive, but he can get off the i-th bus only on the bus stop ti.

Gerald can‘t walk between the bus stops and he also can‘t move in the direction from the school to the house.

Gerald wants to know how many ways he has to get from home to school. Tell him this number. Two ways are considered different if Gerald crosses some segment between the stops on different buses. As the number of ways can be too much, find the remainder of a division of this number by 1000000007 (109?+?7).

Input

The first line contains two space-separated integers: n and m (1?≤?n?≤?109,?0?≤?m?≤?105). Then follow m lines each containing two integers si,?ti. They are the numbers of starting stops and end stops of the buses (0?≤?si?<?ti?≤?n).

Output

Print the only number — the number of ways to get to the school modulo 1000000007 (109?+?7).

Sample test(s)
input
2 2
0 1
1 2
output
1
input
3 2
0 1
1 2
output
0
input
5 5
0 1
0 2
0 3
0 4
0 5
output
16
Note

The first test has the only variant to get to school: first on bus number one to the bus stop number one; then on bus number two to the bus stop number two.

In the second test no bus goes to the third bus stop, where the school is positioned. Thus, the correct answer is 0.

In the third test Gerald can either get or not on any of the first four buses to get closer to the school. Thus, the correct answer is 24?=?16.

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-8
#define M 1000100
#define LL long long
//#define LL long long
#define INF 0x3f3f3f
#define PI 3.1415926535898
#define mod 1000000007


const int maxn = 1000010;

using namespace std;

struct node
{
    int l, r;
    LL num;
}f[maxn];

struct node1
{
    LL x, y;
}p[maxn];
LL dx[maxn];
LL dy[maxn];
LL Max;
int ans;
int xans;

bool cmp(node1 a, node1 b)
{
    return a.y < b.y;
}

int Find(LL x)
{
    int l = 0;
    int r = xans-1;
    while(l <= r)
    {
        int mid = (l+r)>>1;
        if(dy[mid] == x) return mid;
        else if(dy[mid] > x) r = mid-1;
        else l = mid+1;
    }
    return -1;
}


void Bulid(int l, int r, int site)
{
    f[site].l = l;
    f[site].r = r;
    f[site].num = 0LL;
    if(l == r)
    {
        ///if(l == 0) f[site].num = 1LL;
        return;
    }
    int mid = (l+r)>>1;
    Bulid(l, mid, site<<1);
    Bulid(mid+1, r, site<<1|1);
}

LL Query(int l, int r, int site)
{
    if(f[site].l == l && f[site].r == r) return f[site].num;
    int mid = (f[site].l+f[site].r)>>1;
    if(r <= mid) return Query(l, r, site<<1);
    else if(l > mid) return Query(l, r, site<<1|1);
    else
    {
        LL x1 = Query(l, mid, site<<1)%mod;
        LL x2 =  Query(mid+1, r, site<<1|1)%mod;
        return (x1+x2)%mod;
    }
}

void Updata(int site, int m, LL d)
{
    if(f[site].l == f[site].r && f[site].l == m)
    {
        f[site].num += d;
        return;
    }
    int mid = (f[site].l+f[site].r)>>1;
    if(m <= mid) Updata(site<<1, m, d);
    else Updata(site<<1|1, m, d);
    f[site].num += d;
}


void cha(int x, int site)
{
    if(f[site].l == f[site].r && f[site].l == x)
    {
        Max = f[site].num;
        return;
    }
    int mid = (f[site].l+f[site].r)>>1;
    if(x <= mid) cha(x, site<<1);
    else cha(x, site<<1|1);
}

int main()
{
    int n, m;
    while(~scanf("%d %d",&n, &m))
    {
        ans = 0;
        for(int i = 0; i < m; i++)
        {
            scanf("%I64d %I64d",&p[i].x, &p[i].y);
            dx[ans++] = p[i].x;
            dx[ans++] = p[i].y;
        }
        dx[ans++] = n;
        sort(dx, dx+ans);
        sort(p, p+m, cmp);
        xans = 0;
        for(int i = 0; i < ans; i++)
            if(xans == 0 || dy[xans-1] != dx[i]) dy[xans++] = dx[i];
        if(dy[0] != 0)
        {
            cout<<0<<endl;
            continue;
        }
        Bulid(0, xans-1, 1);
        Updata(1, 0, 1);
        for(int i = 0; i < m; i++)
        {
            int x = Find(p[i].x);
            int y = Find(p[i].y);
            LL xx = Query(x, y-1, 1);
            ///cout<<"xx = "<<xx<<endl;
            xx %= mod;
            Updata(1, y, xx);
        }
        int nx = Find(n);
        cha(nx, 1);
        cout<<Max%mod<<endl;
    }
    return 0;
}


codeforces 101 B. Buses


联系
我们