제출 #1340133

#제출 시각아이디문제언어결과실행 시간메모리
1340133fatelessBoat (APIO16_boat)C++20
31 / 100
686 ms589824 KiB
// #pragma GCC optimize("O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
#define speedup cin.tie(0)->sync_with_stdio(0);
#define bitcount __builtin_popcount
#define all(x) begin(x), end(x)
#define int long long
#define pb push_back
#define vc vector

const int mod = 1e9 + 7;

inline bool chmax (int &a, int b) {if (a < b) {a = b; return 1;} return 0;}
inline void add (int &a, int b) {a += b; if (a >= mod) a -= mod;}
inline void solve() {
    int n; cin >> n;
    vc<int> l (n + 1), r (n + 1), t;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        for (int x = l[i]; x <= r[i]; x++) t.pb(x);
    }

    sort(all(t));
    t.erase(unique(all(t)), end(t));

    int m = t.size();
    for (int i = 1; i <= n; i++) {
        l[i] = upper_bound(all(t), l[i]) - begin(t);
        r[i] = upper_bound(all(t), r[i]) - begin(t);
    }

    vc<int> dp (m + 1); dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        int sum = 1;
        for (int x = 1; x <= r[i]; x++) {
            int val = dp[x];
            if (l[i] <= x) add(dp[x], sum);
            add(sum, val);
        }
    }

    int ans = 0;
    for (int x = 1; x <= m; x++) add(ans,  dp[x]);

    cout << ans;
}

signed main() {
    speedup;
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...