oj.uz

Submission #558520

# Submission time Handle Problem Language Result Execution time Memory
558520 2022-05-07T13:41:53 Z hoanghq2004 Boat (APIO16_boat) C++14
0 / 100
 660 ms 5464 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 510;
const int mod = 1e9 + 7;

int n, f[N][N * 2], g[N * 2][N], C[N][N];
int L[N], R[N], cur[N], inv[N];

void add(int& a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    vector <int> dta = {0};
    for (int i = 1; i <= n; ++i) {
        cin >> L[i] >> R[i];
        --L[i];
        dta.push_back(L[i]), dta.push_back(R[i]);
    }
    sort(dta.begin(), dta.end());
    dta.erase(unique(dta.begin(), dta.end()), dta.end());
    int m = dta.size();
    C[0][0] = 1;
    for (int i = 1; i < N; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
    auto power = [&](int a, int n) {
        int ans = 1;
        for (; n; n >>= 1, a = 1LL * a * a % mod)
            if (n & 1) ans = 1LL * ans * a % mod;
        return ans;
    };
    inv[0] = 1;
    for (int i = 1, fact = 1; i <= n; ++i, fact = 1LL * fact * i % mod)
        inv[i] = power(fact, mod - 2);
    auto coef = [&](int n, int k) {
        if (k > n - k) k = n - k;
        int ans = inv[k];
        for (int i = n - k + 1; i <= n; ++i) ans = 1LL * ans * i % mod;
        return ans;
    };
    for (int i = 0; i < m; ++i) f[0][i] = 1;
    for (int s = 1; s < m; ++s) {
        int d = dta[s] - dta[s - 1];
        for (int i = 0; i <= n; ++i) cur[i] = coef(d, i);
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                add(g[s][i], 1LL * C[i - 1][j] * cur[j + 1] % mod);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < m; ++j) {
            f[i][j] = f[i][j - 1];
            if (L[i] >= dta[j] || dta[j] > R[i]) continue;
            int cnt = 0;
            for (int k = i; k > 0; --k) {
                cnt += (L[k] < dta[j] && dta[j] <= R[k]);
                add(f[i][j], 1LL * f[k - 1][j - 1] * g[j][cnt] % mod);
            }
        }
        add(ans, f[i][m - 1]);
    }
    cout << ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 5428 KB Output is correct
2 Correct 660 ms 5244 KB Output is correct
3 Correct 643 ms 5236 KB Output is correct
4 Correct 648 ms 5464 KB Output is correct
5 Correct 651 ms 5272 KB Output is correct
6 Correct 646 ms 5260 KB Output is correct
7 Correct 645 ms 5364 KB Output is correct
8 Correct 647 ms 5260 KB Output is correct
9 Correct 656 ms 5324 KB Output is correct
10 Correct 631 ms 5260 KB Output is correct
11 Correct 645 ms 5240 KB Output is correct
12 Correct 634 ms 5428 KB Output is correct
13 Correct 642 ms 5360 KB Output is correct
14 Correct 656 ms 5420 KB Output is correct
15 Correct 654 ms 5292 KB Output is correct
16 Incorrect 117 ms 3640 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 5428 KB Output is correct
2 Correct 660 ms 5244 KB Output is correct
3 Correct 643 ms 5236 KB Output is correct
4 Correct 648 ms 5464 KB Output is correct
5 Correct 651 ms 5272 KB Output is correct
6 Correct 646 ms 5260 KB Output is correct
7 Correct 645 ms 5364 KB Output is correct
8 Correct 647 ms 5260 KB Output is correct
9 Correct 656 ms 5324 KB Output is correct
10 Correct 631 ms 5260 KB Output is correct
11 Correct 645 ms 5240 KB Output is correct
12 Correct 634 ms 5428 KB Output is correct
13 Correct 642 ms 5360 KB Output is correct
14 Correct 656 ms 5420 KB Output is correct
15 Correct 654 ms 5292 KB Output is correct
16 Incorrect 117 ms 3640 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2120 KB Output is correct
2 Correct 12 ms 2132 KB Output is correct
3 Correct 12 ms 2116 KB Output is correct
4 Correct 14 ms 2132 KB Output is correct
5 Correct 16 ms 2132 KB Output is correct
6 Correct 14 ms 2120 KB Output is correct
7 Correct 13 ms 2132 KB Output is correct
8 Correct 13 ms 2160 KB Output is correct
9 Correct 14 ms 2132 KB Output is correct
10 Correct 14 ms 2132 KB Output is correct
11 Incorrect 13 ms 2116 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 5428 KB Output is correct
2 Correct 660 ms 5244 KB Output is correct
3 Correct 643 ms 5236 KB Output is correct
4 Correct 648 ms 5464 KB Output is correct
5 Correct 651 ms 5272 KB Output is correct
6 Correct 646 ms 5260 KB Output is correct
7 Correct 645 ms 5364 KB Output is correct
8 Correct 647 ms 5260 KB Output is correct
9 Correct 656 ms 5324 KB Output is correct
10 Correct 631 ms 5260 KB Output is correct
11 Correct 645 ms 5240 KB Output is correct
12 Correct 634 ms 5428 KB Output is correct
13 Correct 642 ms 5360 KB Output is correct
14 Correct 656 ms 5420 KB Output is correct
15 Correct 654 ms 5292 KB Output is correct
16 Incorrect 117 ms 3640 KB Output isn't correct
17 Halted 0 ms 0 KB -