Submission #361306

#	Time	Username	Problem	Language	Result	Execution time	Memory
361306		tuank99lhp	Boat (APIO16_boat)	C++17	100 / 100	793 ms	12396 KiB

boat

#include <bits/stdc++.h>

using namespace std;
vector<long long> v;
vector<pair<long long,long long> > V;
int n,l[505],r[505],F[2][2005][505],mod,tinh[505],tinh2[2005][505];
long long lt(long long x,long long y)
{
    if (y==0) return 1;
    long long k=lt(x,y/2);
    if (y%2) return k*k%mod*x%mod;
             return k*k%mod;
}
int main()
{
  //  freopen("a.inp","r",stdin);
   // freopen("a.out","w",stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;++i)
    {
        cin>>l[i]>>r[i];
        v.push_back(l[i]);
        v.push_back(r[i]);
    }
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());

    long long ct=1;
    for (int i=0;i<v.size();++i)
    {
        if (ct<v[i]) V.push_back({ct,v[i]-ct});
        ct=v[i]+1;
        V.push_back({v[i],1});
    }

    for (int i=0;i<V.size();++i) F[0][i][0]=1;
    F[1][0][0]=1;

    ct=0;mod=1e9+7;
    for (int i=1;i<=500;++i) tinh[i]=lt(i,mod-2);

    for (int j=0;j<V.size();++j)
     for (int k=1;k<=n;++k) tinh2[j][k]=tinh[k]*(V[j].second-k+1)%mod;

    for (int i=1;i<=n;++i)
    {
        ct=1-ct;
        pair<long long,long long> X={l[i],0LL};
        l[i]=lower_bound(V.begin(),V.end(),X)-V.begin();
        X={r[i],0LL};
        r[i]=lower_bound(V.begin(),V.end(),X)-V.begin();
        for (int j=0;j<V.size();++j)
        {
            if (j) F[ct][j][0]=0;

            if (j) for (int k=0;k<=min(1LL*i,V[j-1].second);++k)
            {
                    if (F[ct][j-1][k]==0 && F[ct][j-1][k+1]==0) break;

                    F[ct][j][0]+=F[ct][j-1][k];
                    if (F[ct][j][0]>=mod) F[ct][j][0]-=mod;

            }

                for (int k=1;k<=min(1LL*i,V[j].second);++k)
                {
                    if (F[1-ct][j][k-1]==0 && F[1-ct][j][k]==0) break;
                    F[ct][j][k]=F[1-ct][j][k];

                    if (j>=l[i] && j<=r[i])
                    {
                        long long X=F[1-ct][j][k-1];
                        X=X*tinh2[j][k]%mod;
                        F[ct][j][k]+=X;
                        if (F[ct][j][k]>=mod) F[ct][j][k]-=mod;
                    }

                }


            }
        }


    long long kq=mod-1;

     for (int k=0;k<=n;++k) {kq=(kq+F[ct][V.size()-1][k]);if (kq>=mod) kq-=mod;}
    cout<<kq;

    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'long long int lt(long long int, long long int)':
boat.cpp:11:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   11 |     if (y%2) return k*k%mod*x%mod;
      |     ^~
boat.cpp:12:14: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   12 |              return k*k%mod;
      |              ^~~~~~
boat.cpp: In function 'int main()':
boat.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i=0;i<v.size();++i)
      |                  ~^~~~~~~~~
boat.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i=0;i<V.size();++i) F[0][i][0]=1;
      |                  ~^~~~~~~~~
boat.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int j=0;j<V.size();++j)
      |                  ~^~~~~~~~~
boat.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int j=0;j<V.size();++j)
      |                      ~^~~~~~~~~

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