oj.uz

Submission #523173

# Submission time Handle Problem Language Result Execution time Memory
523173 2022-02-07T07:15:57 Z blue Boat (APIO16_boat) C++17
27 / 100
 221 ms 524292 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
#define sz(x) int(x.size())

const ll mod = 1'000'000'007;

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

ll ad(ll a, ll b)
{
    return (a+b) % mod;
}

ll sq(ll a)
{
    return mul(a,a);
}

ll pow(ll b, ll e)
{
    if(e == 0) return 1;
    else if(e % 2 == 1) return mul(b, pow(b, e-1));
    else return sq(pow(b, e/2));
}

ll get_inv(ll a)
{
    return pow(a, mod-2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    ll a[1+N], b[1+N];


    map<ll, ll> values;

    for(int i = 1; i <= N; i++)
    {
        cin >> a[i] >> b[i];
        b[i]++;

        values[a[i]] = 0;
        values[b[i]] = 0;
    }

    values[0] = 0;
    values[1] = 0;


    vll ep;

    for(auto& z : values) ep.push_back(z.first);

    int ct = sz(ep) - 1;

    vll blocksize(1+ct);
    blocksize[0] = 0;
    for(int i = 1; i <= ct; i++)
        blocksize[i] = ep[i] - ep[i-1];

    
    int x[1+N], y[1+N];


    // for(int i = 0; i <= ct; i++) cerr << i << " : " << ep[i] << ' ' << blocksize[i] << '\n';

    for(int i = 1; i <= N; i++)
    {
        x[i] = 0;
        int lo = 1, hi = ct;
        while(lo != hi)
        {
            int mid = (lo+hi)/2 + 1;
            if(ep[mid] <= a[i])
                lo = mid;
            else
                hi = mid-1;
        }
        x[i] = lo + 1;

        y[i] = 0;
        lo = 1, hi = ct;
        while(lo != hi)
        {
            int mid = (lo+hi)/2+1;
            if(ep[mid] <= b[i])
                lo = mid;
            else
                hi = mid-1;
        }
        y[i] = lo;
    }


    ll*** DP = new ll**[1+N];
    for(int i = 0; i <= N; i++)
    {
        DP[i] = new ll*[1+ct];
        for(int j = 0; j <= ct; j++)
        {
            DP[i][j] = new ll[1+N];
            for(int k = 0; k <= N; k++) DP[i][j][k] = 0;
        }
    }


    ll inv[1+N];
    for(int i = 1; i <= N; i++) inv[i] = get_inv(i);

    vvll DPsum(1+N, vll(1+ct, 0)); 

    // cerr << "!" <<  x[1] << ' ' << y[1] << '\n';
    for(int j = x[1]; j <= y[1]; j++)
    {
        DPsum[1][j] = ad(DPsum[1][j], blocksize[j]);
        DP[1][j][1] = blocksize[j];   
    }


    for(int i = 2; i <= N; i++)
    {
        for(int j = 1; j <= ct; j++)
        {
            for(int k = 1; k <= i; k++)
            {
                DP[i][j][k] = DP[i-1][j][k];

                if(x[i] <= j && j <= y[i])
                {
                    if(j == 1 && k == 1)
                    {
                        ;//DP[i][1][1] = blocksize[j] * 
                    }
                    else if(j == 1)
                    {
                        ;
                    }
                    else if(k == 1)
                    {
                        ll curr = 1;

                        for(int j2 = 1; j2 < j; j2++)
                            curr = ad(curr, DPsum[i-1][j2]);

                        DP[i][j][1] = ad(DP[i][j][1], mul(curr, blocksize[j]));
                    }
                    else
                    {
                        if(k <= blocksize[j])
                            DP[i][j][k] = ad(DP[i][j][k], mul(DP[i-1][j][k-1], mul(blocksize[j] - k + 1, inv[k])));
                    }
                }

                DPsum[i][j] = ad(DPsum[i][j], DP[i][j][k]);
            }
        }
    }

    ll res = 0;
    for(int j = 1; j <= ct; j++)
        res = ad(res, DPsum[N][j]);

    cout << res << '\n';
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 221 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 221 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 16836 KB Output is correct
2 Correct 19 ms 16844 KB Output is correct
3 Correct 19 ms 16928 KB Output is correct
4 Correct 19 ms 16844 KB Output is correct
5 Correct 19 ms 16940 KB Output is correct
6 Correct 20 ms 16844 KB Output is correct
7 Correct 23 ms 17052 KB Output is correct
8 Correct 28 ms 16864 KB Output is correct
9 Correct 22 ms 16872 KB Output is correct
10 Correct 23 ms 16844 KB Output is correct
11 Correct 19 ms 16908 KB Output is correct
12 Correct 19 ms 16948 KB Output is correct
13 Correct 18 ms 16916 KB Output is correct
14 Correct 18 ms 16832 KB Output is correct
15 Correct 19 ms 16844 KB Output is correct
16 Correct 10 ms 9932 KB Output is correct
17 Correct 10 ms 9676 KB Output is correct
18 Correct 10 ms 9868 KB Output is correct
19 Correct 10 ms 9932 KB Output is correct
20 Correct 9 ms 9544 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 221 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -