oj.uz

Submission #679199

# Submission time Handle Problem Language Result Execution time Memory
679199 2023-01-07T17:08:09 Z bebra Boat (APIO16_boat) C++17
9 / 100
 2000 ms 10852 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];

map<tuple<int, int, int>, int> mem;


int solve(int l, int r, int pos) {
    if (mem.find({l, r, pos}) != mem.end()) {
        return mem.at({l, r, pos});
    }
    if (r - l + 1 <= 0) {
        mem[{l, r, pos}] = 0;
        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));
    }
    mem[{l, r, pos}] = res;
    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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 2 ms 340 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Execution timed out 2080 ms 10852 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Execution timed out 2080 ms 10852 KB Time limit exceeded
22 Halted 0 ms 0 KB -