oj.uz

Submission #971803

# Submission time Handle Problem Language Result Execution time Memory
971803 2024-04-29T10:35:04 Z Aiperiii Boat (APIO16_boat) C++14
0 / 100
 523 ms 524288 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 523 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -