oj.uz

Submission #939715

# Submission time Handle Problem Language Result Execution time Memory
939715 2024-03-06T16:55:56 Z sysia Boat (APIO16_boat) C++17
31 / 100
 1316 ms 15712 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7;
const int mod = 1e9+7;
const int I = (mod+1)/2;

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

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

int add2(int a, int b){
    a += b;
    if (a >= mod) a-=mod;
    return a;
}

int power(int a, int b){
    if (!b) return 1ll;
    int k = power(a, b/2);
    k = mul(k, k);
    if (b&1) k = mul(k, a);
    return k;
}

void solve(){
    int n; cin >> n;
    vector<int>a(n+1), b(n+1);
    vector<int>s = {0, 1};
    for (int i = 1; i<=n; i++) {
        cin >> a[i] >> b[i];
        s.emplace_back(a[i]);
        s.emplace_back(b[i]);
    }
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    debug(s);
    vector<T>seg;
    for (int i = 0; i<(int)s.size()-1; i++){
        seg.emplace_back(s[i], s[i]);
        if (s[i]+1 <= s[i+1]-1) seg.emplace_back(s[i]+1, s[i+1]-1);
    }
    seg.emplace_back(s.back(), s.back());
    debug(seg);
    int t = 2*n+2;
    vector<int>f(t, 1), inv(t, 1);
    for (int i = 1; i<t; i++){
        f[i] = mul(f[i-1], i);
        inv[i] = mul(inv[i-1], power(i, mod-2));
    }
    auto nck = [&](int N, int K){
        if (N < 0 || K < 0 || N < K) return 0ll;
        return mul(f[N], mul(inv[K], inv[N-K]));
    };
    int m = (int)seg.size();
    //dp[i][j][k] = na ile sposobow da sie wybrac dzialajace rozwiazanie na prefiksie i, gdzie 
    //ostatnie k elementow nalezy do przedzialu seg[j]
    vector dp(m, vector<int>(n+1, 0));
    dp[0][1] = 1; //zerowy przedzial
    for (int i = 1; i<=n; i++){
        auto new_dp = dp;
        vector<int>pref(m);
        for (int s = 0; s < m; s++){
            if (s) pref[s] += pref[s-1];
            for (int k = 0; k <= n; k++) add(pref[s], dp[s][k]);
        }
        // dp[i] = dp[i-1]; //nic nie dokladamy
        for (int j = 1; j<m; j++){
            if (seg[j].second < a[i] || seg[j].first > b[i]) continue;
            int len = seg[j].second - seg[j].first + 1;
            // dp[i][j][1] = suma po dp[i-1][<j][cokolwiek]
            add(new_dp[j][1], mul(pref[j-1], len)); //dokladamy pierwszy element tego przedzialu
            // for (int s = 0; s < j; s++){
            //     for (int k = 0; k <= n; k++){
            //         if (dp[i-1][s][k]){
            //             debug(dp[i-1][s][k], len);
            //         }
            //         add(dp[i][j][1], mul(dp[i-1][s][k], len));
            //     }
            // } 
            for (int k = 2; k <= min(i, len); k++){
                //dokladamy juz nie pierwszy element tego przedzialu
                add(new_dp[j][k], mul(dp[j][k-1], mul(power(nck(len, k-1), mod-2), nck(len, k))));
            }
        }
        dp.swap(new_dp);
    }
    int ans = mod-1;
    for (int i = 0; i<m; i++){
        for (int j = 0; j<=n; j++){
            add(ans, dp[i][j]);
        }
    }
    cout << ans << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 9144 KB Output is correct
2 Correct 468 ms 8604 KB Output is correct
3 Correct 457 ms 8508 KB Output is correct
4 Correct 476 ms 8820 KB Output is correct
5 Correct 462 ms 8504 KB Output is correct
6 Correct 459 ms 8864 KB Output is correct
7 Correct 450 ms 8472 KB Output is correct
8 Correct 520 ms 8668 KB Output is correct
9 Correct 491 ms 8552 KB Output is correct
10 Correct 487 ms 8708 KB Output is correct
11 Correct 478 ms 8760 KB Output is correct
12 Correct 503 ms 8596 KB Output is correct
13 Correct 448 ms 8664 KB Output is correct
14 Correct 464 ms 8928 KB Output is correct
15 Correct 486 ms 8492 KB Output is correct
16 Correct 76 ms 2292 KB Output is correct
17 Correct 94 ms 2028 KB Output is correct
18 Correct 73 ms 1952 KB Output is correct
19 Correct 76 ms 2160 KB Output is correct
20 Correct 100 ms 1980 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 9144 KB Output is correct
2 Correct 468 ms 8604 KB Output is correct
3 Correct 457 ms 8508 KB Output is correct
4 Correct 476 ms 8820 KB Output is correct
5 Correct 462 ms 8504 KB Output is correct
6 Correct 459 ms 8864 KB Output is correct
7 Correct 450 ms 8472 KB Output is correct
8 Correct 520 ms 8668 KB Output is correct
9 Correct 491 ms 8552 KB Output is correct
10 Correct 487 ms 8708 KB Output is correct
11 Correct 478 ms 8760 KB Output is correct
12 Correct 503 ms 8596 KB Output is correct
13 Correct 448 ms 8664 KB Output is correct
14 Correct 464 ms 8928 KB Output is correct
15 Correct 486 ms 8492 KB Output is correct
16 Correct 76 ms 2292 KB Output is correct
17 Correct 94 ms 2028 KB Output is correct
18 Correct 73 ms 1952 KB Output is correct
19 Correct 76 ms 2160 KB Output is correct
20 Correct 100 ms 1980 KB Output is correct
21 Correct 1063 ms 14048 KB Output is correct
22 Correct 1107 ms 14008 KB Output is correct
23 Correct 1190 ms 13768 KB Output is correct
24 Correct 1073 ms 14000 KB Output is correct
25 Correct 1128 ms 13856 KB Output is correct
26 Correct 970 ms 13184 KB Output is correct
27 Correct 1016 ms 13304 KB Output is correct
28 Correct 1095 ms 13368 KB Output is correct
29 Correct 1008 ms 13304 KB Output is correct
30 Correct 1217 ms 15576 KB Output is correct
31 Correct 1281 ms 15712 KB Output is correct
32 Correct 1160 ms 15428 KB Output is correct
33 Correct 1316 ms 15604 KB Output is correct
34 Correct 1310 ms 15312 KB Output is correct
35 Correct 520 ms 8648 KB Output is correct
36 Correct 514 ms 8512 KB Output is correct
37 Correct 466 ms 8532 KB Output is correct
38 Correct 493 ms 8568 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1884 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 9144 KB Output is correct
2 Correct 468 ms 8604 KB Output is correct
3 Correct 457 ms 8508 KB Output is correct
4 Correct 476 ms 8820 KB Output is correct
5 Correct 462 ms 8504 KB Output is correct
6 Correct 459 ms 8864 KB Output is correct
7 Correct 450 ms 8472 KB Output is correct
8 Correct 520 ms 8668 KB Output is correct
9 Correct 491 ms 8552 KB Output is correct
10 Correct 487 ms 8708 KB Output is correct
11 Correct 478 ms 8760 KB Output is correct
12 Correct 503 ms 8596 KB Output is correct
13 Correct 448 ms 8664 KB Output is correct
14 Correct 464 ms 8928 KB Output is correct
15 Correct 486 ms 8492 KB Output is correct
16 Correct 76 ms 2292 KB Output is correct
17 Correct 94 ms 2028 KB Output is correct
18 Correct 73 ms 1952 KB Output is correct
19 Correct 76 ms 2160 KB Output is correct
20 Correct 100 ms 1980 KB Output is correct
21 Correct 1063 ms 14048 KB Output is correct
22 Correct 1107 ms 14008 KB Output is correct
23 Correct 1190 ms 13768 KB Output is correct
24 Correct 1073 ms 14000 KB Output is correct
25 Correct 1128 ms 13856 KB Output is correct
26 Correct 970 ms 13184 KB Output is correct
27 Correct 1016 ms 13304 KB Output is correct
28 Correct 1095 ms 13368 KB Output is correct
29 Correct 1008 ms 13304 KB Output is correct
30 Correct 1217 ms 15576 KB Output is correct
31 Correct 1281 ms 15712 KB Output is correct
32 Correct 1160 ms 15428 KB Output is correct
33 Correct 1316 ms 15604 KB Output is correct
34 Correct 1310 ms 15312 KB Output is correct
35 Correct 520 ms 8648 KB Output is correct
36 Correct 514 ms 8512 KB Output is correct
37 Correct 466 ms 8532 KB Output is correct
38 Correct 493 ms 8568 KB Output is correct
39 Runtime error 2 ms 1884 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -