oj.uz

Submission #679204

# Submission time Handle Problem Language Result Execution time Memory
679204 2023-01-07T17:13:10 Z bebra Boat (APIO16_boat) C++17
0 / 100
 2000 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;


struct Seg {
    int l;
    int r;

    bool empty() const {
        return r - l + 1 <= 0;
    }

    friend Seg intersect(const Seg& lhs, const Seg& rhs) {
        return {max(lhs.l, rhs.l), min(lhs.r, rhs.r)};
    }
};


const int MOD = 1e9 + 7;
const int INV2 = 500000004;

int add(int a, int b) {
    int res = a + b;
    if (res >= MOD) res -= MOD;
    return res;
}

int mul(long long a, int b) {
    return a * b % MOD;
}

const int MAX_N = 500 + 1;
Seg segs[MAX_N];
int dp[MAX_N];

int solve(int l, int r, int pos) {
    if (l == r) {
        return 1;
    }
    if (l > r) {
        return 0;
    }
    int res = 0;
    for (int i = pos; i >= 0; --i) {
        if (r < segs[i].l) {
            continue;
        }
        if (l > segs[i].r) {
            res = add(res, mul(dp[i], r - l + 1));
            continue;
        }
        auto [l1, r1] = intersect(Seg{l, r}, segs[i]);
        res = add(res, mul(r - r1, dp[i]));
        res = add(res, mul(solve(l1, r1, i - 1), mul(r1 - l1, INV2)));
        res = add(res, mul(solve(segs[i].l, l1 - 1, i - 1), r1 - l + 1));
    }
    return res;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> segs[i].l >> segs[i].r;
    }
    segs[0] = {-1, -1};
    dp[0] = 1;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        dp[i] = solve(segs[i].l, segs[i].r, i - 1);
        ans = add(ans, dp[i]);
    }
    cout << ans << '\n';
    return 0;
}


/*
2
3 4
1 6

*/

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -