Submission #984140

#	Time	Username	Problem	Language	Result	Execution time	Memory
984140		Aiperiii	Boat (APIO16_boat)	C++14	9 / 100	2063 ms	15708 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;
int f(int n){
    return ((n*(n+1))/2)%mod;
}
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    vector <int> a(n+1),b(n+1);
    map <int,int> ed;
    set <int> v;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        v.insert(a[i]);
        v.insert(b[i]);
        ed[b[i]]++;
    }
    int p=-1,ls=-1;
    vector <pair <int,int> > r;
    for(auto x : v){
        ls=x;
        if(p!=-1 && x-1>=p)r.pb({p,x-1});
        if(ed[x]){
            r.pb({x,x});
            p=x+1;
        }
        else p=x;
    }
    if(p==ls)r.pb({p,p});
    //for(auto x : r)cout<<x.ff<<" "<<x.ss<<"\n";
    
    vector <vector <int> > val(n+1,vector <int> (r.size())),cnt(n+1,vector <int> (r.size())),add(n+1,vector <int> (r.size()));
    for(int i=1;i<=n;i++){
        for(int j=0;j<r.size();j++){
            if(a[i]<=r[j].ff && r[j].ss<=b[i]){
                cnt[i][j]=r[j].ss-r[j].ff+1;
                val[i][j]=1;
            }
            //cout<<cnt[i][j]<<" ";
        }
      //  cout<<"\n";
    }
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<r.size();j++){
            if(a[i]<=r[j].ff && r[j].ss<=b[i]){
                for(int k=1;k<i;k++){
                    for(int q=0;q<j;q++){
                        val[i][j]+=val[k][q]*cnt[k][q];
                        val[i][j]%=mod;
                        val[i][j]+=add[k][q];
                        val[i][j]%=mod;
                    }
                    if(cnt[i][j]){
                        add[i][j]+=val[k][j]*f(cnt[i][j]-1);
                        add[i][j]%=mod;
                    }
                }
            }
        }
    }
    int ans=0;
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<r.size();j++){
            ans+=val[i][j]*cnt[i][j];
            ans%=mod;
            ans+=add[i][j];
            ans%=mod;
            //cout<<val[i][j]<<" ";
        }
        //cout<<"\n";
    }
    cout<<ans<<"\n";
}
/*
 3
 1 10
 3 10
 8 15
 
2
1 2
2 3
*/

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:42: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]
   42 |         for(int j=0;j<r.size();j++){
      |                     ~^~~~~~~~~
boat.cpp:53: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]
   53 |         for(int j=0;j<r.size();j++){
      |                     ~^~~~~~~~~
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=0;j<r.size();j++){
      |                     ~^~~~~~~~~

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