제출 #1340184

#제출 시각아이디문제언어결과실행 시간메모리
1340184fatelessBoat (APIO16_boat)C++20
0 / 100
1 ms344 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, inf = 1e18;

inline bool chmax (int &a, int b) {if (a < b) {a = b; return 1;} return 0;}
inline void add (int &a, int b) {a = (a + b) % 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];
        t.pb(l[i]);
        t.pb(r[i]);
    }
    t.pb(inf);
    sort(all(t));
    t.erase(unique(all(t)), end(t));
    for (int i = 1; i <= n; i++) {
        l[i] = lower_bound(all(t), l[i]) - begin(t);
        r[i] = upper_bound(all(t), r[i]) - begin(t);
    }

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

    int ans = 0;
    for (int x : dp) add(ans, 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...