Submission #971803

#	Time	Username	Problem	Language	Result	Execution time	Memory
971803		Aiperiii	Boat (APIO16_boat)	C++14	0 / 100	523 ms	524288 KiB

boat

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int mod=1e9+7;
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    vector <int> a(n),b(n);
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
    }
    vector <pair <int,int> > v1,v2;
    v1.pb({0,1});
    for(int i=a[0];i<=b[0];i++)v1.pb({i,1});
    for(int i=1;i<v1.size();i++)v1[i].ss+=v1[i-1].ss;
    
    //for(auto x : v1)cout<<x.ff<<" "<<x.ss<<"\n";
    for(int i=1;i<n;i++){
        pair <int,int> p={a[i],0};
        auto it=lower_bound(all(v1),p);
        int pos=it-v1.begin();
        pos--;
        v2.pb({0,v1.back().ss});
        for(int j=a[i];j<=b[i];j++){
            if(pos>=v1.size())pos=v1.size()-1;
            v2.pb({j,v1[pos].ss});
            pos++;
        }
        swap(v1,v2);
        if(i!=n-1){
            for(int j=1;j<v1.size();j++){
                v1[j].ss+=v1[j-1].ss;
                v1[j].ss%=mod;
            }
        }
        
        v2.clear();
    }
    int res=-1;
    for(auto x : v1){
        res+=x.ss;res%=mod;
    }
    cout<<res<<"\n";
}
/*
 5 3
 4 6
 9 1
 8 8
 4 2
 3 7
 8
 2
 9
 
 2
 1 2
 2 3
 
*/

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:21: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]
   21 |     for(int i=1;i<v1.size();i++)v1[i].ss+=v1[i-1].ss;
      |                 ~^~~~~~~~~~
boat.cpp:31:19: 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]
   31 |             if(pos>=v1.size())pos=v1.size()-1;
      |                ~~~^~~~~~~~~~~
boat.cpp:37:26: 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]
   37 |             for(int j=1;j<v1.size();j++){
      |                         ~^~~~~~~~~~

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