oj.uz

답안 #110905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
110905 2019-05-13T05:21:32 Z TAISA_ Boat (APIO16_boat) C++14
0 / 100
 15 ms 8448 KB 
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr double eps = 1e-9;
constexpr ll MOD = 1000000007LL;
template <typename T>
bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for(int i = 0; i < v.size(); i++) {
        os << v[i] << (i + 1 == v.size() ? "\n" : " ");
    }
    return os;
}
template <typename T>
vector<T> make_v(size_t a) {
    return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) {
    t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) {
    for(auto& e : t) {
        fill_v(e, v);
    }
};
ll mpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1){
            res=res*x%MOD;
        }
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin>>n;
    vector<ll> a(n+1),b(n+1),v,inv(n+10);
    v.push_back(0);
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        v.push_back(a[i]);
        v.push_back(b[i]+1);
    }
    for(int i=1;i<=n;i++){
        inv[i]=mpow(i,MOD-2LL);
    }
    v.push_back(0);
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(all(v),a[i])-v.begin();
        b[i]=lower_bound(all(v),b[i]+1)-v.begin()-1;
    }
    int m=v.size();
    auto dp=make_v<ll>(n+10,m+10);
    auto sum=make_v<ll>(n+10,m+10);
    dp[0][0]=1;
    for(int j=0;j<=m;j++){
        sum[0][j]=1;
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=a[i];j<=b[i];j++){
            ll c=v[j+1]-v[j],x=v[j+1]-v[j],y=1;
            for(int k=i-1;k>=0;k--){
                dp[i][j]+=c*sum[k][j-1]%MOD;
                dp[i][j]%=MOD;
                if(a[k]<=j&&j<=b[k]){
                    c*=(x+1LL)*inv[y+1]%MOD;
                    c%=MOD;
                    x++;
                    y++;
                }
            }
            ans%=MOD;
        }
        sum[i][0]=dp[i][0];
            for(int j=1;j<=m;j++){
                sum[i][j]=sum[i][j-1]+dp[i][j];
                sum[i][j]%=MOD;
            }
            ans+=sum[i][m];
    }
    cout<<ans<<endl;
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8448 KB Output is correct
2 Correct 14 ms 8448 KB Output is correct
3 Correct 15 ms 8448 KB Output is correct
4 Incorrect 15 ms 8448 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8448 KB Output is correct
2 Correct 14 ms 8448 KB Output is correct
3 Correct 15 ms 8448 KB Output is correct
4 Incorrect 15 ms 8448 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8448 KB Output is correct
2 Correct 14 ms 8448 KB Output is correct
3 Correct 15 ms 8448 KB Output is correct
4 Incorrect 15 ms 8448 KB Output isn't correct
5 Halted 0 ms 0 KB -