oj.uz

Submission #480660

# Submission time Handle Problem Language Result Execution time Memory
480660 2021-10-17T15:02:00 Z TAMREF Boat (APIO16_boat) C++17
0 / 100
 1330 ms 8240 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long; using lf = long double; 
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mod = 1e9 + 7;

int inv[505] = {0, 1};

int n;
vector<int> cmp;
int a[505], b[505];

ll a_Ijk[2][1005][505]; // i' < i, j' = j, k' = k
ll b_ij[2][1005]; //i' < i, j' < j, k' arb
ll ans;

int main(){
    fio;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        ++b[i];
        cmp.pp(a[i]); cmp.pp(b[i]);
    }
    for(int i = 1; i <= n; i++) {
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
    }
    sort(all(cmp)); cmp.erase(unique(all(cmp)), cmp.end());
    int d = szz(cmp);
    for(int i = 1; i <= n; i++) {
        a[i] = lb(all(cmp), a[i]) - cmp.begin() + 1;
        b[i] = lb(all(cmp), b[i]) - cmp.begin() + 1;
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < d; j++) {
            b_ij[i & 1][j] = (b_ij[~i & 1][j] + b_ij[i & 1][j-1] - b_ij[~i & 1][j-1]) % mod;
            for(int k = 1; k <= n; k++) {
                a_Ijk[i & 1][j][k] = a_Ijk[~i & 1][j][k];
                ll dp = 0;
                if(a[i] <= j && j < b[i]) {
                    ll len = cmp[j] - cmp[j-1];
                    if(k == 1) {
                        dp = (1 + b_ij[~i & 1][j-1]) * len % mod;
                    }else{
                        dp = a_Ijk[~i & 1][j][k-1] * (len - k + 1) % mod * inv[k] % mod;
                    }
                }
                (a_Ijk[i & 1][j][k] += dp) %= mod;
                (b_ij[i & 1][j] += dp) %= mod;
                (ans += dp) %= mod;
            }
        }
    }
    cout << ans << endl;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1330 ms 8236 KB Output is correct
2 Incorrect 1228 ms 8240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1330 ms 8236 KB Output is correct
2 Incorrect 1228 ms 8240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1330 ms 8236 KB Output is correct
2 Incorrect 1228 ms 8240 KB Output isn't correct
3 Halted 0 ms 0 KB -