Submission #38780

#TimeUsernameProblemLanguageResultExecution timeMemory
38780WaschbarBoat (APIO16_boat)C++14
9 / 100
2000 ms291236 KiB
#include <bits/stdc++.h>
#define a first
#define b second
using namespace std;

const long long INF = 1e18;
const int MOD = 1e9+7;

int n;
vector < map<int,int> > dp(1000);
vector < pair<int,int> > v(1000);

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> v[i].a >> v[i].b;

    map<int,int> :: iterator it;
    for(int i = 1; i <= n; i++){
        for(it = dp[i-1].begin(); it != dp[i-1].end(); it++)
            dp[i][it->first] = it->second;

        it = dp[i-1].begin();
        int x = v[i].a;
        int cnt = 0;
        while(it != dp[i-1].end()) {
            if(it->first >= x) break;
            dp[i][x] = (dp[i][x] + it->second) % MOD;
            cnt = (cnt + it->second) % MOD;
            it++;
        }
        //if(it != dp[i-1].end())
        //    it++;

        for(int j = v[i].a+1; j <= v[i].b; j++){
            dp[i][j] = (dp[i][j] + cnt) % MOD;
            if(it != dp[i-1].end() && it->first < j){
                dp[i][j] = (dp[i][j] + it->second) % MOD;
                cnt = (cnt + it->second) % MOD;
                it++;
            }
        }

        for(int j = v[i].a; j <= v[i].b; j++)
            dp[i][j] = (dp[i][j]+1) % MOD;

    }

    it = dp[n].begin();
    int ans = 0;
    while(it != dp[n].end()) {
        ans = (ans+(it->second)) % MOD;
        //cout << it->second <<" "<<dp[1][it->first]<< " - " << it->first << endl;
        it++;
    }

    cout << ans;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...