Submission #1348550

#TimeUsernameProblemLanguageResultExecution timeMemory
1348550Adeeb_obedoBoat (APIO16_boat)C++20
100 / 100
773 ms12140 KiB
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ld   long double
#define _1 first
#define _2 second
#define yes cout<<"Yes\n"
#define nah cout<<"No\n"
#define FFF ios_base::sync_with_stdio(0);cin.tie(0);
#define ipr pair<int,int>
#define ret return
#define intt int32_t
#define mid ((l+r)/2)
#define pb push_back
#define lll __int128
using namespace std;
int tst, ts;
intt mo = 0*(998244353)+(1e9+7)*1, dx[] = {0, -1, -1, 0}, dy[] = {1, 1, 2, 0};
int mul( int x, int y ) {
    ret (int) ( (ll) x%mo * y%mo  % mo);
    ret x*y;
}
int pwo( int x, ll y ) {
    int res = 1;
    for( int i = 63; i + 1; i-- )
        res = mul( res, mul(res , ( ( 1ll << i )&y ? x : 1 )) );
    ret res;
}
int dvii( int x, int y ) {
    ret mul( x,  pwo(y,mo-2) );
}
int oo( char x , char y) {
    ret ( int )x - y;
}
int lgg( int x, int y ) {
    int u = 0;
    while( x ) {
        u++;
        x /= y;
    }
    ret u;
}//g++ -Wall -o "%e" "%f" && "./%e"
int mun( int x, int y ) {
    while( x < y )x += mo;
    ret ( x - y ) % mo;
}
int add( int x, int y ) {
    ret x + y - ( mo * ( x + y >= mo ) );
    ret x + y;
}
int lcm( int x, int y ) {
    if(x*y==0)ret max(x,y);
    int o=__gcd(x,y);
    x/=o;
    ret x*y;
}
#define endl '\n';
#define nl no*2
#define nr no*2+1
const int M =1e7+7, N = 507, P = 1e12, inf = 1e9+7 ;
int n,k,l[N],ifa[N],cn[N*4][N],cnn[N][N],ccn[N*4][N],dp[2][N],r[N],c[N*4];
vector<int>vv[N*4];
void solve(){
    cin>>n;
    set<int>st;
    vector<int>v(1,inf);
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
        st.insert(l[i]);
        st.insert(r[i]);
    }
    for(auto i:st){
        if(v.back()<i-1){
            c[v.size()]=i-v.back()-1;
            v.pb(i-1);
        }
        c[v.size()]=1;
        v.pb(i);
    }
    /// for every i:0 < i < v.size()-1 the points from v[i-1]+1 to v[i+1]-1 have the same set of intervals
    int ii=1;
    for(int i=0;i<=n;i++){
        ii=mul(ii,max(i,1));
        for(int j=0;j<=i;j++)
            cnn[i][j]=mul(ii,mul(ifa[j],ifa[i-j]));///cnn[i][j]=cnk(i,j)
    }
    for(int i=1;i<v.size();i++){
        ii=1;
        for(int j=0;j<=min(c[i],n);j++){
            ccn[i][j]=mul(ii,ifa[j]);///ccn[i][j]=cnk(c[i],j)
            ii=mul(ii,c[i]-j);
        }
        for(int j=1;j<=n;j++)
            if(l[j]<=v[i]&&v[i]<=r[j])
                vv[i].pb(j);
    }
    for(int i=1;i<v.size();i++)
        for(int j=2;j<=n && c[i]>1;j++)
            for(int p=0;p<=min(c[i],j)-2;p++){
                cn[i][j]=add(cn[i][j],mul(cnn[j-2][p],ccn[i][p+2]));
                /// p+2 is number of intervals have been chosen whith some points from v[i-1]+1 to v[i+1]-1
                /// j is maximum interval has been chosen
                /// c[i] the number of points from v[i-1]+1 to v[i+1]-1 ==>c[i]=v[i+1]-v[i-1]-1
            }
    dp[0][0]=1;
    ///dp[i][j] the number of ways to be j is maximum interval has been chosen and the point v[i] is maximum points may be chosen
    for(int i=1;i<v.size();i++){
        int o=0,kk=0;
        for(int j=0;j<=n;j++)
            dp[i%2][j]=dp[(i-1)%2][j];/// to don't chose any thing
        for(int j=1;j<=n;j++){
            o=add(o,dp[(i-1)%2][j-1]);
            if(l[j]>v[i]||v[i]>r[j])
                continue;
            while(kk<vv[i].size()&&vv[i][kk]<=j)kk++;
            dp[i%2][j]=add(dp[i%2][j],mul(c[i],o));/// to chose just the interval j
            for(int k=kk;k<vv[i].size()&&c[i]>1;k++){
                /// j is minimum interval has been chosen
                /// vv[i][k] is maximum interval has been chosen
                dp[i%2][vv[i][k]]=add(dp[i%2][vv[i][k]],mul(o,cn[i][k-kk+2]));
            }
        }
    }
    int o=0;
    for(int i=1;i<=n;i++)
        o=add(o,dp[(v.size()-1)%2][i]);
    cout<<o<<endl;
}
intt main() {
    FFF
    ifa[0]=1;
    for(int i=1;i<N;i++)
        ifa[i]=mul(dvii(1,i),ifa[i-1]);
    //freopen("7.in", "r", stdin);
    //freopen("out.txt", "w", stdout);
    tst = 1;
    //cin >> tst;
    for( ts = 1; ts <= tst; ts++ ){
        solve();
    }
}

Compilation message (stderr)

boat.cpp:60:34: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+12' to '2147483647' [-Woverflow]
   60 | const int M =1e7+7, N = 507, P = 1e12, inf = 1e9+7 ;
      |                                  ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...