Submission #1227068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227068		cpdreamer	Boat (APIO16_boat)	C++20	27 / 100	13 ms	4160 KiB

boat

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = 1e9+7;
#define F first
#define pb push_back
#define S second
#define P pair
#define V vector
#define all(v) v.begin(), v.end()
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
void file() {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
}
ll add(ll a,ll b) {
    return ((a%MOD)+(b%MOD))%MOD;
}
ll mul(ll a,ll b) {
    return ((a%MOD)*(b%MOD))%MOD;
}
ll md(ll a) {
    return ((a%MOD)+MOD)%MOD;
}
ll dif(ll a,ll b) {
    return md(md(a)-md(b));
}
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
ll mod_inv(ll a) {
    return binpow(a,MOD-2,MOD)%MOD;
}
ll inv[501];
ll v[501][501];
ll dp[501][501];
ll p(ll a,ll b) {
    ll x=1;
    for (ll i=a+1;i<=b;i++) {
        x=mul(x,i);
    }
    return x;
}
ll f(int n,ll A[],ll B[]) {
    for (ll i=1;i<=n;i++) {
        inv[i]=mod_inv(i);
    }
    V<ll>vp;
    V<ll>l,r;
    for (int i=0;i<n;i++) {
        vp.pb(A[i]);
        vp.pb(B[i]);
    }
    sort(all(vp));
    auto it=unique(all(vp));
    vp.resize(distance(vp.begin(),it));
    for (int i=0;i<(int)vp.size()-1;i++) {
        l.pb(vp[i]),r.pb(vp[i]);
        if (vp[i]+1<=vp[i+1]-1) {
            l.pb(vp[i]+1),r.pb(vp[i+1]-1);
        }
    }
    l.pb(vp[(int)vp.size()-1]);
    r.pb(vp[(int)vp.size()-1]);
    int m=(int)l.size();
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (A[i]<=l[j] && r[j]<=B[i]) {
                v[i][j]=1;
            }
            else
                v[i][j]=0;
        }
    }
    ll x[n+1];
    for (int j=0;j<m;j++) {
        ll L=r[j]-l[j]+1;
        x[0]=L;
        for (int i=1;i<=n;i++) {
            x[i]=x[i-1];
            x[i]=mul(x[i],i+L);
            x[i]=mul(x[i],inv[i+1]);
        }
        if (v[0][j]==1) {
            dp[0][j]=(r[j]-l[j]+1)%MOD;
        }
        else {
            dp[0][j]=0;
        }
        if (j>0) {
            dp[0][j]=add(dp[0][j],dp[0][j-1]);
        }
        for (int  i=1;i<n;i++) {
            int c=0;
            dp[i][j]=0;
            if (v[i][j]==1) {
                for (int g=i-1;g>=0;g--) {
                    if (j>0) {
                        dp[i][j]=add(dp[i][j],mul(dp[g][j-1],x[c]));
                    }
                    if (v[g][j]==1) {
                        c++;
                    }
                }
                dp[i][j]=add(dp[i][j],x[c]);
            }
            if (j>0) {
                dp[i][j]=add(dp[i][j],dp[i][j-1]);
            }
        }
    }
    ll ans=0;
    for (int i=0;i<n;i++) {
        ans=add(ans,dp[i][m-1]);
    }
    return ans;
}
ll g(int n,ll A[],ll B[]) {
    V<ll>dp1[n];
    for (ll i=0;i<B[0]-A[0]+1;i++) {
        dp1[0].pb(i+1);
    }
    for (ll i=1;i<n;i++) {
        for (ll j=0;j<B[i]-A[i]+1;j++) {
            ll x=1;
            for (ll g=i-1;g>=0;g--) {
                if (j+A[i]<=A[g]) {
                    continue;
                }
                x=add(x,dp1[g][min(B[g]-A[g],j+A[i]-1-A[g])]);
            }
            dp1[i].pb(x);
        }
        for (ll j=1;j<B[i]-A[i]+1;j++) {
            dp1[i][j]=add(dp1[i][j],dp1[i][j-1]);
        }
    }
    ll ans=0;
    for (ll i=0;i<n;i++) {
        ans=add(ans,dp1[i][B[i]-A[i]]);
    }
    return ans;
}
void solve() {
    int n;
    cin>>n;
    ll A[n],B[n];
    for (int i=0;i<n;i++) {
        cin>>A[i]>>B[i];
    }
    cout<<f(n,A,B)<<endl;
}

void generate() {
    for (int t=0;t<100;t++) {
        int n=(rand()%(int)10)+1;
        if (n>4 )continue;
        ll A[n],B[n];
        for (int i=0;i<n;i++) {
            A[i]=rand()%(int)7;
            B[i]=A[i]+rand()%(int)7;
        }
        if (f(n,A,B)!=g(n,A,B)) {
            cout<<n<<endl;
            for (int i=0;i<n;i++) {
                cout<<A[i]<<" "<<B[i]<<endl;
            }
            cout<<"Output: "<<f(n,A,B)<<endl;
            cout<<"Correct: "<<g(n,A,B)<<endl;
            break;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //file();
    solve();
    //generate();
}

Compilation message (stderr)

boat.cpp: In function 'void file()':
boat.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen("output.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42