2015年2月8日 星期日

Codechef February Challenge 2015 Time to Study Graphs with Chef

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

#define MOD (int)(1e9+7)

typedef long long ll;

typedef pair<ll, ll> LR;
#define l first
#define r second

struct pr
{
    ll l, i, r, j;
    pr(){}
    pr(ll _l, ll _i, ll _r, ll _j)
    {
        l = _l; i = _i; r = _r; j = _j;
    }

    bool operator<(const pr &p) const
    {
        return r < p.r;
    }
}lr[100000];

ll pwd(ll x, ll n)
{
    if( n <= 0 ) return 1;

    ll p = pwd(x, n/2);

    if( n&1 ) return p*p%MOD*x%MOD;
    else return p*p%MOD;
}

ll N, M, K;
map<ll, ll> m;
map<LR, ll> p;

typedef map<ll, ll>::iterator mit;

ll ask(ll x)
{
    if( m.find(x) == m.end() )
    {
        mit it = --m.upper_bound(x);
        m[x] = it->second*pwd(M, x-it->first)%MOD;
    }

    return m[x];
}

ll ask(ll x, ll y)
{
    LR t = LR(x, y);

    if( p.find(t) == p.end() )
    {
        mit it = --m.lower_bound(x);
        p[t] = it->second*pwd(M, x-it->first-1)%MOD;
    }

    ask(x);

    return p[t];
}

int main()
{
    scanf("%lld %lld %lld", &N, &M, &K);

    for(int Ki = 0; Ki < K; Ki++)
        scanf("%lld %lld %lld %lld", &lr[Ki].l, &lr[Ki].i, &lr[Ki].r, &lr[Ki].j);

    sort(lr, lr+K);

    ll Ans = pwd(M, N);
    m[-1] = 1;
    m[0] = 1;

    for(int Ki = 0; Ki < K; Ki++)
    {
        ll l = lr[Ki].l, i = lr[Ki].i, r = lr[Ki].r, j = lr[Ki].j;

        Ans += ask(l, i)*pwd(M, N-r)%MOD;
        Ans %= MOD;

        ask(r);
        ask(r, j);

        m[r] += ask(l, i); m[r] %= MOD;
        p[LR(r, j) ] += ask(l, i); p[LR(r, j) ] %= MOD;
    }

    printf("%lld\n", Ans);
}

沒有留言:

張貼留言