Submission #730851

#	Time	Username	Problem	Language	Result	Execution time	Memory
730851		bgnbvnbv	Boat (APIO16_boat)	C++14	100 / 100	460 ms	6356 KiB

boat

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pll pair<int,int>
#define fi first
#define se second
const int mod=(int)1e9+7;
const int maxn=2*505;
int sz,a[maxn],b[maxn];
vector<int>v,s;
int n;
vector<pll>block;
int val[maxn][maxn];
int cnt[maxn];
int add[maxn];
int chia[maxn];
int pw(int x,int y)
{
    if(y==0) return 1;
    int x1=pw(x,y/2);
    x1=x1*x1%mod;
    if(y&1) x1=x1*x%mod;
    return x1;
}
int pre[maxn];
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i] >> b[i];
        v.push_back(a[i]-1);
        v.push_back(b[i]);
    }
    for(int i=1;i<=n;i++) chia[i]=pw(i,mod-2);
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
    {
        if(i==0||v[i]!=v[i-1]) s.push_back(v[i]);
    }
    swap(v,s);
    for(int i=0;i<v.size();i++)
    {
        if(i==0) block.push_back({0,v[i]});
        else block.push_back({v[i-1]+1,v[i]});
    }
    for(int i=0;i<block.size();i++) pre[i]=1;
    int tt=0,valcu;
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(block.begin(),block.end(),(pll){a[i]+1,0ll})-block.begin()-1;
        b[i]=lower_bound(block.begin(),block.end(),(pll){b[i]+1,0ll})-block.begin()-1;
        for(int j=a[i];j<=b[i];j++)
        {
            cnt[j]++;
            val[j][cnt[j]]=pre[j-1];
            for(int k=1;k<=cnt[j];k++)
            {
                tt=cnt[j]-k+1;
                valcu=val[j][k]*(block[j].se-block[j].fi)%mod*chia[tt]%mod;
                val[j][k]+=valcu;
                if(k==cnt[j]) valcu=0;
                if(val[j][k]>=mod) val[j][k]-=mod;
                add[j]+=valcu;
                if(add[j]>=mod) add[j]-=mod;
            }
            add[j]+=val[j][cnt[j]];
            if(add[j]>=mod) add[j]-=mod;
        }
        for(int j=1;j<block.size();j++)
        {
            add[j]+=add[j-1];
            if(add[j]>=mod) add[j]-=mod;
            pre[j]+=add[j];
            if(pre[j]>=mod) pre[j]-=mod;
        }
        for(int j=1;j<block.size();j++) add[j]=0;
    }
    cout << (pre[block.size()-1]-1+mod)%mod;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:40:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
boat.cpp:45:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
boat.cpp:50:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0;i<block.size();i++) pre[i]=1;
      |                 ~^~~~~~~~~~~~~
boat.cpp:73:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int j=1;j<block.size();j++)
      |                     ~^~~~~~~~~~~~~
boat.cpp:80:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int j=1;j<block.size();j++) add[j]=0;
      |                     ~^~~~~~~~~~~~~

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