oj.uz

Submission #965427

# Submission time Handle Problem Language Result Execution time Memory
965427 2024-04-18T14:00:29 Z steveonalex Boat (APIO16_boat) C++17
9 / 100
 381 ms 4840 KB 
#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const long MOD = 1e9 + 7;
ll fast_pow(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b /= 2;
    }
    return ans;
}
 
ll inverse(ll a){return fast_pow(a, MOD - 2);}
 
const long N = 505;
ll fact[N], ifact[N];
 
void prepare(){
    fact[0] = 1;
    for(long i = 1; i<N; ++i) fact[i] = fact[i-1] * i % MOD;
    ifact[N-1]= inverse(fact[N-1]);
    for(long i = N-1; i>=1; --i) ifact[i-1] = ifact[i] * i % MOD;
}
 
ll C(long n, long k){
    if (k < 0 || k > n) return 0;
    return fact[n] * ifact[k] % MOD * ifact[n - k] % MOD;
}
 
ll eulerCandy(long s, long k){
    return C(s + k - 1, k - 1);
}
 
ll normie(ll a){
    a %= MOD;
    if (a < 0) a += MOD;
    return a;
}

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

void sub(int &a, int b){
    a -= b;
    if (a < 0) a += MOD;
}

int dp[N * 2][N], s[N * 2][N];

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    prepare();

    int n; cin >> n;
    vector<pair<int, int>> a(n);
    for(int i= 0; i<n; ++i) cin >> a[i].first >> a[i].second;

    vector<int> b;
    for(pair<int, int> i: a){
        b.push_back(i.first - 1);
        b.push_back(i.second);
    }
    remove_dup(b);

    vector<pair<int, int>> range;
    range.push_back({0, 0});
    for(int i= 1; i<(int)b.size(); ++i) range.push_back({b[i-1] + 1, b[i]});

    a.insert(a.begin(), {0, 0});

    dp[0][0] = 1;
    for(int i= 0; i <= n; ++i) s[0][i] = 1;
    for(int i= 0; i<range.size(); ++i) s[i][0] = 1;

    for(int layer = 1; layer < (int)range.size(); ++layer){
        int len = range[layer].second - range[layer].first + 1;
        vector<int> fuck(min(n, len) + 1, 1); 
        for(int i = 1; i<(int)fuck.size(); ++i)
            fuck[i] = 1LL * fuck[i-1] * (len - i + 1) % MOD;
        for(int i = 1; i<(int)fuck.size(); ++i) 
            fuck[i] = 1LL * fuck[i] * ifact[i] % MOD;

        vector<int> love(n+1);
        love[1] = len;
        for(int i = 2; i<=n; ++i){
            for(int t = 2; t <= min(fuck.size() - 1, i); ++t){
                add(love[i], 1LL * fuck[t] * C(i - 2, t - 2) % MOD);
            }
        }

        for(int i = 1; i<=n; ++i){
            if (a[i].first > range[layer].first || range[layer].second > a[i].second) continue;
            int sum = s[layer - 1][i - 1];
            int cnt = 0;
            for(int j = i; j<=n; ++j){
                if (a[j].first > range[layer].first || range[layer].second > a[j].second) continue;
                cnt++;
                dp[layer][j] = 1LL * sum * love[cnt] % MOD;
            }
        }
        for(int i = 1; i<=n; ++i){
            s[layer][i] = dp[layer][i];
            add(s[layer][i], s[layer-1][i]);
            add(s[layer][i], s[layer][i-1]);
            sub(s[layer][i], s[layer-1][i-1]);
        }
    }

    int ans = 0;
    for(int j = 1; j< range.size(); ++j) 
    for(int i = 1; i<=n; ++i) add(ans, dp[j][i]);
 
    cout << ans << "\n";
    

    return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i= 0; i<range.size(); ++i) s[i][0] = 1;
      |                   ~^~~~~~~~~~~~~
boat.cpp:157:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for(int j = 1; j< range.size(); ++j)
      |                    ~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 4180 KB Output is correct
2 Correct 373 ms 4432 KB Output is correct
3 Correct 367 ms 4176 KB Output is correct
4 Correct 373 ms 4432 KB Output is correct
5 Correct 368 ms 4180 KB Output is correct
6 Correct 371 ms 4496 KB Output is correct
7 Correct 368 ms 4408 KB Output is correct
8 Correct 381 ms 4688 KB Output is correct
9 Correct 373 ms 4432 KB Output is correct
10 Correct 372 ms 4448 KB Output is correct
11 Correct 368 ms 4432 KB Output is correct
12 Correct 375 ms 4320 KB Output is correct
13 Correct 369 ms 4312 KB Output is correct
14 Correct 373 ms 4840 KB Output is correct
15 Correct 367 ms 4416 KB Output is correct
16 Correct 65 ms 2652 KB Output is correct
17 Correct 70 ms 2708 KB Output is correct
18 Correct 67 ms 2816 KB Output is correct
19 Correct 72 ms 2696 KB Output is correct
20 Correct 68 ms 2692 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 4180 KB Output is correct
2 Correct 373 ms 4432 KB Output is correct
3 Correct 367 ms 4176 KB Output is correct
4 Correct 373 ms 4432 KB Output is correct
5 Correct 368 ms 4180 KB Output is correct
6 Correct 371 ms 4496 KB Output is correct
7 Correct 368 ms 4408 KB Output is correct
8 Correct 381 ms 4688 KB Output is correct
9 Correct 373 ms 4432 KB Output is correct
10 Correct 372 ms 4448 KB Output is correct
11 Correct 368 ms 4432 KB Output is correct
12 Correct 375 ms 4320 KB Output is correct
13 Correct 369 ms 4312 KB Output is correct
14 Correct 373 ms 4840 KB Output is correct
15 Correct 367 ms 4416 KB Output is correct
16 Correct 65 ms 2652 KB Output is correct
17 Correct 70 ms 2708 KB Output is correct
18 Correct 67 ms 2816 KB Output is correct
19 Correct 72 ms 2696 KB Output is correct
20 Correct 68 ms 2692 KB Output is correct
21 Incorrect 84 ms 4180 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 4180 KB Output is correct
2 Correct 373 ms 4432 KB Output is correct
3 Correct 367 ms 4176 KB Output is correct
4 Correct 373 ms 4432 KB Output is correct
5 Correct 368 ms 4180 KB Output is correct
6 Correct 371 ms 4496 KB Output is correct
7 Correct 368 ms 4408 KB Output is correct
8 Correct 381 ms 4688 KB Output is correct
9 Correct 373 ms 4432 KB Output is correct
10 Correct 372 ms 4448 KB Output is correct
11 Correct 368 ms 4432 KB Output is correct
12 Correct 375 ms 4320 KB Output is correct
13 Correct 369 ms 4312 KB Output is correct
14 Correct 373 ms 4840 KB Output is correct
15 Correct 367 ms 4416 KB Output is correct
16 Correct 65 ms 2652 KB Output is correct
17 Correct 70 ms 2708 KB Output is correct
18 Correct 67 ms 2816 KB Output is correct
19 Correct 72 ms 2696 KB Output is correct
20 Correct 68 ms 2692 KB Output is correct
21 Incorrect 84 ms 4180 KB Output isn't correct
22 Halted 0 ms 0 KB -