Submission #730753

#	Time	Username	Problem	Language	Result	Execution time	Memory
730753		bgnbvnbv	Boat (APIO16_boat)	C++14	31 / 100	396 ms	524288 KiB

boat

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int mod=(int)1e9+7;
const int maxn=505;
int sz,a[maxn],b[maxn];
vector<int>v,s;
int bit[1000005];
void update(int pos,int val)
{
    while(pos<=sz)
    {
        bit[pos]+=val;
        if(bit[pos]>=mod) bit[pos]-=mod;
        pos+=pos&(-pos);
    }
}
int get(int pos)
{
    int ans=0;
    while(pos>0)
    {
        ans+=bit[pos];
        if(ans>=mod) ans-=mod;
        pos-=(pos&(-pos));
    }
    return ans;
}
int n;
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];
        for(int j=a[i];j<=b[i];j++) v.push_back(j);
    }
    sort(v.begin(),v.end());
    s.push_back(-1);
    s.push_back(0);
    for(int i=0;i<v.size();i++)
    {
        if(i==0||v[i]!=v[i-1]) s.push_back(v[i]);
    }
    swap(v,s);
    sz=v.size()-1;
    update(1,1);
    for(int i=1;i<=n;i++)
    {
        int l=lower_bound(v.begin(),v.end(),a[i])-v.begin();
        int r=lower_bound(v.begin(),v.end(),b[i])-v.begin();
        for(int j=r;j>=l;j--)
        {
            update(j,get(j-1));
        }
    }
    cout << (get(sz)-1+mod)%mod;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:43: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]
   43 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~

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