Submission #1189971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189971		053thousand	Boat (APIO16_boat)	C++20	31 / 100	2098 ms	226676 KiB

boat

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,c,d,e,f[505],ans,mod=1e9+7;
vector<pair<int,int>>v;
map<int,int>ma,tema;
map<int,int>::iterator maa;
void cal(int x){
    int temp=0;
    maa=ma.begin();
    for(int i=v[x].first;i<=v[x].second;i++){
        while(maa->first<i and maa!=ma.end()){
            temp+=maa->second;
            temp=temp%mod;
            maa++;
        }
        tema[i]+=temp;
        tema[i]=tema[i]%mod;
    }
    for(maa=tema.begin();maa!=tema.end();maa++){
        ma[maa->first]+=maa->second;
        ma[maa->first]%=mod;
    }
    tema.clear();
}
signed main(){
    ma[0]=1;
    cin>>a;
    for(int i=0;i<a;i++){
        cin>>b>>c;
        v.push_back({b,c});
    }
    for(int i=0;i<a;i++){
        cal(i);
    }
    for(maa=ma.begin();maa!=ma.end();maa++){
        ans+=maa->second;
        ans=ans%mod;
    }
    cout<<ans-1;
}

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